修复与 ArrowLoop

Question

来自 Control.Arrow 的 loop 的描述：

The loop operator expresses computations in which an output value is fed back as input, although the computation occurs only once. It underlies the rec value recursion construct in arrow notation.

它的源代码，以及 (->) 的实例化：

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

instance ArrowLoop (->) where
    loop f b = let (c,d) = f (b,d) in c

这立刻让我想起了 fix，定点组合器：

fix :: (a -> a) -> a
fix f = let x = f x in x

所以我的问题是：

是否可以通过 fix 实现特定的 loop？
它们的功能有何不同？

Answer 1

当然可以。每个递归定义都可以写成 fix:

loop f b = let (c, d) = f (b, d) in c
loop f b = fst $ let (c, d) = f (b, d) in (c, d)
loop f b = fst $ let x = f (b, d) in x
loop f b = fst $ let x = f' x in x
  where f' (_, d) = f (b, d)
loop f b = fst $ fix $ f . (b,) . snd

反之亦然：

fix f = loop (join (,) . f . snd) ()

以上应该让你相信loop和fix在谈论(->)时是同等强大的。那么，如果箭头是为了泛化函数，为什么 ArrowLoop 不是这样定义的呢？
```
class Arrow a => ArrowLoop a where
  fix :: a b b -> b
```
Arrows 也概括了 "process" 的概念：当 Arrow a 时，a b c 是一种从 b 计算 c 的方法。如果把ArrowLoop定义为直接泛化fix，那就严重残废了。 fix 必须在没有任何上下文的情况下 "execute" 过程并直接生成类型 b 的值，这意味着 "process" a b b 不能，例如执行IO。或者，考虑箭头
```
newtype LT i o = LT { runLT :: [i] -> [o] }
```
如果 fix 可以从 LT b b 生成 [b]，你会喜欢它，但事实并非如此。

loop 是解决这些限制的一种方法。它以一个过程作为参数并产生一个过程作为结果。从某种意义上说，与第一个进程相关的所有上下文都可以在第二个进程中幸存下来，如果 loop 更像 fix.
则这是不可能的
请注意，我可以为 ArrowLoop 实现 fix 的模拟：
```
-- resulting process ignores its input
fix' :: ArrowLoop a -- taking an impl of loop as argument
     => a b b -> a u b
fix' f = loop ((id &&& id) . f . arr snd)
-- take off the outer application to () (application means (->), after all)
-- and arrowify: join (,) = id &&& id; snd = arr snd; (Prelude..) = (Control.Category..)
-- but the RHSs are more general
```
但我不相信
```
loop' :: Arrow a => (forall x u. a x x -> a u x) -- taking an impl of fix' as argument
      -> a (b, d) (c, d) -> a b c
```
是可以实现的，所以我们也不能把ArrowLoop建立在fix'之上。

修复与 ArrowLoop

fix vs. ArrowLoop

loops

haskell

arrows

fixpoint-combinators