第 18 章：伴随（Adjunctions）
原文：Bartosz Milewski, Category Theory for Programmers, Scala Edition, Chapter 18. 原书 PDF、
.tex源文件及相关图像采用 CC BY-SA 4.0；本译文按同一许可发布。
在数学中，我们有各种方式表达一件事像另一件事。最严格的是相等。如果两件事无法区分，它们就是相等的。在任何可以想象的语境中，一个都可以替代另一个。例如，你有没有注意到，每次谈论交换图时，我们都使用了态射的相等？这是因为态射形成一个集合（hom-set），而集合元素可以比较相等。
但相等往往太强。有许多例子中，两个东西在所有实际意图上都是相同的，却并不真正相等。例如，pair 类型 (Bool, Char) 并不严格等于 (Char, Bool)，但我们理解它们包含相同信息。这个概念最好由两个类型之间的同构来刻画，也就是一个可逆态射。因为它是态射，所以会保持结构；而“iso”意味着它是一次往返的一部分，无论从哪一边出发，最终都会回到同一个位置。对 pair 来说，这个同构称为 swap：
swap :: (a,b) -> (b,a)
swap (a,b) = (b,a)
def swap[A, B]: ((A, B)) => (B, A) = {
case (a, b) => (b, a)
}
swap 碰巧就是它自己的逆。
18.1 伴随与单位/余单位对（Adjunction and Unit/Counit Pair）
当我们谈论范畴同构时，会用范畴之间的映射，也就是函子来表达。我们希望能够说，如果存在一个从 $C$ 到 $D$ 的可逆函子 $R$（“右”），那么两个范畴 $C$ 和 $D$ 同构。换句话说，存在另一个从 $D$ 回到 $C$ 的函子 $L$（“左”），它与 $R$ 组合时等于恒等函子 $I$。有两种可能的组合，$R \circ L$ 和 $L \circ R$；也有两个可能的恒等函子，一个在 $C$ 中，另一个在 $D$ 中。
但棘手之处在于：两个函子相等是什么意思？下面这个相等是什么意思：
R . L = I_D
或者这个：
L . R = I_C
用对象的相等来定义函子的相等似乎合理。两个函子作用在相等对象上时，应该产生相等对象。但一般来说，在任意范畴中我们并没有对象相等的概念。它并不是定义的一部分。（如果继续深入“相等究竟是什么”这个洞穴，我们会抵达同伦类型论。）
你可能会说，函子是范畴的范畴中的态射，所以它们应该可以比较相等。确实，只要我们谈论的是小范畴，对象形成一个集合，就可以用集合元素的相等来比较对象。
但记住，$Cat$ 实际上是一个 2-范畴。2-范畴中的 hom-set 带有额外结构，也就是有作用在 1-态射之间的 2-态射。在 $Cat$ 中，1-态射是函子，2-态射是自然变换。所以在谈论函子时，把自然同构当作相等的替代品更自然。
因此，与其考虑范畴同构，不如考虑一个更一般的等价概念。如果能找到两个在范畴之间来回的函子，并且它们的组合（任一方向）都自然同构于恒等函子，那么范畴 $C$ 和 $D$ 就等价。换句话说，在组合 $R \circ L$ 与恒等函子 $I_D$ 之间存在一个双向自然变换，在 $L \circ R$ 与恒等函子 $I_C$ 之间也存在另一个双向自然变换。
伴随甚至比等价更弱，因为它并不要求两个函子的组合同构于恒等函子。相反，它规定存在一个从 $I_D$ 到 $R \circ L$ 的单向自然变换，以及另一个从 $L \circ R$ 到 $I_C$ 的单向自然变换。下面是这两个自然变换的签名：
eta :: I_D -> R . L
epsilon :: L . R -> I_C
$\eta$ 称为伴随的单位（unit），$\epsilon$ 称为余单位（counit）。
注意这两个定义之间的非对称性。一般来说，我们没有另外两个映射：
R . L -> I_D -- not necessarily
I_C -> L . R -- not necessarily
由于这种非对称性，函子 $L$ 称为函子 $R$ 的左伴随，而函子 $R$ 称为 $L$ 的右伴随。（当然，左右只有在你以某种特定方式画图时才有意义。）
伴随的紧凑记法是：
L -| R
为了更好地理解伴随，让我们更详细地分析单位和余单位。
先从单位开始。它是一个自然变换，因此是一族态射。给定 $D$ 中一个对象 $d$，$\eta$ 的分量是 $I d$（它等于 $d$）和 $(R \circ L)d$ 之间的态射；图中后者称为 $d'$：
eta_d :: d -> (R . L) d
注意，组合 $R \circ L$ 是 $D$ 中的自函子。
这个等式告诉我们，可以任意选择 $D$ 中一个对象 $d$ 作为起点，并使用往返函子 $R \circ L$ 选择目标对象 $d'$。然后我们射出一支箭，也就是态射 $\eta_d$，指向这个目标。
同理，余单位 $\epsilon$ 的分量可以描述为：
epsilon_c :: (L . R) c -> c
它告诉我们，可以任意选择 $C$ 中一个对象 $c$ 作为目标，并使用往返函子 $L \circ R$ 选择源对象 $c' = (L \circ R)c$。然后我们从源射出箭，也就是态射 $\epsilon_c$，指向目标。
另一种看待单位和余单位的方式是：单位允许我们在任何可以插入 $D$ 上恒等函子的地方引入组合 $R \circ L$；而余单位允许我们消去组合 $L \circ R$，用 $C$ 上的恒等函子替换它。这会导向一些“显然”的一致性条件，确保引入之后再消去不会改变任何东西：
L = L . I_D -> L . R . L -> I_C . L = L
R = I_D . R -> R . L . R -> R . I_C = R
这些称为三角恒等式，因为它们使下面的图交换：
L -> L . R . L -> L
R -> R . L . R -> R
这些是函子范畴中的图：箭头是自然变换，它们的组合是自然变换的水平组合。按分量写，这些恒等式变成：
epsilon_(L d) . L eta_d = id_(L d)
R epsilon_c . eta_(R c) = id_(R c)
在 Haskell 中，我们经常用不同名字看到单位和余单位。单位称为 return（或 Applicative 定义中的 pure）：
return :: d -> m d
// return 是 Scala 关键字
def pure[D]: D => M[D]
余单位则称为 extract：
extract :: w c -> c
def extract[C]: W[C] => C
这里，m 是对应于 $R \circ L$ 的（自）函子，w 是对应于 $L \circ R$ 的（自）函子。稍后我们会看到，它们分别是单子和余单子定义的一部分。
如果把自函子看作容器，那么单位（或 return）就是一个多态函数，它围绕任意类型的值创建一个默认盒子。余单位（或 extract）则做相反的事：从容器中取回或产生一个单值。
稍后会看到，每一对伴随函子都会定义一个单子和一个余单子。反过来，每个单子或余单子都可以分解为一对伴随函子，不过这种分解并不唯一。在 Haskell 中，我们大量使用单子，却很少把它们分解成伴随函子对，主要是因为那些函子通常会把我们带出 Hask。
不过，我们可以在 Haskell 中定义自函子的伴随。下面是取自 Data.Functor.Adjunction 的部分定义：
class (Functor f, Representable u) =>
Adjunction f u | f -> u, u -> f where
unit :: a -> u (f a)
counit :: f (u a) -> a
abstract class Adjunction[F[_], U[_]](
implicit val F: Functor[F],
val U: Representable[U]
) {
def unit[A](a: A): U[F[A]]
def counit[A](a: F[U[A]]): A
}
这个定义需要解释。首先，它描述了一个多参数类型类，两个参数是 f 和 u。它在这两个类型构造器之间建立了一个名为 Adjunction 的关系。
竖线之后的附加条件指定函数依赖。例如，f -> u 表示 u 由 f 决定（f 与 u 之间的关系是一个函数，这里是在类型构造器上的函数）。反过来，u -> f 表示，如果我们知道 u，那么 f 也被唯一决定。
马上我会解释，为什么在 Haskell 中可以施加右伴随 u 是可表示函子的条件。
18.2 伴随与 Hom-Set（Adjunctions and Hom-Sets）
还有一个等价定义，用 hom-set 的自然同构来定义伴随。这个定义与我们目前研究过的通用构造很好地衔接起来。每当你听到某个陈述说存在某个唯一态射，它会分解某个构造时，你应该把它理解为从某个集合到某个 hom-set 的映射。这就是“选出一个唯一态射”的含义。
此外，分解通常可以用自然变换描述。分解涉及交换图，也就是某个态射等于两个态射（因子）的组合。自然变换把态射映射为交换图。所以，在通用构造中，我们从一个态射到一个交换图，再到一个唯一态射。最终得到的是从态射到态射的映射，或者从一个 hom-set 到另一个 hom-set 的映射（通常位于不同范畴中）。如果这个映射可逆，并且可以自然地扩展到所有 hom-set，我们就有一个伴随。
通用构造与伴随的主要区别在于，后者是全局定义的，也就是针对所有 hom-set。例如，使用通用构造，你可以定义某两个特定对象的积，即使在那个范畴中其他任意对象对都不存在积。稍后会看到，如果一个范畴中任意一对对象的积都存在，那么它也可以通过伴随定义。
下面是用 hom-set 给出的伴随替代定义。和之前一样，我们有两个函子 $L : D \to C$ 和 $R : C \to D$。选择两个任意对象：$D$ 中的源对象 $d$，以及 $C$ 中的目标对象 $c$。可以用 $L$ 把源对象 $d$ 映射到 $C$。现在在 $C$ 中有两个对象，$L d$ 和 $c$。它们定义一个 hom-set：
C(L d, c)
类似地，可以用 $R$ 映射目标对象 $c$。现在在 $D$ 中有两个对象，$d$ 和 $R c$。它们也定义一个 hom-set：
D(d, R c)
如果存在 hom-set 的同构：
C(L d, c) ~= D(d, R c)
并且它同时在 $d$ 和 $c$ 上自然，那么我们就说 $L$ 是 $R$ 的左伴随。自然性意味着源 $d$ 可以在 $D$ 中平滑变化，目标 $c$ 可以在 $C$ 中平滑变化。更准确地说，我们有一个自然变换 $\varphi$，位于下面两个从 $C$ 到 $Set$ 的（协变）函子之间。它们在对象上的作用是：
c -> C(L d, c)
c -> D(d, R c)
另一个自然变换 $\psi$ 作用在下面两个（逆变）函子之间：
d -> C(L d, c)
d -> D(d, R c)
这两个自然变换都必须可逆。
伴随的两个定义很容易证明等价。例如，让我们从 hom-set 同构推出单位变换：
C(L d, c) ~= D(d, R c)
由于这个同构对任意对象 $c$ 都成立，它也必须对 $c = L d$ 成立：
C(L d, L d) ~= D(d, (R . L) d)
我们知道左边至少必须包含一个态射，也就是恒等态射。自然变换会把这个态射映射为 $D(d, (R \circ L)d)$ 的一个元素；或者插入恒等函子 $I$ 后，映射为：
D(I d, (R . L) d)
我们得到一族以 $d$ 为参数的态射。它们构成函子 $I$ 与函子 $R \circ L$ 之间的自然变换（自然性条件很容易验证）。这正是我们的单位 $\eta$。
反过来，从单位和余单位的存在出发，可以定义 hom-set 之间的变换。例如，取 hom-set $C(L d, c)$ 中的任意态射 $f$。我们想定义一个 $\varphi$，它作用在 $f$ 上，产生 $D(d, R c)$ 中的一个态射。
其实没有太多选择。我们可以尝试用 $R$ 提升 $f$。这会产生一个从 $R(L d)$ 到 $R c$ 的态射 $R f$，也就是 $D((R \circ L)d, R c)$ 中的一个态射。
而 $\varphi$ 的一个分量需要的是从 $d$ 到 $R c$ 的态射。这不是问题，因为我们可以用 $\eta_d$ 的一个分量从 $d$ 到达 $(R \circ L)d$。得到：
phi f = R f . eta_d
另一个方向类似，$\psi$ 的推导也类似。
回到 Haskell 的 Adjunction 定义，自然变换 $\varphi$ 和 $\psi$ 分别由关于 a 和 b 多态的函数 leftAdjunct 与 rightAdjunct 替代。函子 $L$ 和 $R$ 分别称为 f 和 u：
class (Functor f, Representable u) =>
Adjunction f u | f -> u, u -> f where
leftAdjunct :: (f a -> b) -> (a -> u b)
rightAdjunct :: (a -> u b) -> (f a -> b)
abstract class Adjunction[F[_], U[_]](
implicit val F: Functor[F],
val U: Representable[U]
) {
// 调整参数顺序，帮助 Scala 编译器推断类型
def leftAdjunct[A, B](a: A)(f: F[A] => B): U[B]
def rightAdjunct[A, B](fa: F[A])(f: A => U[B]): B
}
unit/counit 表述与 leftAdjunct/rightAdjunct 表述之间的等价性由下面这些映射见证：
unit = leftAdjunct id
counit = rightAdjunct id
leftAdjunct f = fmap f . unit
rightAdjunct f = counit . fmap f
def unit[A](a: A): U[F[A]] =
leftAdjunct(a)(identity)
def counit[A](a: F[U[A]]): A =
rightAdjunct(a)(identity)
def leftAdjunct[A, B](a: A)(f: F[A] => B): U[B] =
U.map(unit(a))(f)
def rightAdjunct[A, B](a: F[A])(f: A => U[B]): B =
counit(F.map(a)(f))
跟随从伴随的范畴描述到 Haskell 代码的翻译，是很有启发性的。我强烈建议把它作为练习。
现在可以解释为什么在 Haskell 中右伴随自动是可表示函子。原因是，作为第一近似，我们可以把 Haskell 类型范畴看作集合范畴。
当右侧范畴 $D$ 是 $Set$ 时，右伴随 $R$ 是一个从 $C$ 到 $Set$ 的函子。如果能在 $C$ 中找到一个对象 rep，使得 hom 函子 $C(rep, -)$ 与 $R$ 自然同构，那么这样的函子就是可表示的。事实证明，如果 $R$ 是某个从 $Set$ 到 $C$ 的函子 $L$ 的右伴随，那么这样的对象总是存在，它就是单元素集合 () 在 $L$ 下的像：
rep = L ()
确实，伴随告诉我们，下面两个 hom-set 自然同构：
C(L (), c) ~= Set((), R c)
对给定的 $c$，右边是从单元素集合 () 到 $R c$ 的函数集合。前面已经见过，每个这样的函数都会从集合 $R c$ 中选出一个元素。这样的函数集合同构于集合 $R c$。所以我们有：
C(L (), -) ~= R
这说明 $R$ 的确是可表示的。
18.3 从伴随得到积（Product from Adjunction）
我们之前用通用构造引入了几个概念。其中许多概念在全局定义时，用伴随表达更容易。最简单的非平凡例子就是积。积的通用构造的要点，是能够把任何类似积的候选者通过通用积来分解。
更准确地说，两个对象 $a$ 和 $b$ 的积，是对象 $(a \times b)$（或 Haskell 记法中的 (a, b)），并配有两个态射 fst 和 snd，使得对于任意其他候选者 $c$，只要它配有两个态射 $p : c \to a$ 与 $q : c \to b$，就存在一个唯一态射 $m : c \to (a, b)$，通过 fst 和 snd 分解 $p$ 与 $q$。
如我们之前见过的，在 Haskell 中可以实现一个分解器，从两个投影生成这个态射：
factorizer :: (c -> a) -> (c -> b) -> (c -> (a, b))
factorizer p q = \x -> (p x, q x)
def factorizer[A, B, C](p: C => A)(q: C => B): (C => (A, B)) =
x => (p(x), q(x))
很容易验证分解条件成立：
fst . factorizer p q = p
snd . factorizer p q = q
factorizer(p)(q).andThen(_._1) == p
factorizer(p)(q).andThen(_._2) == q
我们有一个映射，它接受一对态射 p 和 q，并产生另一个态射 m = factorizer p q。
如何把它翻译成伴随定义所需的两个 hom-set 之间的映射？诀窍是走出 Hask，把这一对态射看成积范畴中的单个态射。
先回忆一下什么是积范畴。取两个任意范畴 $C$ 和 $D$。积范畴 $C \times D$ 中的对象是对象对，一个来自 $C$，一个来自 $D$。态射是态射对，一个来自 $C$，一个来自 $D$。
为了在某个范畴 $C$ 中定义积，我们应该从积范畴 $C \times C$ 开始。来自 $C$ 的态射对，是积范畴 $C \times C$ 中的单个态射。
刚开始可能会有点困惑：我们正在用积范畴定义积。然而，它们是非常不同的积。定义积范畴不需要通用构造。我们所需要的只是对象对和态射对的概念。
不过，来自 $C$ 的对象对并不是 $C$ 中的对象。它是另一个范畴 $C \times C$ 中的对象。我们可以把这对对象形式地写成 $\langle a, b \rangle$，其中 $a$ 和 $b$ 是 $C$ 的对象。另一方面，要定义对象 $a \times b$（或 Haskell 中的 (a, b)），就需要通用构造；这个对象属于同一个范畴 $C$。这个对象应该以通用构造指定的方式表示对象对 $\langle a, b \rangle$。它不一定存在；即使对某些对象对存在，也可能对 $C$ 中其他对象对不存在。
现在把分解器看作 hom-set 的映射。第一个 hom-set 位于积范畴 $C \times C$ 中，第二个位于 $C$ 中。$C \times C$ 中的一般态射是一个态射对 $\langle f, g \rangle$：
f :: c' -> a
g :: c'' -> b
其中 $c''$ 可能不同于 $c'$。但为了定义积，我们关心的是 $C \times C$ 中一个特殊态射，也就是共享同一个源对象 $c$ 的一对 $p$ 和 $q$。这没问题：在伴随定义中，左侧 hom-set 的源不是任意对象，而是左函子 $L$ 作用在右侧范畴某个对象上的结果。符合要求的函子很容易猜到，它就是从 $C$ 到 $C \times C$ 的对角函子 $\Delta$，它在对象上的作用是：
Delta c = <c, c>
因此，我们伴随中的左侧 hom-set 应该是：
(C x C)(Delta c, <a, b>)
它是积范畴中的 hom-set。它的元素是态射对，我们可以把它们认作分解器的参数：
(c -> a) and (c -> b) ...
右侧 hom-set 位于 $C$ 中，并且从源对象 $c$ 指向某个函子 $R$ 作用在 $C \times C$ 中目标对象上的结果。这个函子把对象对 $\langle a, b \rangle$ 映射到我们的积对象 $a \times b$。我们把这个 hom-set 的元素认作分解器的结果：
... -> (c -> (a, b))
我们还没有得到完整伴随。为此，我们首先需要分解器可逆，因为我们正在构造 hom-set 之间的同构。分解器的逆应该从态射 $m$ 开始，也就是从某个对象 $c$ 到积对象 $a \times b$ 的态射。换句话说，$m$ 应该是下面集合的元素：
C(c, a x b)
逆分解器应该把 $m$ 映射为 $C \times C$ 中的态射 $\langle p, q \rangle$，它从 $\langle c, c \rangle$ 到 $\langle a, b \rangle$；换句话说，是下面集合中的元素：
(C x C)(Delta c, <a, b>)
如果这样的映射存在，我们就得出结论：对角函子存在一个右伴随。这个函子定义了积。
在 Haskell 中，总可以通过分别把 m 与 fst 和 snd 组合，构造分解器的逆：
p = fst . m
q = snd . m
要完成这两种积定义方式等价性的证明，还需要说明 hom-set 之间的映射在 $a$、$b$ 和 $c$ 上都是自然的。我会把这件事留给勤勉的读者作为练习。
总结我们做过的事：范畴积可以全局地定义为对角函子的右伴随：
(C x C)(Delta c, <a, b>) ~= C(c, a x b)
这里，$a \times b$ 是右伴随函子 Product 作用在对象对 $\langle a, b \rangle$ 上的结果。注意，任何从 $C \times C$ 出发的函子都是双函子，所以 Product 是一个双函子。在 Haskell 中，Product 双函子直接写作 (,)。你可以把它应用到两个类型上，并得到它们的积类型，例如：
(,) Int Bool ~ (Int, Bool)
Product2[Int, Boolean] ~ (Int, Boolean)
18.4 从伴随得到指数对象（Exponential from Adjunction）
指数对象 $b^a$，或者函数对象 $a \Rightarrow b$，可以用通用构造定义。如果这个构造对所有对象对都存在，就可以被看成一个伴随。诀窍仍然是聚焦于下面这个陈述：
对任意另一个对象 $z$，只要有一个态射 $g : z \times a \to b$，就存在一个唯一态射 $h : z \to (a \Rightarrow b)$。
这个陈述建立了 hom-set 之间的映射。
在这种情况下，我们处理的是同一个范畴中的对象，所以两个伴随函子都是自函子。左（自）函子 $L$ 作用在对象 $z$ 上时产生 $z \times a$。它对应于与某个固定的 $a$ 取积。
右（自）函子 $R$ 作用在 $b$ 上时产生函数对象 $a \Rightarrow b$（或 $b^a$）。同样，$a$ 是固定的。这两个函子之间的伴随常写为：
- x a -| (-)^a
这个伴随背后的 hom-set 映射，最好通过重画我们在通用构造中用过的图来理解。
注意，eval 态射1 不是别的，正是这个伴随的余单位：
(a => b) x a -> b
其中：
(a => b) x a = (L . R) b
我之前提过，通用构造定义的对象在同构意义下唯一。这就是为什么我们会说“这个”积和“这个”指数对象。这个性质也会转移到伴随上：如果一个函子有伴随，那么这个伴随在同构意义下唯一。
18.5 挑战（Challenges）
- 推导 $\psi$ 的自然性方块，其中 $\psi$ 是下面两个（逆变）函子之间的变换：
a -> C(L a, b)
a -> D(a, R b)
- 从伴随第二个定义中的 hom-set 同构出发，推导余单位 $\epsilon$。
- 完成伴随两个定义等价性的证明。
- 说明余积可以由伴随定义。请从余积的分解器定义开始。
- 说明余积是对角函子的左伴随。
- 在 Haskell 中定义积与函数对象之间的伴随。