haskell - 如何通过 Control.Arrow.loop 实现阶乘？

Question

我想知道是否可以使用 Control.Arrow.loop 实现阶乘。
loop :: ArrowLoop a => a (b, d) (c, d) -> a b c
一个明显的想法是实现一个以某种方式终止的分支(一个分支，其中对的第一个元素(类型 c)不依赖于对的第二个元素(类型 d))。
在我看来，这是无法完成的，因为我们无法在第一次迭代期间将任何 bool 函数应用于该对的第二个元素(类型 d)，因为它会导致无限递归，所以它只会给我们留下参数(类型 b )，但任何 bool 函数的结果都不会因迭代而有所不同(参数不会改变)，因此，它要么立即终止，要么根本不终止。
我的另一个想法是创建无穷无尽的阶乘，但这似乎也不真实，因为再一次，这个论点无法改变。
所以，我有3个问题:

我对上述几点是正确的吗？

我是否遗漏了任何其他有助于通过 Control.Arrow.loop 实现阶乘的概念？ ?

这个实现背后的正确想法是什么？

Answer 1

我从未真正使用过ArrowLoop之前，loop很酷。

这是使用 loop 实现的阶乘:

fact :: Integer -> Integer
fact =
  loop $ \(n, f) ->
    ( f n 1
    , \i acc ->
        if i > 0
          then f (i - 1) (i * acc)
          else acc)

试一试吧:

λ> fact <$> [1..11]
[1,2,6,24,120,720,5040,40320,362880,3628800,39916800]

我不知道我是否可以回答您的第一个问题，但对于第三个问题，这显然是可能的。对于可以帮助您的概念，我认为解决点是您正在寻找的那个。例如，您可以从尝试这个开始；)

λ> import Data.Function
λ> fix error

一旦你按够了 Ctrl+C您可以使用固定点编写阶乘:

λ> let fact = fix $ \ f i -> if i > 1 then i * f (i - 1) else i
λ> fact <$> [1..11]
[1,2,6,24,120,720,5040,40320,362880,3628800,39916800]

编辑

似乎对答案进行一些扩展可能会有所帮助。

首先让我们看一下 fact 的另一种更好的(由于尾递归)实现。使用 fix ，所以我们可以看到它与使用 loop 的实现相比如何:

factFix :: Integer -> Integer
factFix n =
  fix
    (\f ->
       \i acc ->
         if i > 0
           then f (i - 1) (i * acc)
           else acc)
    n
    1

我们可以看到它并不遥远。在这两种情况下，我们都会得到 f作为参数，我们返回一个使用它的函数 f ，实际上，返回的非递归函数在这两种情况下都是相同的。为清楚起见，让我们在两个地方都将其提取为重用:

factNoRec :: (Ord p, Num p) => (p -> p -> p) -> p -> p -> p
factNoRec f i acc =
  if i > 0
    then f (i - 1) (i * acc)
    else acc

factLoop :: Integer -> Integer
factLoop n = loop (\(k, f) -> (f k 1, factNoRec f)) n

factFix :: Integer -> Integer
factFix n = fix (\f -> factNoRec f) n 1

希望现在它们是真正相关的概念更加明显。

研究 fix 的实现和 loop (至少对于函数，因为还有 mfix 和循环 Kleisli )提供了对它们关系的更多洞察:

λ> fix f = let x = f x in x
λ> loop f b = let (c,d) = f (b,d) in c

他们真的很亲近。

类型签名怎么样:

λ> :t fix
fix :: (t -> t) -> t
λ> :t loop
loop :: ((b, d) -> (c, d)) -> b -> c

那些看起来不一样。但是如果你在 fact 中做一点统一你会看到 fix和 loop获取类型:

λ> :t fix :: ((a -> b -> c) -> (a -> b -> c)) -> a -> b -> c
λ> :t loop :: ((b, a -> b -> c) -> (c, a -> b -> c)) -> b -> c

所有 a b和 c成为全部 Integer最后，但是查看类型变量可以更好地了解正在发生的事情。真正发生的事情只是通过定点组合器进行递归。