第 22 章：范畴意义下的单子（Monads Categorically）
原文：Bartosz Milewski, Category Theory for Programmers, Scala Edition, Chapter 22. 原书 PDF、
.tex源文件及相关图像采用 CC BY-SA 4.0；本译文按同一许可发布。
如果你向程序员提到单子，最后多半会谈到效果。对数学家来说，单子关乎代数。稍后我们会谈到代数，它们在编程中扮演重要角色；但我想先给你一点关于代数与单子关系的直觉。现在这会有点不够严密，但请先跟着我走。
代数关乎创建、操作和求值表达式。表达式由运算符构建。考虑这个简单表达式：
x^2 + 2x + 1
这个表达式由变量（比如 x）、常量（比如 1 或 2）以及加法、乘法之类的运算符组合而成。作为程序员，我们经常把表达式想成树。
树是容器，所以更一般地说，表达式是用于存储变量的容器。在范畴论中，我们用自函子表示容器。如果给变量 x 分配类型 a，表达式就会具有类型 m a，其中 m 是构建表达式树的自函子。（非平凡的分支表达式通常用递归定义的自函子创建。）
可以对表达式执行的最常见操作是什么？是替换：用表达式替换变量。例如，在我们的例子中，可以把 x 替换为 y - 1，得到：
(y - 1)^2 + 2(y - 1) + 1
发生了什么？我们取了一个类型为 m a 的表达式，并应用一个类型为 a -> m b 的变换（b 表示 y 的类型）。结果是一个类型为 m b 的表达式。写出来就是：
m a -> (a -> m b) -> m b
没错，这就是单子 bind 的签名。
这算是一点动机。现在进入单子的数学部分。数学家使用的记法和程序员不同。他们喜欢用字母 T 表示自函子，用希腊字母：mu 表示 join，eta 表示 return。join 和 return 都是多态函数，因此可以猜到它们对应自然变换。
因此，在范畴论中，单子被定义为一个自函子 T，并配有一对自然变换 mu 和 eta。
mu 是从函子 T 的平方回到 T 的自然变换。平方只是函子与自身组合，也就是 T . T（只有对自函子才能做这种平方）。
mu :: T^2 -> T
这个自然变换在对象 a 处的分量是态射：
mu_a :: T (T a) -> T a
在 Hask 中，它直接翻译为我们对 join 的定义。
eta 是恒等函子 I 与 T 之间的自然变换：
eta :: I -> T
考虑到 I 作用在对象 a 上只是 a，eta 的分量由下面的态射给出：
eta_a :: a -> T a
它直接翻译为我们对 return 的定义。
这些自然变换必须满足一些额外定律。一种看法是，这些定律让我们能够为自函子 T 定义 Kleisli 范畴。记住，a 与 b 之间的 Kleisli 箭头定义为态射 a -> T b。两个这样的箭头的组合（我会把它写成带下标 T 的圆圈）可以用 mu 实现：
g ._T f = mu_c . (T g) . f
其中：
f :: a -> T b
g :: b -> T c
这里，T 作为函子，可以应用到态射 g 上。用 Haskell 记法更容易认出这个公式：
f >=> g = join . fmap g . f
(f >=> g) ==
(flatten compose fmap[B, T[C]](g) compose f)
或者按分量写：
(f >=> g) a = join (fmap g (f a))
(f >=> g)(a) == flatten(fmap(g)(f(a)))
从代数解释看，我们只是在组合两次连续替换。
为了让 Kleisli 箭头形成范畴，我们希望它们的组合满足结合律，并且 eta_a 成为 a 处的恒等 Kleisli 箭头。这个要求可以翻译成关于 mu 和 eta 的单子律。但还有另一种推导这些定律的方式，它让它们看起来更像幺半群定律。事实上，mu 经常称为乘法，而 eta 称为单位。
粗略地说，结合律声明：把 T 的三次方 T^3 降到 T 的两种方式必须给出相同结果。两个单位律（左单位和右单位）声明：当 eta 应用到 T，然后由 mu 归约时，会回到 T。
事情有一点微妙，因为我们在组合自然变换和函子。因此，有必要稍微复习一下水平组合。例如，T^3 可以看作 T 在 T^2 之后的组合。可以对它应用两个自然变换的水平组合：
I_T . mu
得到 T . T；然后可以继续应用 mu 把它归约为 T。I_T 是从 T 到 T 的恒等自然变换。你经常会看到这种水平组合 I_T . mu 的记法被缩短为 T . mu。这个记法没有歧义，因为函子和自然变换直接组合没有意义，所以在这个语境中 T 必须表示 I_T。
也可以在（自）函子范畴 [C, C] 中画出图示：
另一种方式是把 T^3 看作 T^2 . T 的组合，并对它应用 mu . T。结果同样是 T . T，然后再次用 mu 归约到 T。我们要求这两条路径产生相同结果。
类似地，可以对恒等函子 I 在 T 之后的组合应用水平组合 eta . T，得到 T^2，然后用 mu 归约。结果应该与直接把恒等自然变换应用到 T 相同。类比地，对 T . eta 也应该如此。
你可以说服自己，这些定律保证了 Kleisli 箭头的组合确实满足范畴定律。
单子与幺半群之间的相似性非常醒目。我们有乘法 mu、单位 eta、结合律和单位律。但我们对幺半群的定义太窄，无法直接把单子描述成幺半群。因此，让我们推广幺半群的概念。
22.1 幺半范畴（Monoidal Categories）
回到幺半群的传统定义。它是一个带二元运算和一个称为单位的特殊元素的集合。在 Haskell 中，这可以表达为类型类：
class Monoid m where
mappend :: m -> m -> m
mempty :: m
trait Monoid[M] {
def combine(x: M, y: M): M
def empty: M
}
二元运算 mappend 必须满足结合律和单位律（也就是说，与单位 mempty 相乘是不产生变化的操作）。
注意，在 Haskell 中，mappend 的定义是柯里化的。它可以解释为把 m 的每个元素映射到一个函数：
mappend :: m -> (m -> m)
def combine(x: M): (M => M)
正是这种解释产生了“幺半群是单对象范畴”的定义，其中自态射 (m -> m) 表示幺半群的元素。不过，由于柯里化内建于 Haskell，我们同样可以从另一种乘法定义开始：
mu :: (m, m) -> m
def mu: ((M, M)) => M
这里，笛卡尔积 (m, m) 成为待相乘的 pair 的来源。
这个定义提示了一条不同的推广路径：用范畴积替换笛卡尔积。我们可以从一个全局定义了积的范畴开始，选取其中一个对象 m，并把乘法定义为态射：
mu :: m x m -> m
不过有一个问题：在任意范畴中，我们不能偷看对象内部，那么如何选出单位元素？这里有一个技巧。还记得选择元素等价于从单元素集合出发的函数吗？在 Haskell 中，可以把 mempty 的定义替换为一个函数：
eta :: () -> m
def eta: Unit => M
单元素集合是 $Set$ 中的终对象，所以很自然可以把这个定义推广到任何拥有终对象 t 的范畴：
eta :: t -> m
这让我们无需谈论元素，也能选出单位“元素”。
不同于之前把幺半群定义成单对象范畴时，幺半律在这里不会自动满足，必须施加它们。但为了表达这些定律，必须先建立底层范畴积自身的幺半结构。先回忆一下 Haskell 中的幺半结构如何工作。
从结合律开始。Haskell 中对应的等式律是：
mu (x, mu (y, z)) = mu (mu (x, y), z)
mu (x, mu (y, z)) == mu (mu (x, y), z)
在把它推广到其他范畴之前，必须把它重写为函数（态射）的相等。我们必须抽象掉它对各个变量的作用，也就是使用 point-free 记法。知道笛卡尔积是一个双函子后，可以把左边写成：
(mu . bimap id mu)(x, (y, z))
mu compose bimap(identity)(mu)
右边写成：
(mu . bimap mu id)((x, y), z)
mu compose bimap(mu)(identity)
这几乎就是我们想要的。不幸的是，笛卡尔积并非严格结合：(x, (y, z)) 与 ((x, y), z) 并不相同，所以不能直接写成 point-free：
mu . bimap id mu = mu . bimap mu id
mu.compose(bimap(identity)(mu)) ==
mu.compose(bimap(mu)(identity))
另一方面，pair 的两种嵌套方式是同构的。有一个可逆函数称为结合子（associator），用于在它们之间转换：
alpha :: ((a, b), c) -> (a, (b, c))
alpha ((x, y), z) = (x, (y, z))
def alpha[A, B, C]: (((A, B), C)) => ((A, (B, C))) = {
case ((x, y), z) => (x, (y, z))
}
借助结合子，可以为 mu 写出 point-free 的结合律：
mu . bimap id mu . alpha = mu . bimap mu id
mu.compose(
bimap(identity)(mu) compose alpha) ==
mu.compose(bimap(mu)(identity))
单位律也可以用类似技巧处理。在新记法中，它们的形式是：
mu (eta (), x) = x
mu (x, eta ()) = x
mu(eta(), x) == x
mu(x, eta()) == x
它们可以重写为：
(mu . bimap eta id) ((), x) = lambda((), x)
(mu . bimap id eta) (x, ()) = rho (x, ())
mu.compose(bimap(eta)(identity[M]))(((), x)) == lambda(((), x))
mu.compose(bimap(identity[M])(eta))((x, ())) == rho((x, ()))
同构 lambda 和 rho 分别称为左单位子和右单位子。它们见证了 unit () 是笛卡尔积在同构意义下的单位：
lambda :: ((), a) -> a
lambda ((), x) = x
rho :: (a, ()) -> a
rho (x, ()) = x
def lambda[A]: ((Unit, A)) => A = {
case ((), x) => x
}
def rho[A]: ((A, Unit)) => A = {
case (x, ()) => x
}
因此，单位律的 point-free 版本是：
mu . bimap id eta = rho
mu . bimap eta id = lambda
mu.compose(bimap(eta)(identity[M])) == lambda
mu.compose(bimap(identity[M])(eta)) == rho
我们使用底层笛卡尔积自身像类型范畴中的幺半乘法一样运作这一事实，为 mu 和 eta 表达了 point-free 的幺半律。不过请记住，笛卡尔积的结合律和单位律只在同构意义下成立。
事实证明，这些定律可以推广到任何带积和终对象的范畴。范畴积确实在同构意义下满足结合律，终对象也在同构意义下是单位。结合子和两个单位子都是自然同构。这些定律可以用交换图表示。
注意，因为积是双函子，它可以提升一对态射，在 Haskell 中这由 bimap 完成。
我们可以停在这里，说可以在任何带范畴积和终对象的范畴上定义幺半群。只要能选出一个对象 m 和两个满足幺半律的态射 mu 与 eta，就有一个幺半群。但还可以做得更好。为了表达 mu 和 eta 的定律，我们并不需要完整的范畴积。回忆一下，积是通过使用投影的通用构造定义的。但在表达幺半律时，我们并没有使用任何投影。
一个行为像积但并不是积的双函子，称为张量积（tensor product），通常用中缀操作符 ⊗ 表示。一般张量积的定义有点微妙，但我们不必担心。只列出它的性质即可，其中最重要的是在同构意义下满足结合律。
类似地，我们不需要对象 t 是终对象。我们从未使用过它的终性质，也就是从任意对象到它存在唯一态射。我们要求的是，它与张量积配合良好。这意味着我们希望它成为张量积的单位，同样是在同构意义下。合在一起：
一个幺半范畴是一个范畴 $C$，配有一个称为张量积的双函子：
tensor :: C x C -> C
以及一个称为单位对象的特殊对象 i，再配有三个自然同构，分别称为结合子、左单位子和右单位子：
alpha_abc :: (a tensor b) tensor c -> a tensor (b tensor c)
lambda_a :: i tensor a -> a
rho_a :: a tensor i -> a
（此外，还有一个用于简化四重张量积的相干条件。）
重要的是，张量积描述了许多熟悉的双函子。特别是，它适用于积、余积，以及马上会看到的自函子组合（也适用于一些更奇特的积，比如 Day convolution）。幺半范畴会在富范畴的表述中扮演关键角色。
22.2 幺半范畴中的幺半群（Monoid in a Monoidal Category）
现在可以在幺半范畴这个更一般的设定中定义幺半群。先选择一个对象 m。使用张量积，可以形成 m 的幂。m 的平方是 m tensor m。m 的三次方有两种形成方式，但它们通过结合子同构。更高次幂也是类似（这就是需要相干条件的地方）。为了形成幺半群，需要选择两个态射：
mu :: m tensor m -> m
eta :: i -> m
其中 i 是张量积的单位对象。
这些态射必须满足结合律和单位律，可以用下面的交换图表达：
注意，张量积是双函子这一点至关重要，因为我们需要提升态射对，形成 mu tensor id 或 eta tensor id 这样的积。这些图只是我们之前关于范畴积结果的直接推广。
22.3 作为幺半群的单子（Monads as Monoids）
幺半结构会出现在意想不到的地方。函子范畴就是这样一个地方。稍微眯起眼睛，你也许能把函子组合看作一种乘法。问题是，不是任意两个函子都可以组合；一个函子的目标范畴必须是另一个函子的源范畴。这正是态射组合的通常规则，而我们知道，函子的确是范畴 $Cat$ 中的态射。但就像自态射（回到同一个对象的态射）总是可以组合一样，自函子也总是可以组合。
对任意给定范畴 $C$，从 $C$ 到 $C$ 的自函子形成函子范畴 [C, C]。它的对象是自函子，态射是它们之间的自然变换。我们可以从这个范畴中取任意两个对象，比如自函子 F 和 G，并产生第三个对象 F . G，也就是它们组合成的自函子。
自函子组合是张量积的好候选吗？首先必须确认它是一个双函子。它能否用于提升一对态射，也就是这里的一对自然变换？张量积上类似 bimap 的签名大致如下：
bimap :: (a -> b) -> (c -> d) -> (a tensor c -> b tensor d)
如果把对象替换为自函子，箭头替换为自然变换，张量积替换为组合，就得到：
(F -> F') -> (G -> G') -> (F . G -> F' . G')
你可能会认出这是水平组合的特殊情形。
我们还拥有恒等自函子 I，它可以作为自函子组合，也就是新张量积，的单位。此外，函子组合满足结合律。事实上，结合律和单位律都是严格的，不需要结合子或两个单位子。因此，自函子以函子组合作为张量积，形成严格幺半范畴。
这个范畴中的幺半群是什么？它是一个对象，也就是一个自函子 T；以及两个态射，也就是自然变换：
mu :: T . T -> T
eta :: I -> T
不止如此，下面是幺半律：
它们正是我们之前看到的单子律。现在你理解 Saunders Mac Lane 的著名引语了：
总而言之，单子只是自函子范畴中的一个幺半群。
你可能在函数式编程会议的一些 T 恤上见过它。
22.4 从伴随得到单子（Monads from Adjunctions）
一个伴随1 L -| R 是一对在两个范畴 $C$ 和 $D$ 之间来回的函子。它们有两种组合方式，产生两个自函子 R . L 和 L . R。按照伴随定义，这些自函子通过两个称为单位和余单位的自然变换与恒等函子相关：
eta :: I_D -> R . L
epsilon :: L . R -> I_C
我们立刻看到，伴随的单位看起来就像单子的单位。事实证明，自函子 R . L 的确是一个单子。我们只需要定义与 eta 搭配的合适 mu。它是从这个自函子的平方到自函子自身的自然变换；用伴随函子表示，就是：
R . L . R . L -> R . L
确实，可以用余单位折叠中间的 L . R。mu 的精确公式由水平组合给出：
mu = R . epsilon . L
单子律来自伴随的单位与余单位满足的恒等式，以及交换律。
在 Haskell 中我们很少看到从伴随导出的单子，因为伴随通常涉及两个范畴。不过，指数对象或者函数对象的定义是一个例外。下面是形成这个伴随的两个自函子：
L z = z x s
R b = s => b
你可能会认出它们的组合是熟悉的状态单子：
R (L z) = s => (z x s)
我们之前在 Haskell 中见过这个单子：
newtype State s a = State (s -> (a, s))
case class State[S, A](run: S => (A, S))
也把这个伴随翻译到 Haskell。左函子是 product 函子：
newtype Prod s a = Prod (a, s)
case class Prod[S, A](run: (A, S))
右函子是 reader 函子：
newtype Reader s a = Reader (s -> a)
case class Reader[S, A](run: S => A)
它们形成伴随：
instance Adjunction (Prod s) (Reader s) where
counit (Prod (Reader f, s)) = f s
unit a = Reader (\s -> Prod (a, s))
implicit def state[S] = new Adjunction[Prod[S, ?], Reader[S, ?]] {
def counit[A](a: Prod[S, Reader[S, A]]): A = a match {
case Prod((Reader(f), s)) => f(s)
}
def unit[A](a: A): Reader[S, Prod[S, A]] =
Reader(s => Prod((a, s)))
}
你可以很容易说服自己，reader 函子在 product 函子之后的组合确实等价于 state 函子：
newtype State s a = State (s -> (a, s))
case class State[S, A](run: S => (A, S))
正如预期，伴随的单位等价于 state 单子的 return 函数。余单位通过对参数求值来作用于函数。这可以认作 runState 函数的非柯里化版本：
runState :: State s a -> s -> (a, s)
runState (State f) s = f s
def runState[S, A]: State[S, A] => S => (A, S) = {
case State(f) => s => f(s)
}
之所以说非柯里化，是因为在余单位中它作用在一个 pair 上。
现在可以把 state 单子的 join 定义为自然变换 mu 的一个分量。为此，需要三个自然变换的水平组合：
mu = R . epsilon . L
换句话说，我们需要把余单位 epsilon 偷渡过 reader 函子的一层。不能直接调用 fmap，因为编译器会选择 State 函子的 fmap，而不是 Reader 函子的 fmap。但回忆一下，reader 函子的 fmap 只是左函数组合。因此我们会直接使用函数组合。
首先必须剥开数据构造器 State，暴露 State 函子内部的函数。这通过 runState 完成：
ssa :: State s (State s a)
runState ssa :: s -> (State s a, s)
def ssa[S, A]: State[S, State[S, A]]
def rss[S, A]: S => (State[S, A], S) =
runState[S, State[S, A]](ssa)
然后把它与由非柯里化 runState 定义的余单位做左组合。最后，再把它包回 State 数据构造器中：
join :: State s (State s a) -> State s a
join ssa = State (uncurry runState . runState ssa)
def join[S, A]: State[S, State[S, A]] => State[S, A] =
ssa => {
State(
Function.uncurried(runState[S, A])
.tupled
.compose(runState(ssa))
)
}
这确实就是 State 单子的 join 实现。
事实证明，不仅每个伴随都会产生一个单子，反过来也成立：每个单子都可以分解成两个伴随函子的组合。不过，这样的分解并不唯一。下一节我们会谈到另一个自函子 L . R。