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

这是斐波那契:

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 block ，事实上

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 .

试试写 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，继续单子(monad)会更清楚。

单子(monad)和延续

如果你看一下 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 的 Mother of all monads解释。我认为这是一个很好的 continuation monad 教程，尽管它可能并不意味着它。

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