修复与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
所以我的问题是:
- 是否可以通过
fix
来实现特定的loop
? - 它们的功能有何不同?
- Is it possible to implement that particular
loop
viafix
? - How are their functionalities different?
推荐答案
-
好吧,当然.每个递归定义都可以用
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 ArrowLoop
s:
-- 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屋!