【译】 Continuation Monad · berberman's Blog

原文：
Gabriel Gonzalez, Sunday, December 30, 2012, Haskell for all
~~入门级文章~~ 可能算不上

续体单子是最不受欢迎的单子之一，在这篇文章中我希望能够鼓励大家去使用它。文章会从续体的整体概念和作为单子具有的特性来展开。

续体

Haskell 续体具有以下类型：

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

一个续体会接收一个 (a -> r) 的函数，并生成 r（可能是固定的值，像 Int 或 IO ()）。

举个例子，我可能会编写一个长时间运行的程序，每当用户输入一行输入时就会产生一个动作：

onInput :: (String -> IO ()) -> IO ()
        -- 即 Cont (IO ()) String
onInput f = forever $ do
    str <- getLine
    f str

如果你曾经使用过涉及回调的框架，你会对这种写法感到熟悉。我们提供给框架一个函数（或者说一个续体），框架会使用这个函数来完成它的工作。

“稍后完成我”

在使用续体编写程序时，通常会交给别人来完成它。常见原因包括：

你正在编程框架使用了用户提供的回调
你正在为游戏玩家定义一个供他们定制的地图引擎
你很懒

我将使用下面假设的代码段作为例子：

unitAttack :: Target -> IO ()
unitAttack target = do
    swingAxeBack 60
    valid <- isTargetValid target
    if valid
    then ??? target
    else sayUhOh

假设你必须打包并编译这段代码，供其他人（比如说你的同事）以后使用，但是它还不能编译，因为你还有未确定的 ??? 函数。你会怎么办？

像所有好的程序一样，最好的解决方案是最懒惰的。我们将不完整的行为作为一个参数，以便稍后完成函数的人可以通过将特定的行为传入来完成函数：

unitAttack :: Target -> (Target -> IO ()) -> IO ()
unitAttack target todo = do
    swingAxeBack 60
    valid <- isTargetValid target
    if valid
    then todo target
    else sayUhOh

问题解决！注意，右手边的类型签名和我们的 Cont 类型非常相似。我们可以把它包装进 Cont：

unitAttack :: Target -> Cont (IO ()) Target
unitAttack target = Cont $ \todo -> do
    swingAxeBack 60
    valid <- isTargetValid target
    if valid
    then todo target
    else sayUhOh

……或者，更好的是，我们可以使用 ContT 来替代。它的好处在于它是一个单子变换器，可以更加方便。ContT 和 Cont 具有相同的 Monad 实例，所以它们可以相互替换：

newtype ContT r m a = ContT { runContT :: (a -> m r) -> m r }

unitAttack :: Target -> ContT () IO Target
unitAttack target = ContT $ \todo -> do
    swingAxeBack 60
    valid <- isTargetValid target
    if valid
    then todo target
    else sayUhOh

这非常妙，因为现在其他人可以从我们停下的地方延续了（因此得名：续体）。他们只需定义出缺少的函数：

1	damageTarget :: Target -> IO ()

并把它提供给我们的续体去完成。

可变参数

当我们的函数中仅有一个洞时这个策略十分有效，但如果我们的函数中有两个洞，并且他们需要不同的参数呢？

unitAttack :: Target -> IO ()
unitAttack target = do
    ???_1 60
    valid <- isTargetValid target
    if valid
    then ???_2 target
    else sayUhOh

好吧，我们可以试着接受两个续体：

unitAttack
 :: Target -> (Int -> IO ()) -> (Target -> IO ()) -> IO ()
unitAttack target todo1 todo2 = do
    todo1 60
    valid <- isTargetValid target
    if valid
    then todo2 target
    else sayUhOh

……不过这就不再完好地适合我们的 Cont 类型了，它只需一个续体。

幸运的是，有一个清爽并且通用的解决方案。只需定义一个数据类型，将两种可能的参数使用和类型包装起来，并定义一个接收这个和类型的续体：

data Hole = Swing Int | Attack Target

unitAttack :: Target -> ContT () IO Hole
unitAttack target = ContT $ \k -> do
    k (Swing 60)
    valid <- isTargetValid target
    if valid
    then k (Attack target)
    else sayUhOh

每个构造子像是一个占位符，告诉续体正在填的是哪个洞。然后其他人可以从我们停止的地方延续，只需写：

damage    :: Target -> IO ()
swingBack :: Int -> IO ()

continue :: Hole -> IO ()
continue (Swing  n) = swingBack n
continue (Attack t) = damage t

runContT (unitAttack target) continue :: IO ()

这个技巧可以推广到 n 个洞，每个洞都有可变参数。只需定义有 n 个构造子的类型，让每个洞都有一个构造子，并在构造子中储存特定续体所需的参数：

1	data Hole = Hole1 Arg1 Arg2 \| Hole2 \| Hole3 Arg3 \| Hole4

代数数据类型

歪个题，我想稍微说说代数数据类型。如果你不感兴趣的话，可以跳到下一节。事实证明，我们可以很好地推导出上述应用在多个洞的技巧。类型代数告诉我们，可以把下面的类型构造子转换成代数运算符，并从简单的代数操作中得到等价的类型：

1
2
3

Either a b  <=>  a + b
(a, b)      <=>  a * b
a -> b      <=>  b ^ a

这意味着如果我们有一个带着两个续体的函数：

1	(a1 -> r) -> ((a2 -> r) -> r)

……我们可以把它翻译成等价的代数表达式：

1	(r ^ (r ^ a2)) ^ (r ^ a1)

……之后使用代数运算法则得到等价的表示：

1
2
3

  (r ^ (r ^ a2)) ^ (r ^ a1)
= r ^ ((r ^ a2) * (r ^ a1))
= r ^ (r ^ (a2 + a1))

……再把它换回等价的类型，可得：

1	(Either a2 a1 -> r) -> r

……这正是在前一节中我们所说的技巧。

相似地，如果我们有一个多参数的续体：

1	(a -> b -> r) -> r

……我们可以使用类型代数运算得到等价的单参形式：

1 2	r ^ ((r ^ a) ^ b) = r ^ (r ^ (a * b))

……转回去就是：

1	((a, b) -> r) -> r

续体单子

目前为止，我们已经解释了续体的用途，但还没解释单子的。

我坚信通往 Monad 的核心是理解 Kleisli 箭头，如果你想研究单子的目的或者动机，你需要先搞清楚 Kleisli 箭头干了什么。

与其研究 Cont 的 Monad 实例，不如先看看 Cont 上的 Kleisli 箭头长什么样，并从类型层面推断一下它的作用：

1
2
3

  a -> Cont r b
~ a -> (b -> r) -> r    -- 展开 Cont 的定义
~ (b -> r) -> (a -> r)  -- 翻转参数

换句话说，我们拿到一个处理 a 的函数并将它变换为处理 b 的。

这表明了续体单子的一个最初的基本直觉：我们在变换处理器（Handler）。

让我们回顾一下之前的例子来建立这种直觉：

unitAttack :: Target -> ContT () IO Target
unitAttack target = ContT $ \todo -> do
    swingBack 60
    valid <- isTargetValid target
    if valid
    then todo target
    else sayUhOh

我们需要的完成函数的类型为：

1	handler :: Target -> IO ()

我们可以完成这个函数 …… 或者中途放弃：

halfAssedCompletion :: Target -> IO ()
halfAssedCompletion target = do
    registerUnitBeingAttacked
    playDamageSound
    ??? 40  -- 快接近了……

这意味着本质上我们创建了一个新的延续，带着稍微小一点的洞：

halfAssedCompletion :: Target -> ContT () IO Int
halfAssedCompletion target = ContT $ \todo -> do
    registerUnitBeingAttacked
    playDamageSound
    todo 40

这就是一个 Kleisli 箭头！这也意味着我们可以用它和上一个 Kleisli 箭头组合：

1	unitAttack >=> halfAssedCompletion :: Target -> ContT () IO Int

这个组合把 unitAttack 函数代入了我们在 halfAssedCompletion 中留下的每个洞。然而，halfAssedCompletion 留下了更小的 Int 洞，其他人现在需要完成它。

注意，我们原来需要的处理器类型为：

1	handler :: Target -> IO ()

……但现在，我们只需更小的：

1	newHandler :: Int -> IO ()

……换句话说，halfAssedCompletion 作为一个中间者，将 (Int -> IO ()) 类型的处理器变换为 (Target -> IO ())。

Cont 单子就是把这些各种部分完成的操作串在一起，直到所有的洞在最后都被填上。你可以使用这个抽象分阶段地完成一个项目，并在完成项目前维护者变更时能够无缝将工作交给另一个人。或者，你可以使用它将一个框架的回调 API 压缩至单个入口点。

Kleisli 范畴

先前我说过单子的核心是它的 Kleisli 箭头。原因在于 Kleisli 箭头是 Kleisli 范畴中的态射，其中 (>=>) 是 Kleisli 箭头的组合：

1 2	(>=>) :: (Monad m) => (a -> m b) -> (b -> m c) -> (a -> m c) (f >=> g) x = f x >>= g

…… return 是单位元：

1	return :: (Monad m) => a -> m a

如同所有范畴，Kleisli 范畴同样必须遵守范畴定律：

return >=> f = f                   -- 左单位元

f >=> return = f                   -- 右单位元

(f >=> g) >=> h = f >=> (g >=> h)  -- 结合律

遵守这些定律带来了很好的性质。举个例子，它保证你可以独立推导出在组合链中的每一个 Kleisli 箭头。每个 Kleisli 箭头的行为完全取决于它的输入（域）和输出（陪域）。那么让我们来想想模块化是如何转化为 Cont Kleisli 范畴的。

当变更维护者时，你不需要像这样给下一个维护者一堆遍布大量代码的洞：

largeProgram = do
    ...
    x <- ???_1 y
    ...
    ???_2 horseTheyRodeInOn
    ...
    spawn ???_29 foo

取而代之的是，你可以使用一个回调来统一所有的洞，这个回调接收单个类型（陪域）：

largeProgram :: () -> ContT () IO Hole
largeProgram () = ContT $ \k -> do
    ...
    x <- k (Hole1 y)
    ...
    k Hole2
    ...
    k (Hole29 spawn foo)

这给下一个人一个单入口点去延续，因为他们现在只需要写一个 Kleisli 箭头来处理 Hole，其中包括以前所有的洞：

nextContribution :: Hole -> ContT () IO NextHole
nextContribution currHole = ConT $ \nextHole -> case currHole of
    Hole1 y -> ... -- 填第一个洞
    Hole2   -> ... -- 填第二个洞
    ...
    Hole29 spawn foo -> ... -- 填第二十九个洞

然后只需使用 Kleisli 组合连接你的代码贡献：

1	largeProgram >=> nextContribution

这清晰地模块化了第一个人的贡献，后续的贡献也可以被分隔开来。通过重复这个过程，每个后续的代码贡献保持模块化，成为可组合的 Kleisli 箭头，和其他贡献清楚地分开：

alice'sWork :: a -> ContT r m b 
bob'sWork   :: b -> ContT r m c
carlo'sWork :: c -> ContT r m d 

engine = alice'sWork >=> bob'sWork >=> carlo'sWork :: a -> ContT r m d

customMap :: d -> ContT r m e

completeGame = engine >=> customMap :: a -> ContT r m e

这就是为什么框架和游戏自定义地图制作者使用续体来作为公司代码和用户代码之间接口，分隔代码。续体单子可以建立严密的代码边界，包括在项目内部以及面向用户的外部 API。在把贡献代码分隔成 Kleisli 箭头的同时也分隔了每部分的职责。

回调地狱

框架是分离职责的典型例子，其中框架作者提供了一些代码，但是用户需要用自己的回调来填补空白。这通常会导致在使用一些框架时出现回调地狱，Node.js 就是其中将该原则发挥极致的一个。

但是并非一定如此。续体单子告诉我们一个遍布回调的庞大 API 总是可以压缩成一个单回调单参数的。更好的是，我们得到了用于组合多层回调的单子语法糖。

我会用 GLUT 作为一个例子，它需要一些像这样的回调：

type ReshapeCallback = Size -> IO ()

type VisibilityCallback = Visibility -> IO ()

type WindowStateCallback = WindowState -> IO ()

type CloseCallback = IO ()

-- 还有好多，但先止步于此

相反地是，我们可以把 GLUT 的多个回调包装进一个规范的 ConT API：

glut :: () -> ContT () IO Hole

data Hole
   = Reshape Size
   | Visible Visibility
   | Window WindowState
   | Close
   ...

现在末端用户仅有单个 GLUT 单子的入口点，因此他们只需在单个函数中完成框架：

userCallbacks :: Hole -> ContT () IO a
userCallbacks hole = ContT $ \_ -> case hole of
    Reshape size -> ... -- 重塑形状回调
    Visibility v -> ... -- 可见性改变回调
    Window ws    -> ... -- 窗口状态改变回调
    Close        -> ... -- 窗口关闭回调
    ...

此外，他们现在可以将代码组合到 glut 框架：

1	glut >=> userCallbacks :: () -> ContT () IO a

止步于此

我们如何知道续体已经完成，并且没有后续了呢？让我们看看在没有更多的洞，并且不使用续体的情况下编译器推出的类型：

1
2
3

>>> let done = ContT $ \_ -> return ()
>>> :t done
done :: Monad m => ContT () m a

返回类型是多态的，意味着没有留下未填的洞了。上述函数只是在所有洞里填上了 return ()。我们也可以证明如果最终返回结果的类型是 Void，空类型，续体链也是完成的：

absurd :: Void -> a  -- 来自 "void" 包

run :: (Monad m) => ContT r m Void -> m r
run c = runContT c absurd

run 只接收完成，没有洞的程序。我们可以在上个 GLUT 例子中使用 run，因为最终的用户回调处理器没有留下未完成的洞：

1	run ((glut >=> userCallbacks) ()) :: IO ()

总结

我希望这篇文章能够激励人们去使用续体单子来构造和模块化代码完成的边界。续体单子在程序员尝试把一个回调地狱抽象成简单、统一、单个入口的干净接口时很自然地出现。

berberman's Blog

续体