如何通过Control.Arrow.loop实现因子法？

Question

我想知道是否可以用Control.Arrow.loop来实现factorial。

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

其中一个明显的想法是实现一个以某种方式终止的分支（一个分支，其中对的第一个元素（类型是 c)不会依赖于该对的第二个元素(类型的 d)).在我看来，这是不可能的，因为我们不能将任何布尔函数应用于该对的第二个元素(type d)，因为它将导致无限递归，所以在第一次迭代时，我们只留下了参数（type b)，但任何布尔函数的结果都不会因为迭代的不同而不同(参数不会改变)，因此，它要么立即终止，要么永远不会终止.我的另一个想法是创建一个无穷无尽的因子流，但这似乎也不是真实的，因为，参数再次不能改变.所以，我有3个问题。

1. 我上面的观点对吗?
2. 我是否遗漏了任何其他的概念，这些概念将有助于实现通过 Control.Arrow.loop?
3. 这种实现方式的正确思路是什么？

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 最后，但看类型变量反而能更好地了解事情的真相。而真正的事情只是通过定点组合器的手段进行递归。