Haskell Cont monad 如何以及为何工作？

发布于 2024-09-11 08:32:59 字数 281 浏览 9 评论 0原文

这就是 Cont monad 的定义方式：

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

你能解释一下它是如何工作的以及为什么工作吗？它在做什么？

原文

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?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

剑心龙吟 2024-09-18 08:32:59

关于延续单子，首先要认识到的是，从根本上来说，它根本没有做任何事情。这是真的！

一般来说，延续的基本思想是它代表计算的其余部分。假设我们有一个这样的表达式：foo (bar xy) z。现在，仅提取括号部分，bar x y——这是整个表达式的部分，但它不仅仅是我们可以应用的函数。相反，我们需要将函数应用到它。因此，在这种情况下，我们可以将“其余计算”视为 \a -> foo a z，我们可以将其应用于 bar x y 来重建完整的形式。

现在，“其余计算”的概念很有用，但使用起来很尴尬，因为它超出了我们正在考虑的子表达式的范围。为了让事情更好地工作，我们可以把事情从里到外：提取我们感兴趣的子表达式，然后将其包装在一个函数中，该函数接受一个代表其余计算的参数：\k -> k（条xy）。

这个修改后的版本为我们提供了很大的灵活性——它不仅从上下文中提取子表达式，而且还允许我们在子表达式本身内操作外部上下文。我们可以将其视为一种暂停计算，使我们能够明确控制接下来发生的事情。现在，我们如何概括这一点？好吧，子表达式几乎没有变化，所以我们只需将其替换为 inside-out 函数的参数，即可得到 \xk -> k x——换句话说，只不过是函数应用，颠倒了。我们可以轻松地编写 flip ($)，或者添加一点异国情调的外语风格并将其定义为运算符 |>。

现在，将表达式的每个部分翻译成这种形式将很简单，尽管很乏味且极其混乱。幸运的是，有更好的方法。作为 Haskell 程序员，当我们考虑在后台上下文中构建计算时，我们想到的下一件事是说，这是一个 monad 吗？ 在这种情况下，答案是 >是的，是的。

要将其转换为 monad，我们从两个基本构建块开始：

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

在此上下文中访问 a 类型的内容意味着什么？它只是意味着，对于某个值 x :: a，我们将 flip ($) 应用于 x，为我们提供了一个函数接受一个函数，该函数接受 a 类型的参数，并将该函数应用于 x。假设我们有一个暂停的计算，其中包含 Bool 类型的值。这给了我们什么类型？

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

因此，对于挂起的计算，类型 m a 计算为 (a -> b) -> b...这可能是一个虎头蛇尾的事情，因为我们已经知道了 Cont 的签名，但现在请让我高兴一下。

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

因此，替换 (a -> b) -> b 和 Cont b a，我们的反向函数应用程序的基本构建块的一元类型是什么？ a-> (a→b)→ b 转换为 a ->继续 b a...与 return 相同的类型签名，事实上，这正是它的本质。

从现在开始，一切几乎都直接从类型中产生：除了实际的实现之外，基本上没有明智的方法来实现>>=。但它实际上在做什么？

此时我们回到我最初所说的：延续 monad 并没有真正做任何事情。 Cont r a 类型的内容基本上等同于 a 类型的内容，只需提供 id 作为挂起计算的参数即可。这可能会让人问，如果 Cont r a 是一个 monad，但转换如此微不足道，那么 a 是否不应该单独也是一个单子？当然，这不能按原样工作，因为没有类型构造函数可以定义为 Monad 实例，但是假设我们添加了一个简单的包装器，例如 data Id a = Id a。这确实是一个单子，即恒等单子。

>>= 对恒等单子有什么作用？类型签名是Id a -> (a→Id b)→ Id b，相当于a -> (a→b)→ b，这又是一个简单的函数应用。确定 Cont r a 与 Id a 基本等价后，我们也可以推断出在这种情况下，(>>=)< /code> 只是函数应用。

当然，Cont r a 是一个疯狂的颠倒世界，每个人都留着山羊胡子，因此实际发生的情况涉及以令人困惑的方式打乱事物，以便将两个挂起的计算链接在一起形成一个新的挂起计算，但本质上，实际上没有什么不寻常的事情发生！将函数应用于参数，呵呵，函数式程序员生活中的又一天。

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.

回复收藏 0 原文

秋意浓 2024-09-18 08:32:59

这是斐波那契：

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

想象一下你有一台没有调用堆栈的机器 - 它只允许尾递归。如何在那台机器上执行fib？您可以轻松地重写函数以线性而不是指数时间工作，但这需要一点点洞察力并且不是机械的。

使其成为尾递归的障碍是第三行，其中有两个递归调用。我们只能进行一次调用，并且还必须给出结果。这是延续进入的地方。

我们将让 fib (n-1) 接受附加参数，该参数将是一个函数，指定计算结果后应执行的操作，将其称为 x。当然，它会添加fib (n-2)。因此：要计算 fib n，您需要计算 fib (n-1)，之后，如果您调用结果 x，您会计算 fib (n-2)，之后，如果调用结果y，则返回x+y。

换句话说，您必须告诉：

如何进行以下计算：“fib' n c = 计算 fib n 并将 c 应用于结果“？

答案是您执行以下操作：“计算 fib (n-1) 并将 d 应用于结果”，其中 d x 表示“计算 fib (n-2) 并将 e 应用于结果”，其中 e y 表示 c (x+y)代码>.在代码中：

fib' 0 c = c 0
fib' 1 c = c 1
fib' n c = fib' (n-1) d
           where d x = fib' (n-2) e
                 where e y = c (x+y)

同样，我们可以使用 lambda：

fib' 0 = \c -> c 0
fib' 1 = \c -> c 1
fib' n = \c -> fib' (n-1) $ \x ->
               fib' (n-2) $ \y ->
               c (x+y)

要获取实际的斐波那契数，请使用标识：fib' n id。您可以认为 fib (n-1) $ ... 行将其结果 x 传递到下一行。

最后三行听起来像一个 do 块，事实上，

fib' 0 = return 0
fib' 1 = return 1
fib' n = do x <- fib' (n-1)
            y <- fib' (n-2)
            return (x+y)

根据 monad Cont 的定义，直到新类型都是相同的。注意差异。开头是 \c ->，而不是 x <- ... 而是 ... $ \x ->和 c 而不是 return。

尝试使用 CPS 以尾递归方式编写阶乘 n = n *阶乘 (n-1) 。

>>= 是如何工作的？ m >>= k 相当于

do a <- m
   t <- k a
   return t

将翻译返回，与 fib' 中的风格相同，您可以

\c -> m $ \a ->
      k a $ \t ->
      c t

简化 \t ->; c t 到 c

m >>= k = \c -> m $ \a -> k a c

添加您

m >>= k  = Cont $ \c -> runCont m $ \a -> runCont (k a) c

在此页面顶部获得的新类型。它很复杂，但如果您知道如何在 do 表示法和直接使用之间进行转换，您就不需要知道 >>= 的确切定义！如果您查看 do 块，延续 monad 会更加清晰。

Monad 和延续

如果你看看列表 monad 的这种用法......

do x <- [10, 20]
   y <- [3,5]
   return (x+y)

[10,20] >>= \x ->
  [3,5] >>= \y ->
    return (x+y)

([10,20] >>=) $ \x ->
  ([3,5] >>=) $ \y ->
    return (x+y)

它看起来像延续！事实上，当您应用一个参数时 (>>=) 的类型为 (a -> mb) -> m b 是Cont (mb) a。请参阅 sigfpe 的所有 monad 之母的解释。我认为这是一个很好的延续 monad 教程，尽管它可能不是这个意思。

由于延续和单子在两个方向上都有很强的相关性，我认为适用于单子的也适用于延续：只有努力工作才能教你它们，而不是阅读一些墨西哥卷饼隐喻或类比。

Here's fibonacci:

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

Imagine you have a machine without a call stack - it only allows tail recursion. How to execute fib on that machine? You could easily rewrite the function to work in linear, instead of exponential time, but that requires tiny bit of insight and is not mechanical.

The obstacle to making it tail recursive is the third line, where there are two recursive calls. We can only make a single call, which also has to give the result. Here's where continuations enter.

We'll make fib (n-1) take additional parameter, which will be a function specifying what should be done after computing its result, call it x. It will be adding fib (n-2) to it, of course. So: to compute fib n you compute fib (n-1) after that, if you call the result x, you compute fib (n-2), after that, if you call the result y, you return x+y.

In other words you have to tell:

How to do the following computation: "fib' n c = compute fib n and apply c to the result"?

The answer is that you do the following: "compute fib (n-1) and apply d to the result", where d x means "compute fib (n-2) and apply e to the result", where e y means c (x+y). In code:

fib' 0 c = c 0
fib' 1 c = c 1
fib' n c = fib' (n-1) d
           where d x = fib' (n-2) e
                 where e y = c (x+y)

Equivalently, we can use lambdas:

fib' 0 = \c -> c 0
fib' 1 = \c -> c 1
fib' n = \c -> fib' (n-1) $ \x ->
               fib' (n-2) $ \y ->
               c (x+y)

To get actual Fibonacci use identity: fib' n id. You can think that the line fib (n-1) $ ... passes its result x to the next one.

The last three lines smell like a do block, and in fact

fib' 0 = return 0
fib' 1 = return 1
fib' n = do x <- fib' (n-1)
            y <- fib' (n-2)
            return (x+y)

is the same, up to newtypes, by definition of monad Cont. Note differences. There's \c -> at the beginning, instead of x <- ... there's ... $ \x -> and c instead of return.

Try writing factorial n = n * factorial (n-1) in a tail recursive style using CPS.

How does >>= work? m >>= k is equivalent to

do a <- m
   t <- k a
   return t

Making the translation back, in the same style as in fib', you get

\c -> m $ \a ->
      k a $ \t ->
      c t

simplifying \t -> c t to c

m >>= k = \c -> m $ \a -> k a c

Adding newtypes you get

m >>= k  = Cont $ \c -> runCont m $ \a -> runCont (k a) c

which is on top of this page. It's complex, but if you know how to translate between do notation and direct use, you don't need to know exact definition of >>=! Continuation monad is much clearer if you look at do-blocks.

Monads and continuations

If you look at this usage of list monad...

do x <- [10, 20]
   y <- [3,5]
   return (x+y)

[10,20] >>= \x ->
  [3,5] >>= \y ->
    return (x+y)

([10,20] >>=) $ \x ->
  ([3,5] >>=) $ \y ->
    return (x+y)

that looks like continuation! In fact, (>>=) when you apply one argument has type (a -> m b) -> m b which is Cont (m b) a. See sigfpe's Mother of all monads for explanation. I'd regard that as a good continuation monad tutorial, though it wasn't probably meant as it.

Since continuations and monads are so strongly related in both directions, I think what applies to monads applies to continuations: only hard work will teach you them, and not reading some burrito metaphor or analogy.

回复收藏 0 原文

仄言 2024-09-18 08:32:59

编辑：文章已迁移到以下链接。

我写了一个直接针对这个主题的教程，希望对您有用。（这确实有助于巩固我的理解！）它有点太长了，不太适合 Stack Overflow 主题，所以我将其迁移到 Haskell Wiki。

请参阅：MonadCont 底层

回复收藏 0 原文

清晰传感 2024-09-18 08:32:59

我认为掌握 Cont monad 的最简单方法是了解如何使用它的构造函数。我现在将假设以下定义，尽管 transformers 包的实际情况略有不同：

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

这给出了：

Cont :: ((a -> r) -> r) -> Cont r a

所以要构建一个 Cont r a 类型的值，我们需要给 Cont 一个函数：

value = Cont $ \k -> ...

现在，k 本身的类型为 a ->; r，并且 lambda 的主体需要具有类型 r。显而易见的做法是将 k 应用于 a 类型的值，并获取 r 类型的值。是的，我们可以做到这一点，但这实际上只是我们可以做的众多事情之一。请记住，value 在 r 中不必是多态的，它可能是 Cont String Integer 类型或其他具体类型。因此：

我们可以将 k 应用于 a 类型的多个值，并以某种方式组合结果。
我们可以将 k 应用于 a 类型的值，观察结果，然后根据结果决定将 k 应用于其他内容。
我们可以完全忽略 k 并自己生成一个 r 类型的值。

但这一切意味着什么呢？ k 最终会是什么？好吧，在 do 块中，我们可能会有这样的东西：

flip runCont id $ do
  v <- thing1
  thing2 v
  x <- Cont $ \k -> ...
  thing3 x
  thing4

这是有趣的部分：我们可以在我们的脑海中，以某种非正式的方式，在 Cont 构造函数，并将其之后的整个计算的其余部分视为其本身的值。但等一下，它是什么取决于 x 是什么，所以它实际上是一个来自 a< 类型的值 x 的函数 /code> 到某个结果值：

restOfTheComputation x = do
  thing3 x
  thing4

事实上，这个restOfTheComputation粗略地说就是k最终的结果。换句话说，您使用一个值调用 k，该值将成为 Cont 计算的结果 x，运行其余的计算，然后作为调用 k 的结果，生成的 r 会蜿蜒回到 lambda 中。所以：

如果您多次调用 k ，其余的计算将运行多次，并且结果可以根据您的意愿进行组合。
如果您根本没有调用 k，则整个计算的其余部分将被跳过，并且封闭的 runCont 调用只会返回 类型的任何值>r 你成功地综合了。也就是说，除非计算的其他部分从他们的 k 调用你，并扰乱结果......

如果你'现在我仍然和我在一起，应该很容易看出这可能非常强大。为了阐明这一点，让我们实现一些标准类型类。

instance Functor (Cont r) where
  fmap f (Cont c) = Cont $ \k -> ...

我们得到一个 Cont 值，其绑定结果 x 类型为 a，以及一个函数 f :: a ->; b，我们想要创建一个 Cont 值，绑定结果 f x 类型为 b。好吧，要设置绑定结果，只需调用 k...

  fmap f (Cont c) = Cont $ \k -> k (f ...

等等，我们从哪里获取 x ？嗯，它将涉及到我们还没有使用过的c。请记住 c 的工作原理：它获得一个函数，然后使用其绑定结果调用该函数。我们想要调用我们的函数，并将f应用于该绑定结果。所以：

  fmap f (Cont c) = Cont $ \k -> c (\x -> k (f x))

田田！接下来，Applicative：

instance Applicative (Cont r) where
  pure x = Cont $ \k -> ...

这个很简单。我们希望绑定结果是我们得到的x。

  pure x = Cont $ \k -> k x

现在，<*>：

  Cont cf <*> Cont cx = Cont $ \k -> ...

这有点棘手，但本质上使用与 fmap 相同的思想：首先通过创建 lambda 从第一个 Cont 获取函数让它调用：

  Cont cf <*> Cont cx = Cont $ \k -> cf (\fn -> ...

然后从第二个获取值x，并使fn x成为绑定结果：

  Cont cf <*> Cont cx = Cont $ \k -> cf (\fn -> cx (\x -> k (fn x)))

Monad大致相同，尽管需要 runCont 或一个 case 或 let 来解压新类型。

这个答案已经很长了，所以我不会进入ContT（简而言之：它与Cont完全相同！唯一的区别在于类型构造函数，所有内容的实现都是相同的）或 callCC （一个有用的组合器，提供了一种忽略 k 的便捷方法，实现了从子块的提前退出）。

对于简单且合理的应用程序，请尝试 Edward Z. Yang 的博客文章实现 labelled for 循环中的break 和 continue。

I think the easiest way to get a grip on the Cont monad is to understand how to use its constructor. I'm going to assume the following definition for now, although the realities of the transformers package are slightly different:

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

This gives:

Cont :: ((a -> r) -> r) -> Cont r a

so to build a value of type Cont r a, we need to give a function to Cont:

value = Cont $ \k -> ...

Now, k itself has type a -> r, and the body of the lambda needs to have type r. An obvious thing to do would be to apply k to a value of type a, and get a value of type r. We can do that, yes, but that's really only one of many things we can do. Remember that value need not be polymorphic in r, it might be of type Cont String Integer or something else concrete. So:

We could apply k to several values of type a, and combine the results somehow.
We could apply k to a value of type a, observe the result, and then decide to apply k to something else based on that.
We could ignore k altogether and just produce a value of type r ourselves.

But what does all this mean? What does k end up being? Well, in a do-block, we might have something looking like this:

flip runCont id $ do
  v <- thing1
  thing2 v
  x <- Cont $ \k -> ...
  thing3 x
  thing4

Here's the fun part: we can, in our minds and somewhat informally, split the do-block in two at the occurrence of the Cont constructor, and think of the rest of the entire computation after it as a value in itself. But hold on, what it is depends on what x is, so it's really a function from a value x of type a to some result value:

restOfTheComputation x = do
  thing3 x
  thing4

In fact, this restOfTheComputation is roughly speaking what k ends up being. In other words, you call k with a value which becomes the result x of your Cont computation, the rest of the computation runs, and then the r produced winds its way back into your lambda as the result of the call to k. So:

if you called k multiple times, the rest of the computation will get run multiple times, and the results may be combined however you wish.
if you didn't call k at all, the rest of the entire computation will be skipped, and the enclosing runCont call will just give you back whatever value of type r you managed to synthesise. That is, unless some other part of the computation is calling you from their k, and messing about with the result...

If you're still with me at this point it should be easy to see this could be quite powerful. To make the point a little, let's implement some standard type classes.

instance Functor (Cont r) where
  fmap f (Cont c) = Cont $ \k -> ...

We're given a Cont value with bind result x of type a, and a function f :: a -> b, and we want to make a Cont value with bind result f x of type b. Well, to set the bind result, just call k...

  fmap f (Cont c) = Cont $ \k -> k (f ...

Wait, where do we get x from? Well, it's going to involve c, which we haven't used yet. Remember how c works: it gets given a function, and then calls that function with its bind result. We want to call our function with f applied to that bind result. So:

  fmap f (Cont c) = Cont $ \k -> c (\x -> k (f x))

Tada! Next up, Applicative:

instance Applicative (Cont r) where
  pure x = Cont $ \k -> ...

This one's simple. We want the bind result to be the x we get.

  pure x = Cont $ \k -> k x

Now, <*>:

  Cont cf <*> Cont cx = Cont $ \k -> ...

This a little trickier, but uses essentially the same ideas as in fmap: first get the function from the first Cont, by making a lambda for it to call:

  Cont cf <*> Cont cx = Cont $ \k -> cf (\fn -> ...

Then get the value x from the second, and make fn x the bind result:

  Cont cf <*> Cont cx = Cont $ \k -> cf (\fn -> cx (\x -> k (fn x)))

Monad is much the same, although requires runCont or a case or let to unpack the newtype.

This answer is already quite long, so I won't go into ContT (in short: it is exactly the same as Cont! The only difference is in the kind of the type constructor, the implementations of everything are identical) or callCC (a useful combinator that provides a convenient way to ignore k, implementing early exit from a sub-block).

For a simple and plausible application, try Edward Z. Yang's blog post implementing labelled break and continue in for loops.

回复收藏 0 原文

~没有更多了~