第 12 章：极限与余极限（Limits and Colimits）
原文：Bartosz Milewski, Category Theory for Programmers, Scala Edition, Chapter 12. 原书 PDF、
.tex源文件及相关图像采用 CC BY-SA 4.0；本译文按同一许可发布。
在范畴论中，似乎一切都与一切有关，而且一切都可以从许多角度观察。以积的通用构造为例。既然我们已经更了解函子和自然变换，能否简化它，甚至推广它？让我们试试。
积的构造始于选择两个对象 a 和 b，也就是我们想构造其积的对象。但“选择对象”是什么意思？能否用更范畴化的语言重述这个动作？
两个对象形成一个模式，一个非常简单的模式。可以把这个模式抽象成一个范畴：一个非常简单的范畴，但仍然是范畴。我们称它为 2。它只包含两个对象 1 和 2，除了两个必需的恒等态射之外没有其他态射。现在，可以把在 $C$ 中选择两个对象这件事，重述为定义一个从范畴 2 到 $C$ 的函子 $D$。函子把对象映射到对象，所以它的像只是两个对象（如果函子折叠对象，也可能只有一个对象，这也没关系）。它也映射态射；在这里，它只是把恒等态射映射到恒等态射。
这种方式的好处在于，它建立在范畴概念之上，避免了“选择对象”这种不精确描述，这种描述直接取自祖先狩猎采集时代的词汇。顺便说一句，它也很容易推广，因为没有什么能阻止我们使用比 2 更复杂的范畴来定义模式。
继续往下。积定义的下一步是选择候选对象 c。这里同样可以把选择重述为来自单对象范畴的函子。事实上，如果我们使用 Kan 扩张，那会是正确做法。但我们还没准备好讨论 Kan 扩张，所以可以使用另一个技巧：从同一个范畴 2 到 $C$ 的常函子 Delta。在 $C$ 中选择 c 可以用 Delta_c 完成。记住，Delta_c 把所有对象映射到 c，把所有态射映射到 id_c。
现在我们有两个从 2 到 $C$ 的函子 Delta_c 和 $D$，自然会询问它们之间的自然变换。由于 2 中只有两个对象，自然变换会有两个分量。2 中的对象 1 被 Delta_c 映射到 c，被 $D$ 映射到 a。所以 Delta_c 与 $D$ 之间自然变换在 1 处的分量，是从 c 到 a 的态射。可以称它为 p。类似地，第二个分量是从 c 到 b 的态射 q，其中 b 是对象 2 在 $D$ 下的像。
但这正像我们在积的原始定义中使用的两个投影。因此，与其谈论选择对象和投影，不如谈论选择函子和自然变换。碰巧在这个简单例子中，这个变换的自然性条件平凡成立，因为 2 中没有非平凡态射（除了恒等态射）。
如果把这个构造推广到 2 以外的范畴，例如包含非平凡态射的范畴，就会对 Delta_c 与 $D$ 之间的变换施加自然性条件。我们称这样的变换为锥（cone），因为 Delta 的像是锥体或金字塔的顶点，而自然变换的分量形成锥体的侧边。$D$ 的像形成锥体的底部。
一般来说，为了构造一个锥，我们从定义模式的范畴 $I$ 开始。它是一个小范畴，通常还是有限范畴。我们选择一个从 $I$ 到 $C$ 的函子 $D$，并把它（或它的像）称为图式（diagram）。在 $C$ 中选择某个对象 c 作为锥的顶点。用它定义从 $I$ 到 $C$ 的常函子 Delta_c。从 Delta_c 到 $D$ 的自然变换就是我们的锥。对有限的 $I$ 来说，它只是一组把 c 连接到图式的态射；图式就是 $I$ 在 $D$ 下的像。
自然性要求这个图中所有三角形（也就是金字塔的侧面）都交换。确实，取 $I$ 中任意态射 f。函子 $D$ 把它映射为 $C$ 中的态射 D f，这个态射构成某个三角形的底边。常函子 Delta_c 把 f 映射到 c 上的恒等态射。Delta 把态射的两端压缩成同一个对象，于是自然性方块变成交换三角形。这个三角形的两条侧边就是自然变换的分量。
这就是一个锥。我们感兴趣的是通用锥，就像在积定义中选择通用对象一样。有许多方式可以处理它。例如，可以基于给定函子 $D$ 定义一个锥的范畴。这个范畴中的对象是锥。不过，并非 $C$ 中每个对象 c 都能成为锥的顶点，因为 Delta_c 和 $D$ 之间可能不存在自然变换。
为了使它成为范畴，还必须定义锥之间的态射。这些态射会完全由它们顶点之间的态射决定。但不是任意态射都可以。记住，在积的构造中，我们施加了条件：候选对象（顶点）之间的态射必须是投影的公共因子。例如：
p' = p . m
q' = q . m
val p1 = p compose m
val q1 = q compose m
这个条件在一般情形中翻译为：那些以分解态射为一边的三角形都交换。
我们把这些分解态射作为锥范畴中的态射。很容易检查这些态射确实可以组合，并且恒等态射也是分解态射。因此，锥形成范畴。
现在可以把通用锥定义为锥范畴中的终对象。终对象的定义说，从任意其他对象到该对象都有唯一态射。在我们的情形中，这意味着从任意其他锥的顶点，到通用锥的顶点，都存在唯一的分解态射。我们把这个通用锥称为图式 $D$ 的极限，记作 Lim D（在文献中，常会看到 Lim 符号下方有一个指向 $I$ 的左箭头）。作为简写，我们常常把这个锥的顶点称为极限（或极限对象）。
直觉是，极限把整个图式的性质体现在单个对象中。例如，我们那个双对象图式的极限就是两个对象的积。积（连同两个投影）包含关于两个对象的信息。而通用性意味着它没有额外垃圾。
12.1 作为自然同构的极限（Limit as a Natural Isomorphism）
这个极限定义仍然有些令人不满意。我的意思是，它可用，但仍然带着连接任意两个锥的三角形交换条件。如果能把它替换成某个自然性条件，会优雅得多。但该怎么做？
我们不再处理一个锥，而是处理整个锥的集合（事实上是范畴）。如果极限存在（先说清楚：并不保证存在），这些锥中有一个是通用锥。对每个锥，都有一个唯一分解态射，把它的顶点，称为 c，映射到通用锥的顶点，也就是 Lim D。（事实上，我可以省略“其他”这个词，因为恒等态射把通用锥映射到自身，并且平凡地通过自身分解。）让我重复重点：给定任意锥，都有一个特殊种类的唯一态射。我们有一个从锥到特殊态射的映射，而且它是一一映射。
这个特殊态射是 hom-set C(c, Lim D) 的成员。这个 hom-set 中的其他成员没那么幸运，因为它们不会分解锥的映射。我们想做的是，对每个 c，从集合 C(c, Lim D) 中选出一个态射，且这个态射满足特定交换条件。这听起来像是在定义自然变换吗？当然非常像！
但这个变换关联的是哪些函子？一个函子是把 c 映射到集合 C(c, Lim D) 的映射。它是从 $C$ 到 $Set$ 的函子，也就是把对象映射到集合。事实上，它是逆变函子。下面定义它在态射上的作用：取一个从 c' 到 c 的态射 f：
f :: c' -> c
我们的函子把 c' 映射到集合 C(c', Lim D)。为了定义这个函子在 f 上的作用，也就是提升 f，必须定义 C(c, Lim D) 与 C(c', Lim D) 之间的对应映射。所以选取 C(c, Lim D) 的一个元素 u，看看能否把它映射到 C(c', Lim D) 的某个元素。hom-set 的元素是态射，所以有：
u :: c -> Lim D
可以把 u 与 f 预组合，得到：
u . f :: c' -> Lim D
这正是 C(c', Lim D) 的元素。因此，我们确实找到了态射的映射：
contramap :: (c' -> c) -> (c -> LimD) -> (c' -> LimD)
contramap f u = u . f
def contramap[C, C1, D[_]](f: C1 => C, u: C => Lim[D]): C1 => Lim[D] =
u compose f
注意 c 与 c' 顺序的反转，这是逆变函子的特征。
为了定义自然变换，还需要另一个同样从 $C$ 到 $Set$ 的函子。但这次考虑的是锥的集合。锥只是自然变换，所以我们看的是自然变换集合 Nat(Delta_c, D)。从 c 到这个特定自然变换集合的映射是一个（逆变）函子。如何说明这一点？同样，定义它在态射上的作用：
f :: c' -> c
对 f 的提升，应该是两个从 $I$ 到 $C$ 的函子之间自然变换的映射：
Nat(Delta_c, D) -> Nat(Delta_c', D)
如何映射自然变换？每个自然变换都是一组态射的选择，也就是它的分量；$I$ 中每个元素对应一个态射。某个 alpha（Nat(Delta_c, D) 的成员）在 a（$I$ 中的对象）处的分量是态射：
alpha_a :: Delta_c a -> D a
或者，使用常函子 Delta 的定义：
alpha_a :: c -> D a
给定 f 和 alpha，必须构造一个 beta，它是 Nat(Delta_c', D) 的成员。它在 a 处的分量应该是态射：
beta_a :: c' -> D a
可以很容易从前者 alpha_a 得到后者 beta_a，只要用 f 预组合：
beta_a = alpha_a . f
相对容易证明，这些分量确实组合成一个自然变换。
给定态射 f，我们就按分量构造出了两个自然变换之间的映射。这个映射定义了如下函子的 contramap：
c -> Nat(Delta_c, D)
刚刚所做的是展示：我们有两个从 $C$ 到 $Set$ 的（逆变）函子。我没有做任何额外假设；这些函子总是存在。
顺便说一句，第一个函子在范畴论中扮演重要角色，讨论 Yoneda 引理时还会再见到它。任意范畴 $C$ 到 $Set$ 的逆变函子有一个名字：它们称为“预层”（presheaf）。这个函子称为可表示预层。第二个函子也是预层。
现在有了两个函子，就可以讨论它们之间的自然变换。因此，不再绕弯子，结论如下：
从 $I$ 到 $C$ 的函子 $D$ 有极限 Lim D，当且仅当刚刚定义的两个函子之间存在自然同构：
C(c, Lim D) ~= Nat(Delta_c, D)
提醒一下，自然同构是指每个分量都是同构，也就是可逆态射的自然变换。
我不会逐步证明这个陈述。过程相当直接，只是有些冗长。处理自然变换时，通常关注它们的分量，而分量是态射。在这个例子中，由于两个函子的目标都是 $Set$，自然同构的分量将是函数。这些是高阶函数，因为它们从 hom-set 到自然变换集合。再次，你可以通过考虑函数对参数做什么来分析函数：这里的参数会是态射，也就是 C(c, Lim D) 的成员；结果会是自然变换，也就是 Nat(Delta_c, D) 的成员，或者说我们称为锥的东西。这个自然变换又有自己的分量，而这些分量也是态射。所以一路向下都是态射；如果能跟踪它们，就能证明这个陈述。
最重要的结果是，这个同构的自然性条件，正是锥映射的交换条件。
作为后续内容的预告，提一下：集合 Nat(Delta_c, D) 可以被看作函子范畴中的 hom-set；因此，我们的自然同构关联了两个 hom-set，这指向一种更一般的关系，称为伴随。
12.2 极限的例子（Examples of Limits）
我们已经看到，范畴积是由那个称为 2 的简单范畴生成的图式的极限。
还有一个更简单的极限例子：终对象。第一反应也许是认为单对象范畴会导向终对象，但事实比这更极端：终对象是由空范畴生成的极限。来自空范畴的函子不选择任何对象，所以一个锥收缩成只有顶点。通用锥就是这样一个孤零零的顶点：从任意其他顶点到它都有唯一态射。你会认出这正是终对象的定义。
下一个有趣的极限称为等化子（equalizer）。它由一个双元素范畴生成，这个范畴有两个平行态射从一个对象指向另一个对象（并且像往常一样，还有恒等态射）。这个范畴在 $C$ 中选择一个图式，包含两个对象 a 和 b，以及两个态射：
f :: a -> b
g :: a -> b
val f: A => B
val g: A => B
要在这个图式上构造锥，必须添加顶点 c 和两个投影：
p :: c -> a
q :: c -> b
val p: C => A
val q: C => B
我们有两个必须交换的三角形：
q = f . p
q = g . p
q == f compose p
q == g compose p
这告诉我们，q 由其中一个等式唯一决定，比如 q = f . p，因此可以把它从图中省略。于是只剩下一个条件：
f . p = g . p
f compose p == g compose p
理解它的一种方式是，如果把注意力限制在 $Set$ 中，函数 p 的像会选择 a 的一个子集。当限制在这个子集上时，函数 f 和 g 相等。
例如，取 a 为由坐标 x 和 y 参数化的二维平面。取 b 为实数线，并定义：
f (x, y) = 2 * y + x
g (x, y) = y - x
def f(x: Double, y: Double) = 2 * y + x
def g(x: Double, y: Double) = y - x
这两个函数的等化子是实数集合（顶点 c）以及函数：
p t = (t, (-2) * t)
def p(t: Double) = (t, (-2) * t)
注意，p t 在二维平面中定义了一条直线。沿着这条直线，两个函数相等。
当然，还有其他集合 c' 和函数 p' 也可能导向等式：
f . p' = g . p'
f compose p1 == g compose p1
但它们都会唯一地通过 p 分解。例如，可以取单元素集合 () 作为 c'，并取函数：
p' () = (0, 0)
def p1: Unit => (Double, Double) = _ => (0, 0)
这是一个好锥，因为 f(0, 0) = g(0, 0)。但它不是通用的，因为它通过 h 唯一分解：
p' = p . h
val p1 = p compose h
其中：
h () = 0
def h(x: Unit) = 0.0
因此，等化子可用于求解 f x = g x 这种类型的方程。但它更加一般，因为它用对象和态射定义，而不是用代数方式定义。
另一个更一般的“解方程”思想体现在另一个极限中，也就是拉回（pullback）。这里仍然有两个想要相等的态射，但这一次它们的定义域不同。我们从形状为 1 -> 2 <- 3 的三对象范畴开始。这个范畴对应的图式包含三个对象 a、b 和 c，以及两个态射：
f :: a -> b
g :: c -> b
val f: A => B
val g: C => B
这个图式常称为余张量图（cospan）。
建立在这个图式上的锥包含顶点 d 和三个态射：
p :: d -> a
q :: d -> c
r :: d -> b
val p: D => A
val q: D => C
val r: D => B
交换条件告诉我们，r 完全由其他态射决定，可以从图中省略。因此只剩下如下条件：
g . q = f . p
g compose q == f compose p
拉回就是这个形状的通用锥。
同样，如果把关注点缩小到集合，可以把对象 d 想成由来自 a 与 c 的元素对组成，这些元素对满足：f 作用在第一个分量上，等于 g 作用在第二个分量上。如果这仍然太一般，可以考虑特殊情形：g 是常函数，比如 g _ = 1.23（假设 b 是实数集合）。这时你真正求解的是方程：
f x = 1.23
f(x) == 1.23
在这种情况下，c 的选择无关紧要（只要它不是空集），所以可以取它为单元素集合。集合 a 可以是三维向量集合，而 f 是向量长度。那么拉回就是由 pair (v, ()) 组成的集合，其中 v 是长度为 1.23 的向量（方程 sqrt(x^2 + y^2 + z^2) = 1.23 的解），而 () 是单元素集合中的虚设元素。
但拉回还有更一般的应用，也包括在编程中。例如，考虑把 C++ 类看作一个范畴，其中态射是连接子类到父类的箭头。我们把继承视为传递性质：如果 C 继承 B，B 继承 A，那么就说 C 继承 A（毕竟，期待 A 指针的地方可以传入 C 指针）。此外，假设 C 继承 C，所以每个类都有恒等箭头。这样，子类关系就与子类型关系对齐。C++ 还支持多重继承，所以可以构造菱形继承图，其中两个类 B 和 C 继承 A，第四个类 D 多重继承 B 和 C。通常情况下，D 会得到两份 A，这很少是人们想要的；但可以使用虚继承，让 D 中只有一份 A。
D 在这个图中作为拉回意味着什么？这意味着任何多重继承自 B 和 C 的类 E，同时也是 D 的子类。这在 C++ 中不能直接表达，因为 C++ 的子类型是名义化的（C++ 编译器不会推断这种类关系；它需要“鸭子类型”）。但可以跳出子类型关系，转而问从 E 到 D 的转换是否安全。如果 D 是 B 和 C 的最小组合，没有额外数据，也没有重写方法，那么这个转换就是安全的。当然，如果 B 和 C 的某些方法存在名称冲突，就不会有拉回。
拉回在类型推断中也有更高级的用途。经常需要统一两个表达式的类型。例如，假设编译器想推断函数的类型：
twice f x = f (f x)
它会为所有变量和子表达式分配初步类型。特别是，它会分配：
f :: t0
x :: t1
f x :: t2
f (f x) :: t3
由此推导出：
twice :: t0 -> t1 -> t3
它还会根据函数应用规则得出一组约束：
t0 = t1 -> t2 -- because f is applied to x
t0 = t2 -> t3 -- because f is applied to (f x)
这些约束必须通过寻找一组类型（或类型变量）来统一：把它们替换进两个表达式中的未知类型后，应产生相同类型。其中一个替换是：
t1 = t2 = t3 = Int
twice :: (Int -> Int) -> Int -> Int
但显然这不是最一般的替换。最一般替换可通过拉回获得。这里不展开细节，因为它们超出了本书范围，但你可以说服自己，结果应该是：
twice :: (t -> t) -> t -> t
其中 t 是自由类型变量。
12.3 余极限（Colimits）
就像范畴论中的所有构造一样，极限在反范畴中有其对偶形象。当反转锥中所有箭头方向时，得到余锥（co-cone），其中通用的那个称为余极限（colimit）。注意，反转也会影响分解态射；它现在从通用余锥流向任意其他余锥。
余极限的典型例子是余积，它对应由 2 生成的图式，而 2 正是我们在定义积时使用的那个范畴。
积与余积都体现了一对对象的本质，只是方式不同。
正如终对象是极限，始对象是对应空范畴图式的余极限。
拉回的对偶称为推出（pushout）。它基于一个称为张量图（span）的图式，由范畴 1 <- 2 -> 3 生成。
12.4 连续性（Continuity）
我之前说过，函子接近于范畴之间连续映射的概念，因为它们从不破坏已有连接（态射）。从范畴 $C$ 到 $C'$ 的连续函子 $F$ 的实际定义，包括函子保持极限这一要求。$C$ 中每个图式 $D$ 都可以通过简单组合两个函子，映射到 $C'$ 中的图式 F . D。$F$ 的连续性条件说：如果图式 $D$ 有极限 Lim D，那么图式 F . D 也有极限，并且它等于 F(Lim D)。
注意，由于函子把态射映射到态射，也把组合映射到组合，锥的像总是锥。交换三角形总被映射成交换三角形（函子保持组合）。分解态射也一样：分解态射的像仍然是分解态射。所以每个函子几乎都是连续的。可能出错的是唯一性条件。在 $C'$ 中，分解态射可能不唯一。$C'$ 中也可能存在 $C$ 中没有的其他“更好锥”。
hom 函子是连续函子的例子。回忆一下，hom 函子 C(a, b) 在第一个变量上逆变，在第二个变量上协变。换句话说，它是一个函子：
C^op x C -> Set
当固定第二个参数时，hom-set 函子（也就是可表示预层）把 $C$ 中的余极限映射为 $Set$ 中的极限；当固定第一个参数时，它把极限映射为极限。
在 Haskell 中，hom 函子是把任意两个类型映射到函数类型的映射，所以它只是一个参数化函数类型。当固定第二个参数，例如固定为 String 时，得到逆变函子：
newtype ToString a = ToString (a -> String)
instance Contravariant ToString where
contramap f (ToString g) = ToString (g . f)
trait Contravariant[F[_]] {
def contramap[A, B](fa: F[A])(f: B => A): F[B]
}
case class ToString[A](f: A => String) extends AnyVal
implicit val contravariant = new Contravariant[ToString] {
def contramap[A, B](fa: ToString[A])(f: B => A): ToString[B] =
ToString(fa.f compose f)
}
连续性意味着，当 ToString 应用于一个余极限，例如余积 Either b c 时，会产生一个极限；在这个例子中，就是两个函数类型的积：
ToString (Either b c) ~ (b -> String, c -> String)
ToString[Either[B, C]] ~ (B => String, C => String)
确实，任意来自 Either b c 的函数都实现为带两个分支的 case 语句，而这两个分支由一对函数分别处理。
类似地，当固定 hom-set 的第一个参数时，得到熟悉的 reader 函子。它的连续性意味着，例如任何返回积的函数都等价于函数的积；特别是：
r -> (a, b) ~ (r -> a, r -> b)
R => (A, B) ~ (R => A, R => B)
我知道你在想什么：想出这些东西并不需要范畴论。你是对的！不过，我仍然觉得惊人的是，这类结果可以从第一原则推出，完全不诉诸比特与字节、处理器架构、编译器技术，甚至 lambda 演算。
如果你好奇“极限”和“连续性”这些名字从何而来，它们是微积分中相应概念的推广。在微积分中，极限和连续性用开邻域定义。定义拓扑的开集形成一个范畴（一个偏序集）。
12.5 挑战（Challenges）
- 在 C++ 类的范畴中，你会如何描述推出？
- 说明恒等函子
Id :: C -> C的极限是始对象。 - 给定集合的子集形成一个范畴。在这个范畴中，如果第一个集合是第二个集合的子集，就定义一个连接两个集合的态射。这样的范畴中，两个集合的拉回是什么？推出是什么？始对象和终对象是什么？
- 你能猜出余等化子（coequalizer）是什么吗？
- 说明在带终对象的范畴中，朝向终对象的拉回就是积。
- 类似地，说明从始对象出发的推出（如果存在）就是余积。