修复与ArrowLoop

Question

loop来自的描述Control.Arrow:

循环运算符表示计算,其中输出值作为输入反馈,尽管计算仅发生一次.它以箭头符号表示rec值递归构造的基础.

它的源代码,以及它的实例化(->):

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

所以我的问题是:

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

Answer 1

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) ()
   

2. 上面的内容应该说服你,loop并且fix在谈论时具有同等的威力(->).那么,为什么箭头意图概括函数,是ArrowLoop不是这样定义的呢？

   class Arrow a => ArrowLoop a where
     fix :: a b b -> b
   

   箭头也概括了"过程"的概念:何时Arrow a,a b c是一种c从a 计算a 的方法b.如果ArrowLoop被定义为直接推广fix,那么它将严重削弱.fix必须在没有任何上下文的情况下"执行"该过程并直接产生类型的值b,这意味着"过程" a b b不能例如执行IO.或者,考虑箭头

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

   你喜欢它,如果从a fix产生[b]a LT b b,但它没有.

   loop是围绕这些限制的一种方式.它将一个进程作为参数并生成一个进程作为结果.从某种意义上说,与第一个过程相关的所有上下文都可以在第二个过程中存活,如果loop更像是这样的话就不可能存在fix.

   请注意,我可以实现的模拟fix为ArrowLoopS:

   -- 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'无论是.