haskell - Haskell Cont monad 如何以及为什么工作？

Question

这就是 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

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

Answer 1

关于 continuation monad，首先要意识到的是，从根本上说，它根本没有真正做任何事情。这是真的！

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

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

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

现在，将表达式的每一个片段都翻译成这种形式会很简单，尽管很乏味而且非常令人困惑。幸运的是，有更好的方法。作为 Haskell 程序员，当我们考虑在后台上下文中构建计算时，我们认为接下来会说，这是一个 monad 吗？在这种情况下，答案是肯定的，是的。

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

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

在这种情况下可以访问某种类型的东西意味着什么a？这只是意味着，对于某些值x :: a，我们已经应用flip ($)到x，给了我们一个函数，该函数接受一个接受类型参数的函数a，并将该函数应用于x. 假设我们有一个挂起的计算持有一个 type 的值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 -> Cont b a...相同的类型签名return，事实上，这正是它的本质。

从现在开始，几乎所有内容都直接从类型中分离出来：>>=除了实际实现之外，基本上没有明智的实现方式。但它实际上在做什么？

在这一点上，我们回到我最初所说的：continuation monad 并没有真正做任何事情。简单地通过将作为参数提供给挂起的计算来Cont r a简单地等价于type的某些东西。这可能会导致人们问，如果是一个 monad 但转换是如此微不足道，那么是否不应该单独也是一个 monad？当然这不能按原样工作，因为没有类型构造函数可以定义为实例，但是假设我们添加了一个简单的包装器，比如. 这确实是一个单子，即身份单子。aidCont r aaMonaddata Id a = Id a

身份单子有什么作用>>=？类型签名是Id a -> (a -> Id b) -> Id b，相当于a -> (a -> b) -> b，又是简单的函数应用。确定了 与Cont r a的简单等价后Id a，我们可以推断在这种情况下，(>>=)也只是函数应用程序。

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

Answer 2

这是斐波那契：

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)，如果调用 result x，则计算fib (n-2)，然后，如果调用 result 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。注意差异。There's\c ->在开头，而不是x <- ...there's... $ \x ->和c而不是return.

尝试factorial n = n * factorial (n-1)使用 CPS 以尾递归风格编写。

如何>>=工作？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-blocks，继续单子会更清楚。

单子和延续

如果你看一下 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)

看起来像继续！实际上，(>>=)当您应用一个参数时，其类型(a -> m b) -> m b为Cont (m b) a. 有关解释，请参阅 sigfpe 的所有单子之母。我认为这是一个很好的 continuation monad 教程，尽管它可能并不意味着它。

由于 continuation 和 monad 在两个方向上都密切相关，我认为适用于 monad 的东西也适用于 continuation：只有努力工作才能教会你它们，而不是阅读一些墨西哥卷饼的隐喻或类比。

Answer 3

编辑：文章迁移到下面的链接。

我已经写了一个直接解决这个主题的教程，我希望你会觉得有用。（它确实有助于巩固我的理解！）它有点太长了，无法舒适地融入 Stack Overflow 主题，所以我将它迁移到了 Haskell Wiki。

请参阅：引擎盖下的 MonadCont

Answer 4

我认为掌握Contmonad 的最简单方法是了解如何使用它的构造函数。我现在将假设以下定义，尽管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它本身有 type a -> r，而 lambda 的主体也需要有 type r。一个显而易见的事情是应用k一个类型的值a，并获得一个类型的值r。我们可以做到这一点，是的，但这只是我们可以做的许多事情之一。请记住，在 中value不必是多态的r，它可能是类型Cont String Integer或其他具体的东西。所以：

• 我们可以应用于ktype 的多个值a，并以某种方式组合结果。
• 我们可以应用k到 type 的值a，观察结果，然后k根据它决定应用到其他东西。
• 我们可以完全忽略k，只自己产生一个类型的值r。

但这一切意味着什么？k最终成为什么？好吧，在一个 do-block 中，我们可能会有这样的东西：

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

这是有趣的部分：在我们的脑海中，有些非正式地，我们可以在构造函数出现时将 do-block 一分为二，并将其之后Cont的整个计算的其余部分视为其本身的值。但是等等，它是什么取决于它是什么，所以它实际上是一个从类型值到某个结果值的函数：xxa

restOfTheComputation x = do
  thing3 x
  thing4

事实上，粗略地说，这restOfTheComputation就是最终的结果。换句话说，您调用一个值，该值成为您的计算结果，其余的计算运行，然后生成的作为调用的结果返回到您的 lambda 。所以：kkxContrk

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

如果您此时仍在我身边，应该很容易看出这可能非常强大。为了说明一点，让我们实现一些标准类型类。

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

我们得到了一个Cont绑定结果x为 type的值a和一个函数f :: a -> b，我们想要创建一个Cont绑定结果f x为 type的值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 中基本相同的想法：首先从 first 获取函数Cont，方法是制作一个 lambda 供它调用：

  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或案例或让解包新类型。

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

对于一个简单且合理的应用程序，请尝试 Edward Z. Yang 的博客文章实现标记的 break 并在 for 循环中继续。

Answer 5

试图补充其他答案：

嵌套 lambda 的可读性很差。这正是 let... in... 和 ... where ... 存在的原因，通过使用中间变量来摆脱嵌套的 lambda。使用这些，绑定实现可以重构为：

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

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

这有望使正在发生的事情更加清晰。带有延迟应用的返回实现框值。使用 runCont id 将 id 应用于装箱值，返回原始值。

对于任何可以简单地拆箱任何装箱值的 monad，通常有一个简单的 bind 实现，即简单地拆箱值并对其应用 monadic 函数。

要获得原始问题中的混淆实现，首先将 ka 替换为 Cont $ runCont (ka) ，然后可以将其替换为 Cont $ \c-> runCont (ka) c

现在，我们可以将 where 移动到子表达式中，这样我们就剩下

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

括号内的表达式可以脱糖为 \a -> runCont (ka) c $ runCont m id。

最后，我们使用 runCont 的属性 f ( runCont mg) = runCont m (fg)，我们回到原来的混淆表达式。