修复与ArrowLoop [英] fix vs. ArrowLoop

问题描述

Control.Arrow中loop的描述:

尽管运算仅发生一次，但循环运算符表示将输出值作为输入反馈的运算.它是箭头表示法的rec值递归构造的基础.

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.

它的源代码及其对(->)的实例化:

Its source code, and its instantiation for (->):

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:

This immediately reminds me of fix, the fixpoint combinator:

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

所以我的问题是:

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

1. Is it possible to implement that particular loop via fix?
2. How are their functionalities different?

推荐答案

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没有这样定义?

The above should convince you that loop and fix are equivalently powerful when talking about (->). Why, then, if arrows are meant to generalize functions, is ArrowLoop not defined like so?

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

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

Arrows also generalize the notion of "process": when Arrow a, a b c is a way to calculate a c from a b. If ArrowLoop was defined to directly generalize fix, then it would be severely crippled. fix would have to "execute" the process without any context and directly produce a value of type b, which means the "process" a b b cannot e.g. perform IO. Or, consider the arrow

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

如果fix会从LT b b生成[b]，但您却不愿意，那么您会想要的.

You’d like it if fix would produce a [b] from a LT b b, but it doesn’t.

loop是解决这些限制的一种方法.它以过程作为参数，并产生过程作为结果.从某种意义上说，与第一个过程相关的所有上下文都可以在第二个过程中保留下来，如果loop更像是fix，则不可能.

loop is a way around these restrictions. It takes a process as argument and produces a process as result. In a sense, all the context associated with the first process can be survived in the second, which would not be possible if loop were more like fix.

请注意，我可以为ArrowLoop s实现fix的类似物:

Note that I can implement an analogue of fix for 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'上.

is implementable, so we can’t base ArrowLoop on fix' either.

这篇关于修复与ArrowLoop的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！