修复与ArrowLoop

问题描述

Control.Arrow中loop的描述:

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

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的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！