loops - 修复与 ArrowLoop

Question

loop的描述来自 Control.Arrow :

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

所以我的问题是:

是否有可能实现那个特定的 loop通过 fix ?

它们的功能有何不同？

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

箭头也概括了“过程”的概念:当 Arrow a , a b c是一种计算 c 的方法来自 b .如果 ArrowLoop被定义为直接概括 fix ，那么它就会严重瘫痪。 fix必须在没有任何上下文的情况下“执行”该过程并直接生成 b 类型的值，表示“进程”a b b不能，例如执行IO .或者，考虑箭头

newtype LT i o = LT { runLT :: [i] -> [o] }

如果 fix 你会喜欢它将产生 [b]来自 LT b b ，但事实并非如此。
loop是绕过这些限制的一种方法。它将过程作为参数并产生过程作为结果。从某种意义上说，与第一个进程相关的所有上下文都可以在第二个进程中保留下来，如果 loop 是不可能的。更像 fix .

请注意，我可以实现 fix 的模拟。对于 ArrowLoop年代:

-- 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'任何一个。