是否可以通过Control.Arrow.loop实现阶乘？

Question

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

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

一个显而易见的想法是实现某种终止分支（该分支对（类型c）的第一个元素不依赖于该对（类型d）的第二个元素的分支）。在我看来，这是无法完成的，因为我们无法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]

编辑

似乎在答案上稍加扩展可能会有所帮助。

首先，让我们看一下factusing 的另一种更好的实现（由于尾递归）fix，因此我们可以看到它与我们的实现相比如何loop：

?> import Data.Function
?> fix error

我们可以看到它并不遥远。在这两种情况下，我们都将其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和的for循环Kleisli）可提供有关它们之间关系的更多见解：

?> 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]

他们真的很亲密。

类型签名如何：

?> :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中端，但看着型变量，而不是给出一个更好地了解发生了什么事情。真正发生的只是通过定点组合器进行递归。