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

问题描述

这是Cont monad的定义：

  newtype Cont ra = Cont {runCont ::（a  - > r） - > r} 
 
实例Monad（Cont r）其中
返回a = Cont（$ a）
 m>> = k = Cont $ \c  - > runCont m $ \a  - > runCont（k a）c 
  

你能解释一下它是如何工作的？它是干什么的？

关于继续monad的第一件事情是从根本上说，做任何事情。这是真的！

继续的基本概念是它代表了计算的其余部分。假设我们有这样一个表达式： foo（bar x y）z 。现在，只需提取括号内的部分，即 bar x y - 这是整个表达式的部分，但它不仅仅是我们可以应用的函数。相反，这是我们需要将一个函数应用于的事情。因此，在这种情况下，我们可以讨论其余计算，因为 \ a - > foo az ，我们可以将它应用于 bar xy 来重建完整的表单。

现在，这种剩余计算的概念是有用的，但它的工作很尴尬，因为它是我们正在考虑的子表达式之外的东西。为了让事情变得更好，我们可以将事情从内到外：提取我们感兴趣的子表达式，然后将其包装在一个函数中，该函数接受一个表示其余计算的参数： \k - > k（bar xy）。

这个修改版本给了我们很大的灵活性 - 不仅从它的上下文中提取了一个子表达式，但它可以让我们在子表达式本身内操纵外部的上下文。我们可以将它看作一种暂停计算，让我们明确控制接下来会发生什么。现在，我们怎么概括这个？那么，这个子表达式几乎没有变化，所以让我们用一个参数代替它，这个函数给了我们 \x k - > k x - 换句话说，只不过是函数应用程序，反转。我们可以轻松地编写 flip（$），或者添加一些具有异国情调的外语风格，并将其定义为运算符 |> 。

现在，将表达式的每一个表达转换为这种形式将会很简单，尽管繁琐且令人生畏地混淆。幸运的是，还有更好的方法。作为Haskell程序员，当我们认为在后台环境中构建计算时，我们认为接下来的事情是，这是否是monad？在这种情况下，答案是是的

，是的。

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

• 对于monad m ，类型 ma 的值表示在monad的上下文中可以访问 a 类型的值。
  
• 我们的暂停计算的核心是翻转函数
  在这种情况下？这仅仅意味着，对于某些值 x :: a ，我们已经将 flip（$）应用于 x ，给我们一个函数，它接受一个函数，该函数接受一个类型为 a 的参数，并将该函数应用于 X 。假设我们有一个暂挂的计算，它保存着 Bool 类型的值。这给了我们什么类型？

   > ：t flip（$）True 
   flip（$）True ::（Bool  - > b） - > b 
    

  因此，对于暂停计算，类型 ma 解决（a - > b） - >因为我们已经知道 Cont 的签名，但是我现在就幽默了。

  $ b
  $ b

  这里需要注意的一点是，一种反转也适用于monad的类型： Cont ba 代表一个函数，它需要一个函数 a - > b 并评估为 b 。作为一个延续表示计算的未来，所以签名中的类型 a 代表某种意义上的过去。
  
  

  因此，将（a - > b） - > b 与 Cont b a ，我们的反函数应用程序的基本构建块的monadic类型是什么？ a - > （a - > b） - > b 转换为 a - > Cont ba ...与 return 相同的类型签名，实际上就是这样。

  
  
  

  从这里开始，几乎所有的东西都直接从类型中分离出来：除了实际上，实际上没有明智的方法来实现>> = 实现。但是，它究竟是干什么的？ ？
  
  

  在这一点上，我们回到我刚才说的话：继续monad并不是真的在做任何事情。类型 Cont ra 的东西只是简单地类型 a ，简单地通过提供 id 作为暂停计算的参数。这可能会导致人们询问，如果 Cont ra 是一个monad，但转换过于平凡，是否不应该是 a 单独也是是单子吗？当然，这不起作用，因为没有类型构造函数来定义 Monad 实例，但是说我们添加了一个简单的包装器，比如数据Id a = Id a 。这确实是一个monad，即身份monad。

  
  
  

  >>> = 为身份monad做？类型签名是 Id a - > （a - > Id b） - > Id b ，相当于 a - > （a - > b） - > b ，这只是简单的函数应用程序。确定 Cont ra 与 Id a 相当，我们可以推断在这种情况下， （>> =）仅仅是函数应用程序。 当然， Cont ra 是一个疯狂的倒置式世界，每个人都有山泥倾泻的感觉，所以实际上发生的事情包括以混乱的方式对事物进行混洗，以便将两个暂停计算链接在一起，形成一个新的暂停计算，本质上，实际上并不是什么不寻常的东西！在函数式程序员的生活中，将函数应用于参数，哼哼。

  
  

  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?

  解决方案

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

  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.

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

  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 |>.

  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.

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

  • 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.

  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
  

  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.

  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".

  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?

  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.

  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.

  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屋！