第 25 章：单子的代数（Algebras for Monads）
原文：Bartosz Milewski, Category Theory for Programmers, Scala Edition, Chapter 25. 原书 PDF、
.tex源文件及相关图像采用 CC BY-SA 4.0；本译文按同一许可发布。
如果把自函子解释为定义表达式的方式，那么代数让我们求值这些表达式，而单子让我们形成并操作这些表达式。把代数和单子结合起来，不仅能获得大量功能，还能回答几个有趣的问题。
其中一个问题涉及单子与伴随之间的关系。我们已经看到，每个伴随都会定义一个单子（以及一个余单子）。问题是：每个单子（余单子）都能从伴随导出吗？答案是肯定的。有一整族伴随会生成给定单子。我会展示其中两个这样的伴随。
让我们回顾定义。单子是一个自函子 m，配有两个满足某些相干条件的自然变换。这些变换在 a 处的分量是：
eta_a :: a -> m a
mu_a :: m (m a) -> m a
同一个自函子的代数，是选择一个特定对象，也就是载体 a，并配上一个态射：
alg :: m a -> a
首先要注意，代数的方向与 eta_a 相反。直觉上，eta_a 从类型为 a 的值创建一个平凡表达式。让代数与单子兼容的第一个相干条件保证：使用载体为 a 的代数求值这个表达式，会得到原来的值：
alg . eta_a = id_a
第二个条件来自这样一个事实：对双层嵌套表达式 m (m a) 求值有两种方式。可以先应用 mu_a 压平表达式，然后使用代数的求值器；也可以先应用提升后的求值器来求值内部表达式，然后对结果应用求值器。我们希望这两种策略等价：
alg . mu_a = alg . m alg
这里，m alg 是用函子 m 提升 alg 后得到的态射。下面两个交换图描述了这两个条件（我把 m 替换成了 T，是为了呼应后文）：
a --eta_a--> T a --alg--> a
| |
id_a id_a
| |
v v
a ----------------------> a
T (T a) --T alg--> T a --alg--> a
| ^
mu_a |
v |
T a -----------alg---------------+
也可以在 Haskell 中表达这些条件：
alg . return = id
alg . join = alg . fmap alg
alg compose pure == id
alg compose flatten == alg compose fmap(alg)
看一个小例子。列表自函子的代数由某个类型 a 以及一个从 a 的列表产生 a 的函数组成。可以通过选择元素类型和累加器类型都等于 a，用 foldr 表达这个函数：
foldr :: (a -> a -> a) -> a -> [a] -> a
def foldr[A]: (A => A => A) => A => List[A] => A
这个特定代数由一个双参数函数（称为 f）和一个值 z 指定。列表函子恰好也是一个单子，其中 return 会把值转换成单元素列表。代数，也就是这里的 foldr f z，在 return 之后的组合会把 x 变成：
foldr f z [x] = x `f` z
def foldr[A]: (A => A => A) => A => List[A] => A =
f => z => {
case x :: Nil => f(x)(z)
}
这里把 f 的作用写成了中缀记法。如果下面的相干条件对每个 x 都满足，那么这个代数就与单子兼容：
x `f` z = x
f(x)(z) == x
如果把 f 看作二元运算符，这个条件说明 z 是右单位元。
第二个相干条件作用在列表的列表上。join 的作用是连接各个列表。随后可以折叠得到的列表。另一方面，也可以先折叠各个列表，再折叠得到的列表。同样，如果把 f 解释为二元运算符，这个条件说明该二元运算是结合的。当 (a, f, z) 是幺半群时，这些条件当然成立。
25.1 T-代数（T-algebras）
由于数学家喜欢把单子称为 T，他们把与之兼容的代数称为 T-代数。给定范畴 C 中单子 T 的 T-代数会形成一个范畴，称为 Eilenberg-Moore 范畴，常记作 C^T。这个范畴中的态射是代数同态。它们就是我们在 F-代数中见过的同态。
T-代数是由载体对象和求值器组成的 pair，即 (a, f)。存在一个显然的遗忘函子 U_T，从 C^T 到 C，它把 (a, f) 映射到 a。它也把 T-代数同态映射为 C 中载体对象之间的对应态射。你也许还记得，在伴随那一章里，遗忘函子的左伴随称为自由函子。
U_T 的左伴随称为 F_T。它把 C 中的对象 a 映射到 C^T 中的自由代数。这个自由代数的载体是 T a。它的求值器是一个从 T (T a) 回到 T a 的态射。由于 T 是单子，可以使用单子的 mu_a（Haskell 中的 join）作为求值器。
还必须证明这是一个 T-代数。为此，需要满足两个相干条件：
alg . eta_(T a) = id_(T a)
alg . mu_a = alg . T alg
但如果把 mu 代入为代数，这些正是单子律。
你也许还记得，每个伴随都会定义一个单子。事实证明，F_T 与 U_T 之间的伴随，定义的正是构造 Eilenberg-Moore 范畴时使用的那个单子 T。由于可以对每个单子执行这个构造，我们得出结论：每个单子都可以由一个伴随生成。稍后我还会展示另一个生成同一单子的伴随。
计划如下：首先我会通过定义这个伴随的单位和余单位，并证明相应的三角恒等式成立，来说明 F_T 确实是 U_T 的左伴随。然后我会说明，由这个伴随生成的单子确实就是我们原来的单子。
伴随的单位是自然变换：
eta :: I -> U_T . F_T
计算这个变换在 a 处的分量。恒等函子给出 a。自由函子产生自由代数 (T a, mu_a)，遗忘函子把它归约为 T a。合起来就得到一个从 a 到 T a 的映射。我们直接使用单子 T 的单位作为这个伴随的单位。
再看余单位：
epsilon :: F_T . U_T -> I
计算它在某个 T-代数 (a, f) 处的分量。遗忘函子忘掉 f，自由函子产生 pair (T a, mu_a)。所以，为了定义余单位 epsilon 在 (a, f) 处的分量，需要 Eilenberg-Moore 范畴中的合适态射，也就是一个 T-代数同态：
(T a, mu_a) -> (a, f)
这样的同态应该把载体 T a 映射到 a。我们只要复活那个被遗忘的求值器 f。这一次，我们把它用作 T-代数同态。确实，使 f 成为 T-代数的同一个交换图，也可以重新解释为说明它是一个 T-代数同态：
T (T a) --T f--> T a
| |
mu_a f
v v
T a ----f-----> a
于是，我们已经把余单位自然变换 epsilon 在 (a, f)（T-代数范畴中的对象）处的分量定义为 f。
为了完成伴随，还需要说明单位和余单位满足三角恒等式。它们是：
T a --T eta_a--> T (T a) --mu_a--> T a
a --eta_a--> T a --f--> a
第一个因为单子 T 的单位律而成立。第二个正是 T-代数 (a, f) 的定律。
我们已经确定这两个函子形成一个伴随：
F_T -| U_T
每个伴随都会产生一个单子。往返组合
U_T . F_T
是 C 中产生对应单子的自函子。来看它作用在对象 a 上会怎样。F_T 创建的自由代数是 (T a, mu_a)。遗忘函子 U_T 丢掉求值器。所以确实有：
U_T . F_T = T
正如预期，伴随的单位就是单子 T 的单位。
你也许记得，伴随的余单位通过下面的公式产生单子的乘法：
mu = R . epsilon . L
这是三个自然变换的水平组合，其中两个是恒等自然变换，分别把 L 映射到 L、把 R 映射到 R。中间那个余单位，是一个自然变换，它在代数 (a, f) 处的分量是 f。
来计算分量 mu_a。我们首先把 epsilon 水平组合在 F_T 之后，得到 epsilon 在 F_T a 处的分量。由于 F_T 把 a 变成代数 (T a, mu_a)，而 epsilon 选取求值器，所以最后得到 mu_a。左侧再与 U_T 做水平组合不会改变任何东西，因为 U_T 对态射的作用是平凡的。因此，从伴随得到的 mu 的确就是原单子 T 的 mu。
25.2 Kleisli 范畴（The Kleisli Category）
我们之前已经见过 Kleisli 范畴。它是从另一个范畴 C 和一个单子 T 构造出来的范畴。我们把这个范畴称为 C_T。Kleisli 范畴 C_T 中的对象是 C 的对象，但态射不同。Kleisli 范畴中从 a 到 b 的态射 f_K，对应于原范畴中从 a 到 T b 的态射 f。我们把这个态射称为从 a 到 b 的 Kleisli 箭头。
Kleisli 范畴中的态射组合，是用 Kleisli 箭头的单子组合定义的。例如，把 g_K 组合在 f_K 之后。在 Kleisli 范畴中有：
f_K :: a -> b
g_K :: b -> c
这在范畴 C 中对应于：
f :: a -> T b
g :: b -> T c
我们把组合定义为：
h_K = g_K . f_K
也就是 C 中的 Kleisli 箭头：
h :: a -> T c
h = mu . (T g) . f
在 Haskell 中会写成：
h = join . fmap g . f
h == flatten.compose(fmap(g) _ compose f)
存在一个从 C 到 C_T 的函子 F，它在对象上的作用是平凡的。在态射上，它把 C 中的 f 映射为 C_T 中的态射，方式是创建一个会修饰 f 返回值的 Kleisli 箭头。给定态射：
f :: a -> b
它会创建 C_T 中的态射，其对应 Kleisli 箭头为：
eta . f
在 Haskell 中会写成：
return . f
unit compose f
我们还可以定义一个从 C_T 回到 C 的函子 G。它接收 Kleisli 范畴中的对象 a，并把它映射到 C 中的对象 T a。它在态射 f_K 上的作用，对应于 Kleisli 箭头：
f :: a -> T b
也就是 C 中的一个态射：
T a -> T b
它由先提升 f、再应用 mu 给出：
mu_(T b) . T f
用 Haskell 记法读作：
G fT = join . fmap f
你也许认出，这正是用 join 定义单子 bind 的方式。
很容易看出，这两个函子形成伴随：
F -| G
并且它们的组合 G . F 会复现原单子 T。
所以这是产生同一单子的第二个伴随。事实上，存在一个完整的伴随范畴 Adj(C, T)，其中的伴随都会在 C 上产生同一个单子 T。我们刚刚看到的 Kleisli 伴随是这个范畴中的初始对象，而 Eilenberg-Moore 伴随是终对象。
25.3 余单子的余代数（Coalgebras for Comonads）
对于任意余单子 W，可以做类似构造。我们可以定义一个与余单子兼容的余代数范畴。它们使下面这些图交换：
a --coa--> W a --epsilon_a--> a
a --coa--> W a --delta_a--> W (W a)
| ^
coa |
v |
W a --------W coa----------------+
其中 coa 是载体为 a 的余代数的余求值态射：
coa :: a -> W a
而 epsilon 和 delta 是定义余单子的两个自然变换（在 Haskell 中，它们的分量称为 extract 和 duplicate）。
存在一个显然的遗忘函子 U_W，从这些余代数的范畴到 C。它只是忘掉余求值。我们考虑它的右伴随 F_W：
U_W -| F_W
遗忘函子的右伴随称为余自由函子。F_W 生成余自由余代数。它把 C 中的对象 a 指派为余代数 (W a, delta_a)。这个伴随把原来的余单子复现为复合 U_W . F_W。
类似地，可以用余 Kleisli 箭头构造一个余 Kleisli 范畴，并从对应的伴随重新生成余单子。
25.4 Lens
让我们回到关于 lens 的讨论。lens 可以写成一个余代数：
coalg_s :: a -> Store_s a
这是函子 Store_s 的余代数：
data Store s a = Store (s -> a) s
case class Store[S, A](run: S => A, s: S)
// convenient partially applied constructor
object Store {
def apply[S, A](run: S => A): S => Store[S, A] =
s => new Store(run, s)
}
这个余代数也可以表达为一对函数：
set :: a -> s -> a
get :: a -> s
（可以把 a 想成“全部”（all），把 s 想成其中一个“小”（small）的部分。）用这对函数表示时，有：
coalg_s a = Store (set a) (get a)
这里，a 是类型为 a 的值。注意，部分应用的 set 是一个函数 s -> a。
我们也知道 Store_s 是一个余单子：
instance Comonad (Store s) where
extract (Store f s) = f s
duplicate (Store f s) = Store (Store f) s
implicit def storeComonad[S] = new Comonad[Store[S, ?]] {
def extract[A](wa: Store[S, A]): A = wa match {
case Store(f, s) => f(s)
}
def duplicate[A](wa: Store[S, A]): Store[S, Store[S, A]] = wa match {
case Store(f, s) => Store(Store(f), s)
}
}
问题是：在什么条件下，lens 是这个余单子的余代数？第一个相干条件：
epsilon_a . coalg = id_a
翻译为：
set a (get a) = a
这就是一条 lens 律：如果把结构 a 的某个字段设为它原先的值，什么都不会改变。
第二个条件：
fmap coalg . coalg = delta_a . coalg
需要稍微多做一点工作。首先回忆 Store 函子的 fmap 定义：
fmap g (Store f s) = Store (g . f) s
implicit def storeFunctor[S] = new Functor[Store[S, ?]] {
def fmap[A, B](g: A => B)(fa: Store[S, A]): Store[S, B] = fa match {
case Store(f, s) =>
Store(g compose f, s)
}
}
把 fmap coalg 应用于 coalg 的结果，得到：
Store (coalg . set a) (get a)
Store(coalg compose set(a), get(a))
另一方面，把 duplicate 应用于 coalg 的结果，产生：
Store (Store (set a)) (get a)
Store(Store(set(a)), get(a))
要让这两个表达式相等，Store 下面的两个函数在作用于任意 s 时必须相等：
coalg (set a s) = Store (set a) s
coalg(set(a)(s)) == Store(set(a))(s)
展开 coalg，得到：
Store (set (set a s)) (get (set a s)) = Store (set a) s
Store(set(set(a)(s)))(get(set(a)(s))) == Store(set(a))(s)
这等价于剩下两条 lens 律。第一条：
set (set a s) = set a
set(set(a)(s)) == set(a)
告诉我们，把字段的值设置两次，与设置一次相同。第二条律：
get (set a s) = s
get(set(a)(s)) == s
告诉我们，读取刚设置为 s 的字段值，会得到 s 本身。
换句话说，一个行为良好的 lens 确实是 Store 函子的余单子余代数。
25.5 挑战（Challenges）
- 自由函子
F :: C -> C^T在态射上的作用是什么？提示：使用单子mu的自然性条件。 - 定义伴随：
U_W -| F_W
- 证明上面的伴随会复现原来的余单子。