在 Haskell 中用（广义）箭头编写阶乘

Question

我想在 Haskell 中用

(->)

箭头写一个阶乘。我不明白如何将递归翻译成

loop

。我已经成功地使用

loop

为我的阶乘设置了一个固定点，但现在 lambda 抽象出现了问题，我无法翻译它。

loop f b = let (d, c) = f (d, b) in c
g = \(f, x) -> (\x -> if x == 0 then 1 else x * f (x - 1), f x)
main = print $ loop g 5

有一篇关于在另一个转换流的箭头中编写阶乘的文章：

[a] -> [b]

，但这不是我感兴趣的情况。我正在寻找的是更多类似的。

如何在

(->)

箭头中写阶乘？

Answer 1

这里是 Haskell 箭头表示法中阶乘函数的等效递归定义。

fact :: Integer -> Integer
fact = proc b -> do
    rec
        c <- f -<< b
        f <- g -< f
    returnA -< c

g :: (Integer -> Integer) -> Integer -> Integer
g f x = if x == 0 then 1 else x * f (x-1)

递归块的第二行清楚地表明阶乘函数是

g

的不动点。 在第一行中，需要一个高阶箭头应用程序

-<<

，因为

f

也是块内的箭头。 该行也可以写成

c <- app -< (f,b)

目前尚不清楚是否可以通过仅定义数据（即不应用高阶箭头）来以递归箭头表示法进行定义。

Answer 2

一种可能是首先将递归转换为使用

fix

，然后使用

fix

实现

loop

：

import Control.Arrow

fix :: (a -> a) -> a
fix = loop (\(f, x) -> let x' = f x in (x', x'))

或使用箭头符号进行无点：

fix = loop (uncurry ($) >>> (id &&& id))