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

Question

我想知道是否可以使用 Control.Arrow.loop 实现阶乘。

loop :: ArrowLoop a => a (b, d) (c, d) -> a b c

一个明显的想法是实现一个以某种方式终止的分支（一个分支，其中对的第一个元素（类型 c）不依赖于对的第二个元素（类型 d)). 在我看来，这是不可能完成的，因为在第一次迭代期间我们不能将任何布尔函数应用于该对的第二个元素（类型 d），因为它会导致无限递归，所以它只会留下我们使用参数（类型 b），但任何布尔函数的结果都不会根据迭代而有所不同（参数不会改变），因此，它要么立即终止，要么根本不终止。我的另一个想法是创建无穷无尽的阶乘流，但这似乎也不真实，因为再一次，论点无法改变。所以，我有 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]

编辑

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

首先让我们看一下使用 fix 的 fact 的另一种更好的（由于尾递归）实现，因此我们可以看到它与我们使用 [=20= 的实现相比如何]:

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

我们可以看到它已经不远了。在这两种情况下，我们都将 f 作为参数，并且我们 return 支持使用该 f 的函数，事实上，returned 非递归函数在这两种情况下是相同的个案。为清楚起见，让我们在两个地方提取它以供重用：

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，但是查看类型变量可以更好地了解正在发生的事情。真正发生的事情只是通过定点组合器进行递归。

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

How to implement Factorial via Control.Arrow.loop?

haskell

functional-programming

factorial

arrows