Haskell Cont monad 如何以及为什么工作? [英] How and why does the Haskell Cont monad work?

问题描述

Cont monad 是这样定义的:

This is how the Cont monad is defined:

newtype Cont r a = Cont { runCont :: (a -> r) -> r }

instance Monad (Cont r) where
    return a = Cont ($ a)
    m >>= k  = Cont $ c -> runCont m $ a -> runCont (k a) c

您能解释一下这是如何以及为什么起作用的吗?它在做什么?

Could you explain how and why this works? What is it doing?

推荐答案

关于延续 monad，首先要意识到的是，从根本上说，它根本没有做任何事情.是真的！

The first thing to realize about the continuation monad is that, fundamentally, it's not really doing anything at all. It's true!

一般而言，延续的基本思想是它代表计算的其余部分.假设我们有一个这样的表达式:foo (bar x y) z.现在，只提取括号中的部分，bar x y——这是整个表达式的部分，但它不仅仅是一个我们可以应用的函数.相反，我们需要应用一个函数到.因此，在这种情况下，我们可以将其余计算"称为 a ->foo a z，我们可以将其应用于 bar x y 以重建完整的表单.

The basic idea of a continuation in general is that it represents the rest of a computation. Say we have an expression like this: foo (bar x y) z. Now, extract just the parenthesized portion, bar x y--this is part of the total expression, but it's not just a function we can apply. Instead, it's something we need to apply a function to. So, we can talk about the "rest of the computation" in this case as being a -> foo a z, which we can apply to bar x y to reconstruct the complete form.

现在，碰巧这个计算的其余部分"的概念很有用，但使用起来很尴尬，因为它是我们正在考虑的子表达式之外的东西.为了让事情做得更好，我们可以把事情从里到外:提取我们感兴趣的子表达式，然后将它包装在一个函数中，该函数接受一个代表计算其余部分的参数:k ->k (bar x y).

Now, it happens that this concept of "the rest of the computation" is useful, but it's awkward to work with, since it's something outside of the subexpression we're considering. To make things work better, we can turn things inside-out: extract the subexpression we're interested in, then wrap it in a function that takes an argument representing the rest of the computation: k -> k (bar x y).

这个修改后的版本给了我们很大的灵活性——它不仅从它的上下文中提取一个子表达式，而且它让我们在子表达式本身内操纵外部上下文.我们可以将其视为一种暂停计算，让我们可以明确控制接下来发生的事情.现在，我们如何概括这一点?好吧，子表达式几乎没有变化，所以让我们用一个内向外函数的参数替换它，给我们 x k ->k x——换言之，无非是函数应用，逆向.我们可以很容易地编写 flip ($)，或者添加一点异国情调的外语并将其定义为运算符 |>.

This modified version gives us a lot of flexibility--not only does it extract a subexpression from its context, but it lets us manipulate that outer context within the subexpression itself. We can think of it as a sort of suspended computation, giving us explicit control over what happens next. Now, how could we generalize this? Well, the subexpression is pretty much unchanged, so let's just replace it with a parameter to the inside-out function, giving us x k -> k x--in other words, nothing more than function application, reversed. We could just as easily write flip ($), or add a bit of an exotic foreign language flavor and define it as an operator |>.

现在，将表达式的每一个部分翻译成这种形式会很简单，尽管很乏味而且非常令人困惑.幸运的是，有更好的方法.作为 Haskell 程序员，当我们考虑在背景上下文中构建计算时，我们想到的下一件事是说，这是一个单子吗?在这种情况下，答案是是的，是的.

Now, it would be simple, albeit tedious and horribly obfuscating, to translate every piece of an expression to this form. Fortunately, there's a better way. As Haskell programmers, when we think building a computation within a background context the next thing we think is say, is this a monad? And in this case the answer is yes, yes it is.

为了把它变成一个 monad，我们从两个基本的构建块开始:

To turn this into a monad, we start with two basic building blocks:

• 对于 monad m，ma 类型的值表示在 monad 的上下文中可以访问 a 类型的值.
• 我们暂停计算"的核心是翻转函数应用.

• For a monad m, a value of type m a represents having access to a value of type a within the context of the monad.
• The core of our "suspended computations" is flipped function application.

在此上下文中访问 a 类型的内容是什么意思?这只是意味着，对于某些值 x :: a，我们已经将 flip ($) 应用到 x，给我们一个函数接受一个函数，该函数接受 a 类型的参数，并将该函数应用于 x.假设我们有一个挂起的计算，其中包含 Bool 类型的值.这给了我们什么类型?

What does it mean to have access to something of type a within this context? It just means that, for some value x :: a, we've applied flip ($) to x, giving us a function that takes a function which takes an argument of type a, and applies that function to x. Let's say we have a suspended computation holding a value of type Bool. What type does this give us?

> :t flip ($) True
flip ($) True :: (Bool -> b) -> b

因此对于挂起的计算，类型 m a 的结果是 (a -> b) ->b... 这可能是一个反高潮，因为我们已经知道 Cont 的签名，但现在让我幽默一下.

So for suspended computations, the type m a works out to (a -> b) -> b... which is perhaps an anticlimax, since we already knew the signature for Cont, but humor me for now.

这里要注意的一个有趣的事情是，一种反转"也适用于 monad 的类型:Cont b a 表示一个函数，它接受一个函数 a ->b 并计算为 b.由于延续代表计算的未来"，因此签名中的类型 a 在某种意义上代表过去".

An interesting thing to note here is that a sort of "reversal" also applies to the monad's type: Cont b a represents a function that takes a function a -> b and evaluates to b. As a continuation represents "the future" of a computation, so the type a in the signature represents in some sense "the past".

所以，替换 (a -> b) ->b 和 Cont b a，我们反向函数应用程序的基本构建块的 monadic 类型是什么?<代码>a ->(a -> b) ->b 转换为 a ->Cont b a... 与 return 相同的类型签名，事实上，它正是如此.

So, replacing (a -> b) -> b with Cont b a, what's the monadic type for our basic building block of reverse function application? a -> (a -> b) -> b translates to a -> Cont b a... the same type signature as return and, in fact, that's exactly what it is.

从现在开始，几乎所有的东西都直接从类型中分离出来:除了实际的实现之外，基本上没有任何明智的方法来实现 >>=.但它实际上在做什么?

From here on out, everything pretty much falls directly out from the types: There's essentially no sensible way to implement >>= besides the actual implementation. But what is it actually doing?

此时我们回到我最初所说的:continuation monad 并没有真正做任何事情.Cont r a 类型的东西在微不足道上等同于 a 类型的东西，只需提供 id 作为暂停计算的参数.这可能会让人问，如果 Cont ra 是一个 monad 但转换是如此微不足道，那么 a 是否应该单独 also单子?当然，这不能正常工作，因为没有类型构造函数可以定义为 Monad 实例，但是假设我们添加了一个简单的包装器，例如 data Id a = Id a.这确实是一个单子，即身份单子.

At this point we come back to what I said initially: the continuation monad isn't really doing much of anything. Something of type Cont r a is trivially equivalent to something of just type a, simply by supplying id as the argument to the suspended computation. This might lead one to ask whether, if Cont r a is a monad but the conversion is so trivial, shouldn't a alone also be a monad? Of course that doesn't work as is, since there's no type constructor to define as a Monad instance, but say we add a trivial wrapper, like data Id a = Id a. This is indeed a monad, namely the identity monad.

>>= 对身份 monad 有什么作用?类型签名是 Id a ->(a ->Id b) ->id b，相当于 a ->(a -> b) ->b，又是简单的函数应用.确定 Cont ra 与 Id a 等价之后，我们也可以推断出，在这种情况下，(>>=) 只是函数应用.

What does >>= do for the identity monad? The type signature is Id a -> (a -> Id b) -> Id b, which is equivalent to a -> (a -> b) -> b, which is just simple function application again. Having established that Cont r a is trivially equivalent to Id a, we can deduce that in this case as well, (>>=) is just function application.

当然，Cont ra 是一个疯狂的颠倒世界，每个人都有山羊胡子，所以实际发生的事情包括以令人困惑的方式将事物打乱，以便将两个暂停的计算链接在一起成为一个新的暂停计算，但本质上，实际上并没有什么不寻常的事情发生！将函数应用于参数，呵呵，函数式程序员生活中的又一天.

Of course, Cont r a is a crazy inverted world where everyone has goatees, so what actually happens involves shuffling things around in confusing ways in order to chain two suspended computations together into a new suspended computation, but in essence, there isn't actually anything unusual going on! Applying functions to arguments, ho hum, another day in the life of a functional programmer.

这篇关于Haskell Cont monad 如何以及为什么工作?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！