Continuation Monad

啊啊啊啊Github连击又断掉了！好的那么我们今天来谈Continuation Monad（哭丧脸。

Continuation Monad 长什么样子？大概像这样：

1
2
3
4
5
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

那么Continuation究竟是一个什么概念？一般来说，Continuation表示的是“剩下的计算”的概念。熟悉命令式语言的读者可能对此没有什么概念，不过在命令式的世界里这件事可以粗略的表示为“分号后面的部分”。举个例子来说，假设我们这样一个表达式foo (bar x y) z，观察括号里面的部分，(bar x y)求值之后，需要应用到foo _ z。写成合法的表达式就是\a -> foo a z，这也就是“剩下的计算”的语义。这样，我们就可以通过把bar x y应用到\a -> foo a z来重新构建原来的形式。

不过这样看起来实在不太雅观，我们能不能把它变的好看一点呢？不如试试把外面的放到里面，把里面的放到外面？这样我们就有了\k -> k (bar a b)。这里k表示剩余的计算。

这样表示起来我们就获得了很好的灵活性。看看原来的表达式foo (bar a b) z，我们不仅仅把bar a b从上下文中提取了出来，而且还能在这个subexpression中操作外面的上下文！等等这个是不是听起来很耳熟？仿佛已经闻到了一股清新的Monad的气味！

不妨把这个想象成一种挂起的计算，并且我们能够显式地控制接下来将要发生什么。那么，我们要怎么推广到一般情况呢？观察到内部的subexpression并没有变化，不妨把它作为参数，得到\x k -> k x。呃…这不就是单纯的flip ($)吗！看起来，Continuation本质上并没有比函数应用多出什么东西。

那么作为一个Haskell程序员，我们这个时候肯定会思考这个东西，本质上是在一些上下文上面构建计算，这是个Monad吧？嗯没错，它的确是Monad。为了使它成为Monad，我们从两个基本的概念开始构建：

  • 对于Monad m，类型m a代表在这个Monad上下文当中的a类型
  • 我们挂起的计算本质上是颠倒顺序的函数应用

那么这个Monad的上下文是什么？对于x :: a来说，这仅仅意味着我们对它应用flip ($)。$的类型签名为(a -> b) -> a -> b，flip ($)的类型则是简单的a -> (a -> b) -> b。噢，看起来已经有点像Cont的形式了！正如一个continuation代表着“未来的”某种计算，类型a自然就代表着某种意义上的“过去”。把(a -> b) -> b替换成Cont b a，我们就得到了return的类型a -> Cont b a！

所以一个Cont r a究竟意味着什么？不过是一个等待着接受一个函数a -> r，并把它应用到a类型的函数罢了。实际上，如果给一个id函数进去，Cont r a和a完全是等价的！在这种语义下，>>=该怎么实现呢？

回想一下Continuation的语义，我们所做的只不过是定义了一个函数，这里就叫做|>吧，这个函数所做的唯一的事情就是将它的第一个参数应用到第二个参数上。

1
2
(|>) :: a -> (a -> r) -> r
x |> f = f x

我们再来观察一下>>=的类型：(>>=) :: Cont r a -> (a -> Cont r b) -> Cont r b，展开类型之后即(>>=) :: (a -> r) -> r -> (a -> (b -> r) -> r) -> (b -> r) -> r。注意到返回类型应该是(b -> r) -> r，我们应该能够很自然的写出

1
(x |>) >>= (|>) = \f -> x |> (\b -> b |> f)

现在一切都很显然了，我们所做的不过是一连串的函数应用而已。把|>翻译为runCont c f，我们就得到了前面看到的m >>= k = \f -> runCont m (\b -> runCont (k b) f)。不怎么好理解是不是？人肉展开一下可以知道，我们实际上就是构造了这样一大串无用的表达式\f -> x |> (\a -> a |> (\b -> b |> ........ (\z -> z |> f))))。对，没错，你已经得到了Continuation Monad。是不是有一种上当的感觉？绕了这么大一个圈子最后只是把一个好好的f x变成了一大串无用的lambda表达式？别着急，就连最“无用”的id都能起到很大的作用，在下一篇文章里我们就介绍Continuation Monad的应用：Coroutine。