第 20 章：程序员定义的单子（Monads: Programmer's Definition）
原文：Bartosz Milewski, Category Theory for Programmers, Scala Edition, Chapter 20. 原书 PDF、
.tex源文件及相关图像采用 CC BY-SA 4.0；本译文按同一许可发布。
程序员围绕单子发展出了一整套神话。它据说是编程中最抽象、最困难的概念之一。有些人“懂了”，有些人不懂。对许多人来说，理解单子概念的那一刻就像神秘体验。单子抽象了如此多不同构造的本质，以至于我们在日常生活中找不到很好的类比。我们只能像摸象的盲人一样在黑暗中摸索，摸到不同部位后得意地喊：“它是一根绳子”、“它是一截树干”或者“它是一卷卷饼！”
让我先澄清事实：围绕单子的神秘主义，全都来自误解。单子是一个非常简单的概念。造成困惑的是单子应用的多样性。
为这篇文章做准备时，我查了一下 duct tape（又称 duck tape）及其应用。下面只是你可以用它做的一小部分事情：
- 密封管道
- 修复 Apollo 13 上的二氧化碳 scrubber
- 治疗疣
- 修复 Apple iPhone 4 掉话问题
- 制作舞会礼服
- 建造悬索桥
现在想象一下，你不知道 duct tape 是什么，却试图只根据这个列表搞清楚它。祝你好运！
所以我想给“单子就像……”这类陈词滥调再添一条：单子就像 duct tape。它的应用极其多样，但原理非常简单：它把东西粘在一起。更准确地说，它组合东西。
这部分解释了很多程序员，尤其是来自命令式背景的程序员，在理解单子时遇到的困难。问题在于，我们不习惯用函数组合来思考编程。这可以理解。我们经常给中间值命名，而不是把它们直接从一个函数传给另一个函数。我们也会内联短小的胶水代码，而不是把它们抽象成辅助函数。下面是 C 中命令式风格的向量长度函数实现：
double vlen(double * v) {
double d = 0.0;
int n;
for (n = 0; n < 3; ++n)
d += v[n] * v[n];
return sqrt(d);
}
把它与下面这个（风格化的）Haskell 版本比较，后者显式表现了函数组合：
vlen = sqrt . sum . fmap (flip (^) 2)
def fmap[A, B]: (A => B) => List[A] => List[B] =
f => {
case Nil => Nil
case x :: xs => f(x) :: fmap[A, B](f)(xs)
}
def sum: List[Double] => Double = _.sum
import math._
def vlen: List[Double] => Double =
sqrt _ compose sum compose fmap(pow(_, 2))
（这里，为了让事情更晦涩，我对指数运算符 (^) 做了部分应用，把它的第二个参数设为 2。）
我并不是说 Haskell 的 point-free 风格总是更好，而是说函数组合位于我们编程中所做一切的底层。尽管我们实际上在组合函数，Haskell 仍费了很大力气提供一种命令式风格语法，称为 do 记法，用于单子组合。稍后会看到它的用法。但首先，让我解释为什么一开始就需要单子组合。
20.1 Kleisli 范畴（The Kleisli Category）
我们之前通过修饰普通函数得到了 writer 单子。具体的修饰方式是把返回值与字符串，或者更一般地，与幺半群元素配对。现在可以认识到，这样的修饰是一个函子：
newtype Writer w a = Writer (a, w)
instance Functor (Writer w) where
fmap f (Writer (a, w)) = Writer (f a, w)
case class Writer[W, A](run: (A, W))
implicit def writerFunctor[W] = new Functor[Writer[W, ?]] {
def fmap[A, B](f: A => B)(fa: Writer[W, A]): Writer[W, B] =
fa match {
case Writer((a, w)) => Writer(f(a), w)
}
}
随后，我们找到了一种组合被修饰函数，也就是 Kleisli 箭头的方式。这类函数形式如下：
a -> Writer w b
A => Writer[W, B]
正是在组合内部，我们实现了日志的累积。
现在可以给出 Kleisli 范畴的更一般定义。我们从范畴 $C$ 和自函子 $m$ 开始。对应的 Kleisli 范畴 $K$ 与 $C$ 拥有相同对象，但它的态射不同。$K$ 中两个对象 $a$ 和 $b$ 之间的态射，在原始范畴 $C$ 中实现为一个态射：
a -> m b
重要的是要记住，我们把 $K$ 中的 Kleisli 箭头看作 $a$ 和 $b$ 之间的态射，而不是 $a$ 和 $m b$ 之间的态射。
在我们的例子中，$m$ 被特化为某个固定幺半群 w 上的 Writer w。
只有当我们能为 Kleisli 箭头定义合适组合时，它们才形成一个范畴。如果存在一个满足结合律，并且每个对象都有恒等箭头的组合，那么函子 $m$ 称为单子，得到的范畴称为 Kleisli 范畴。
在 Haskell 中，Kleisli 组合用鱼操作符 >=> 定义，恒等箭头是称为 return 的多态函数。下面是使用 Kleisli 组合给出的单子定义：
class Monad m where
(>=>) :: (a -> m b) -> (b -> m c) -> (a -> m c)
return :: a -> m a
trait Monad[M[_]] {
def >=>[A, B, C](m1: A => M[B], m2: B => M[C]): A => M[C]
def pure[A](a: A): M[A]
}
请记住，定义单子有许多等价方式，而这并不是 Haskell 生态中的主要定义。我喜欢它，是因为它概念上简单，并提供了很好的直觉；但编程时还有其他更方便的定义。我们马上就会谈到它们。
在这种表述中，单子律非常容易表达。它们不能在 Haskell 中被强制执行，但可以用于等式推理。它们只是 Kleisli 范畴中的标准组合律：
(f >=> g) >=> h = f >=> (g >=> h) -- associativity
return >=> f = f -- left unit
f >=> return = f -- right unit
这种定义也表达了单子真正是什么：它是一种组合被修饰函数的方式。它无关副作用或状态。它关乎组合。稍后会看到，被修饰函数可以用于表达各种效果或状态，但这不是单子的目的。单子是把一个被修饰函数的一端和另一个被修饰函数的一端粘起来的 duct tape。
回到 Writer 例子：日志函数（Writer 函子的 Kleisli 箭头）形成一个范畴，因为 Writer 是单子：
instance Monoid w => Monad (Writer w) where
f >=> g = \a ->
let Writer (b, s) = f a
Writer (c, s') = g b
in Writer (c, s `mappend` s')
return a = Writer (a, mempty)
implicit def writerMonad[W: Monoid] = new Functor[Writer[W, ?]] {
def >=>[A, B, C](f: A => Writer[W, B], g: B => Writer[W, C]) =
a => {
val Writer((b, s1)) = f(a)
val Writer((c, s2)) = g(b)
Writer((c, Monoid[W].combine(s1, s2)))
}
def pure[A](a: A) =
Writer(a, Monoid[W].empty)
}
object kleisliSyntax {
// 允许把 >=> 当作中缀操作符使用
implicit class MonadOps[M[_], A, B](m1: A => M[B]) {
def >=>[C](m2: B => M[C])(implicit m: Monad[M]): A => M[C] = {
m.>=>(m1, m2)
}
}
}
只要 w 的幺半群律成立，Writer w 的单子律就成立（它们同样不能在 Haskell 中被强制执行）。
Writer 单子有一个很有用的 Kleisli 箭头，称为 tell。它唯一的目的就是把自己的参数加入日志：
tell :: w -> Writer w ()
tell s = Writer ((), s)
def tell[W](s: W): Writer[W, Unit] =
Writer((), s)
稍后会把它当作其他单子函数的构件。
20.2 鱼的解剖（Fish Anatomy）
为不同单子实现鱼操作符时，你很快会意识到，许多代码是重复的，并且可以轻松抽取出来。首先，两个函数的 Kleisli 组合必须返回一个函数，因此它的实现完全可以从一个接受类型为 a 的参数的 lambda 开始：
(>=>) :: (a -> m b) -> (b -> m c) -> (a -> m c)
f >=> g = \a -> ...
def >=>[A, B, C](f: A => M[B], g: B => M[C]) =
a => {...}
我们唯一能对这个参数做的事，就是把它传给 f：
f >=> g = \a -> let mb = f a
in ...
def >=>[A, B, C](f: A => M[B], g: B => M[C]) =
a => {
val mb = f(a)
...
}
此时，我们手里有一个类型为 m b 的对象，以及一个函数 g :: b -> m c，需要产生类型为 m c 的结果。让我们定义一个函数来完成这件事。这个函数称为 bind，通常写作中缀操作符：
(>>=) :: m a -> (a -> m b) -> m b
def flatMap[A, B](ma: M[A])(f: A => M[B]): M[B]
对于每个单子，我们不必定义鱼操作符，而可以改为定义 bind。事实上，Haskell 中单子的标准定义使用的就是 bind：
class Monad m where
(>>=) :: m a -> (a -> m b) -> m b
return :: a -> m a
trait Monad[M[_]] {
def flatMap[A, B](ma: M[A])(f: A => M[B]): M[B]
def pure[A](a: A): M[A]
}
下面是 Writer 单子的 bind 定义：
(Writer (a, w)) >>= f =
let Writer (b, w') = f a
in Writer (b, w `mappend` w')
object bindSyntax {
// 允许把 flatMap 当作中缀操作符使用
implicit class MonadOps[A, B, W: Monoid](wa: Writer[W, A]) {
def flatMap(f: A => Writer[W, B]): Writer[W, B] = wa match {
case Writer((a, w1)) =>
val Writer((b, w2)) = f(a)
Writer(b, Monoid[W].combine(w1, w2))
}
}
}
它确实比鱼操作符的定义短。
利用 m 是函子这一事实，还可以进一步拆解 bind。可以用 fmap 把函数 a -> m b 应用到 m a 的内容上。这会把 a 变成 m b。因此，应用的结果类型是 m (m b)。这还不是我们想要的，我们需要类型为 m b 的结果，但已经很接近了。我们只需要一个函数来折叠或压平 m 的双重应用。这样的函数称为 join：
join :: m (m a) -> m a
def flatten[A](mma: M[M[A]]): M[A]
使用 join，可以把 bind 重写为：
ma >>= f = join (fmap f ma)
def flatMap[A, B](ma: M[A])(f: A => M[B]): M[B] =
flatten(fmap(f)(ma))
这导向第三种定义单子的选择：
class Functor m => Monad m where
join :: m (m a) -> m a
return :: a -> m a
trait Monad[M[_]] extends Functor[M] {
def flatten[A](mma: M[M[A]]): M[A]
def pure[A](a: A): M[A]
}
这里我们显式要求 m 是 Functor。在前两个单子定义中并不需要这样做。这是因为任何支持鱼操作符或 bind 操作符的类型构造器 m，都会自动成为函子。例如，可以用 bind 和 return 定义 fmap：
fmap f ma = ma >>= \a -> return (f a)
def fmap[A, B](f: A => B)(ma: M[A]): M[B] =
flatMap(ma)(a => pure(f(a)))
为完整起见，下面是 Writer 单子的 join：
join :: Monoid w => Writer w (Writer w a) -> Writer w a
join (Writer ((Writer (a, w')), w)) = Writer (a, w `mappend` w')
def flatten[A, W: Monoid](wwa: Writer[W, Writer[W, A]]): Writer[W, A] =
wwa match {
case Writer((Writer((a, w2)), w1)) =>
Writer(a, Monoid[W].combine(w1, w2))
}
20.3 do 记法（The do Notation）
一种使用单子写代码的方式是直接处理 Kleisli 箭头，并用鱼操作符组合它们。这种编程模式是 point-free 风格的推广。Point-free 代码紧凑，而且常常相当优雅。不过一般来说，它可能很难理解，甚至接近晦涩。这就是为什么大多数程序员更喜欢给函数参数和中间值命名。
处理单子时，这意味着相比鱼操作符，更偏好 bind 操作符。Bind 接受一个单子值并返回一个单子值。程序员可以选择给这些值命名。但这很难说是改进。我们真正想要的是假装自己正在处理普通值，而不是封装它们的单子容器。命令式代码就是这样工作的，副作用，比如更新全局日志，大多被隐藏在视野之外。而这正是 Haskell 中 do 记法模拟的东西。
你可能会疑惑，既然如此，为什么还要使用单子？如果我们想让副作用不可见，为什么不坚持使用命令式语言？答案是，单子给了我们对副作用更好的控制。例如，Writer 单子中的日志从函数传到函数，并且从不作为全局变量暴露。不存在弄乱日志或制造数据竞争的可能。此外，单子代码被清楚地标记出来，并与程序其余部分隔离。
do 记法只是单子组合的语法糖。表面上看，它很像命令式代码，但会直接翻译成一连串 bind 和 lambda 表达式。
例如，取我们之前用来说明 Writer 单子中 Kleisli 箭头组合的例子。按照当前定义，它可以重写为：
process :: String -> Writer String [String]
process = upCase >=> toWords
def toWords: String => Writer[String, List[String]] =
s => Writer(s.split("\\s+").toList, "toWords ")
def process: String => Writer[String, List[String]] = {
import kleisliSyntax._
// -Ypartial-unification should be on
upCase >=> toWords
}
这个函数把输入字符串中的所有字符转成大写，并把它拆分成单词，同时生成自己的操作日志。
用 do 记法，它看起来像这样：
process s = do
upStr <- upCase s
toWords upStr
def process: String => Writer[String, List[String]] =
s => {
import bindSyntax._
for {
upStr <- upCase(s)
words <- toWords(upStr)
} yield words
}
这里，upStr 只是一个 String，尽管 upCase 产生的是 Writer：
upCase :: String -> Writer String String
upCase s = Writer (map toUpper s, "upCase ")
def upCase: String => Writer[String, String] =
s => Writer(s.toUpperCase, "upCase ")
这是因为编译器会把 do 块脱糖成：
process s =
upCase s >>= \upStr ->
toWords upStr
def process: String => Writer[String, List[String]] =
s => {
import bindSyntax._
upCase(s) >>= (upStr => toWords(upStr))
}
upCase 的单子结果被绑定到一个接受 String 的 lambda。出现在 do 块中的，正是这个字符串的名字。读到这一行时：
upStr <- upCase s
upStr <- upCase(s)
我们会说，upStr 得到了 upCase s 的结果。
当内联 toWords 时，这种伪命令式风格会更明显。我们用对 tell 的调用替换它，先记录字符串 "toWords "，然后用 return 返回把字符串 upStr 通过 words 拆分后的结果。注意，words 是一个作用在字符串上的普通函数。
process s = do
upStr <- upCase s
tell "toWords "
return (words upStr)
def words: String => List[String] =
_.split("\\s+").toList
def process: String => Writer[String, List[String]] =
s => {
import bindSyntax._
for {
upStr <- upCase(s)
_ <- tell("toWords ")
} yield words(upStr)
}
这里，do 块中的每一行都会在脱糖后的代码中引入一个新的嵌套 bind：
process s =
upCase s >>= \upStr ->
tell "toWords " >>= \() ->
return (words upStr)
def words: String => List[String] =
_.split("\\s+").toList
def process: String => Writer[String, List[String]] =
s => {
import bindSyntax._
for {
upStr <- upCase(s)
_ <- tell("toWords ")
} yield words(upStr)
}
注意，tell 产生一个 unit 值，所以它不必被传给后续 lambda。忽略单子结果的内容（但不忽略它的效果，这里是对日志的贡献）非常常见，因此有一个专门的操作符可以在这种情况下替代 bind：
(>>) :: m a -> m b -> m b
m >> k = m >>= (\_ -> k)
object moreSyntax {
// 允许把 >> 当作中缀操作符使用
implicit class MoreOps[A, B, W: Monoid](m: Writer[W, A])
extends bindSyntax.MonadOps[A, B, W](m) {
def >>(k: Writer[W, B]): Writer[W, B] =
m >>= (_ => k)
}
}
我们代码实际脱糖后的样子是：
process s =
upCase s >>= \upStr ->
tell "toWords " >>
return (words upStr)
def process: String => Writer[String, List[String]] = s => {
import moreSyntax._
upCase(s) flatMap (upStr =>
tell("toWords ") >>
writerMonad.pure(words(upStr)))
}
一般来说，do 块由多行（或子块）组成；这些行要么使用左箭头引入新名字，让它们在后续代码中可用，要么纯粹为了副作用而执行。Bind 操作符隐含在代码行之间。顺便说一句，在 Haskell 中可以用花括号和分号替代 do 块中的格式缩进。这为把单子描述成“重载分号”的方式提供了理由。
注意，do 记法脱糖时产生的 lambda 和 bind 操作符嵌套，会让每一行的结果影响 do 块剩余部分的执行。这个性质可以用于引入复杂控制结构，例如模拟异常。
有趣的是，do 记法的等价物也在命令式语言中找到了应用，尤其是 C++。我说的是可恢复函数（resumable functions）或协程。C++ 的 future 形成单子1 并不是什么秘密。它是延续单子的一个例子，我们很快会讨论它。延续的问题在于它们非常难组合。在 Haskell 中，我们用 do 记法把“我的处理器会调用你的处理器”这种意大利面条式结构，变成非常像顺序代码的东西。可恢复函数让 C++ 中的同样转换成为可能。同一个机制还可以把嵌套循环2 的复杂结构变成 list comprehension 或“生成器”，它们本质上就是列表单子的 do 记法。没有单子这个统一抽象时，每个这样的问题通常都要通过提供语言的自定义扩展来处理。在 Haskell 中，这些全都通过库来解决。