第 3 章：大大小小的范畴（Categories Great and Small）

原文：Bartosz Milewski, Category Theory for Programmers, Scala Edition, Chapter 3. 原书 PDF、.tex 源文件及相关图像采用 CC BY-SA 4.0；本译文按同一许可发布。

通过研究各种例子，才能真正欣赏范畴。范畴有各种形状和规模，也常常出现在意料之外的地方。我们从一些非常简单的例子开始。

3.1 没有对象（No Objects）

最平凡的范畴有零个对象，因此也有零个态射。它本身是一个很悲伤的范畴，但在其他范畴的上下文中可能很重要，例如在所有范畴构成的范畴中，是的，确实有这么一个东西。如果你认为空集有意义，那么为什么空范畴不能有意义？

3.2 简单图（Simple Graphs）

只要用箭头连接对象，就可以构建范畴。可以想象从任意有向图开始，通过添加更多箭头把它变成一个范畴。首先，在每个节点上添加恒等箭头。然后，对于任意两个箭头，只要一个箭头的终点与另一个箭头的起点重合，换句话说，只要它们是可组合（composable）的，就添加一个新箭头来作为它们的组合。每次添加新箭头后，还必须考虑它与任何其他箭头（恒等箭头除外）以及它自身的组合。通常最终会得到无限多个箭头，但这没关系。

也可以换一种方式看这个过程：你正在创建一个范畴，它为图中的每个节点配备一个对象，并把所有可能的可组合图边链（chains）作为态射。甚至可以把恒等态射看作长度为零的链的特殊情况。

由给定图生成的这种范畴称为自由范畴（free category）。它是自由构造的一个例子。自由构造是一种过程：通过添加满足法则所需的最少项目，补全给定结构。这里要满足的是范畴法则。以后会看到更多这样的例子。

3.3 序（Orders）

现在来看完全不同的东西！在某种范畴中，态射是对象之间的关系：小于等于关系。检查一下它是否真的是范畴。我们有恒等态射吗？每个对象都小于等于它自身，成立！有组合吗？如果 $a \leq b$ 且 $b \leq c$，那么 $a \leq c$，成立！组合满足结合律吗？成立！带有这种关系的集合称为预序（preorder），所以预序确实是范畴。

还可以有一种更强的关系，它满足附加条件：如果 $a \leq b$ 且 $b \leq a$，那么 $a$ 必须与 $b$ 相同。这称为偏序（partial order）。

最后，如果要求任意两个对象之间总有某种方向的关系，就得到线性序（linear order）或全序（total order）。

我们把这些有序集刻画成范畴。预序是这样一种范畴：从任意对象 $a$ 到任意对象 $b$ 最多只有一个态射。这类范畴还有另一个名字：“薄范畴”（thin category）。预序就是薄范畴。

在范畴 $C$ 中，从对象 $a$ 到对象 $b$ 的态射集合称为hom-set，写作 $C(a, b)$，有时也写作 $Hom_C(a, b)$。所以，预序中的每个 hom-set 要么为空，要么是单元素集合。这也包括 hom-set $C(a, a)$，也就是从 $a$ 到 $a$ 的态射集合。在任何预序中，它都必须是单元素集合，只包含恒等态射。不过，预序中可以有环。偏序中禁止环。

能够识别预序、偏序和全序非常重要，因为这关系到排序。快速排序、冒泡排序、归并排序等排序算法只能在全序上正确工作。偏序可以用拓扑排序处理。

3.4 幺半群作为集合（Monoid as Set）

幺半群是一个简单到令人尴尬、却又惊人强大的概念。它是基础算术背后的概念：加法和乘法都会形成幺半群。幺半群在编程中无处不在。它们表现为字符串、列表、可折叠数据结构、并发编程中的 future、函数式响应式编程中的事件，等等。

传统上，幺半群定义为带有二元运算的集合。这个运算只需要满足两点：它是结合的，并且存在一个特殊元素，相对于这个运算表现为单位元。

例如，包含零的自然数在加法下形成幺半群。结合律意味着：

$$ (a + b) + c = a + (b + c) $$

换句话说，加数字时可以省略括号。

中性元素是零，因为：

$$ 0 + a = a $$

并且：

$$ a + 0 = a $$

第二个等式是冗余的，因为加法是交换的，也就是 $a + b = b + a$；但交换性不是幺半群定义的一部分。例如，字符串连接并不交换，却仍然形成幺半群。顺便说一句，字符串连接的中性元素是空字符串，它可以附加到字符串任意一侧而不改变该字符串。

在 Scala 中，可以为幺半群定义一个 trait：某个类型 M 拥有中性元素 empty 和二元运算 combine。

trait Monoid[M] {
  def combine(m1: M, m2: M): M
  def empty: M
}

注意，在 Scala 类型系统中，也无法直接表达 empty 和 combine 的幺半群性质，也就是 empty 是中性元素、combine 满足结合律。这些性质需要程序员确保。

Scala 的 type class 风格通常通过 trait 与隐式值组合表达。定义新类型时，不必提前声明它属于某个 type class。可以稍后再为给定类型提供相应实例。例如，可以把 String 声明为一个幺半群，提供 empty 和 combine 的实现：

object Monoid {
  implicit val stringMonoid: Monoid[String] = new Monoid[String] {
    def combine(m1: String, m2: String): String = m1 + m2
    def empty: String = ""
  }
}

这里复用了字符串连接运算符 +。空字符串则是字符串连接的中性元素。

值得强调的是，在函数式编程中，经常会表达函数本身的相等，而不仅仅表达函数产生的值相等。概念上，这不同于说“对任意两个输入字符串，combine 和字符串连接产生相同输出”。后者称为外延（extensional）相等。由于参数值有时称为点（points），例如函数 $f$ 在点 $x$ 处的值，所以这也称为逐点相等。不指定参数的函数相等称为无点（point-free）。顺便说一句，无点等式常常涉及函数组合，而函数组合又用一个点来表示，这对初学者可能有点混乱。

C++ 中最接近声明幺半群的做法，是使用 C++20 标准的 concept 功能：

template<typename T>
struct mempty;

template<typename T>
T mappend(T, T) = delete;

template<typename M>
concept Monoid = requires (M m) {
    { mempty<M>::value() } -> std::same_as<M>;
    { mappend(m, m) } -> std::same_as<M>;
};

第一个定义是一个结构，用来为每个特化保存中性元素。

关键字 delete 表示没有定义默认值，必须逐案指定。类似地，mappend 也没有默认值。

Monoid concept 会测试给定类型 M 是否存在合适的 mempty 和 mappend 定义。

要实例化 Monoid concept，可以提供相应特化和重载：

template<>
struct mempty<std::string> {
    static std::string value() { return ""; }
};

template<>
std::string mappend(std::string s1, std::string s2) {
    return s1 + s2;
}

3.5 幺半群作为范畴（Monoid as Category）

上面是用集合元素定义幺半群的“熟悉”方式。但如你所知，在范畴论中，我们试图远离集合及其元素，转而谈论对象和态射。因此稍微改变视角，把二元运算的应用想成在集合中“移动”或“平移”东西。

例如，有一种操作是给每个自然数加 5。它把 0 映射到 5，把 1 映射到 6，把 2 映射到 7，以此类推。这是在自然数集合上定义的一个函数。这很好：我们有一个函数和一个集合。一般来说，对于任意数 $n$，都有一个加 $n$ 的函数，也就是 $n$ 的“加法器”。

加法器如何组合？“加 5”的函数与“加 7”的函数组合，得到“加 12”的函数。所以，加法器的组合可以等价于加法规则。这也很好：可以用函数组合替换加法。

不过还有更多：还存在中性元素零的加法器。加零不会移动任何东西，所以它就是自然数集合上的恒等函数。

我完全可以不给你传统加法规则，而是给你加法器的组合规则，并且不会丢失任何信息。注意，加法器的组合满足结合律，因为函数组合满足结合律；并且我们有对应恒等函数的零加法器。

敏锐的读者也许注意到，从整数到加法器的映射来自 combine 类型签名的另一种解释：M => (M => M)。它告诉我们，combine 会把幺半群集合中的一个元素映射为一个作用在该集合上的函数。

现在，请忘掉你正在处理自然数集合，只把它想成一个单独对象，一个带着一堆态射（加法器）的团块。幺半群是单对象范畴。事实上，monoid 这个名字来自希腊语 mono，意思是“单个”。每个幺半群都可以描述为一个单对象范畴，其中有一组态射，并且它们遵循相应的组合规则。

字符串连接是一个有趣情况，因为可以选择定义右追加器，也可以定义左追加器，或者说前置器。两个模型的组合表互为镜像。你很容易说服自己：在 "foo" 之后追加 "bar"，对应于先前置 "bar" 再前置 "foo"。

你可能会问：每个范畴式幺半群，也就是每个单对象范畴，是否都定义一个唯一的“集合加二元运算”式幺半群？事实是，我们总能从单对象范畴中提取一个集合。这个集合就是态射集合，也就是例子中的加法器集合。换句话说，我们有范畴 $M$ 中单个对象 $m$ 的 hom-set：$M(m, m)$。可以很容易在这个集合上定义二元运算：两个集合元素的幺半群积，就是对应态射组合所对应的元素。如果给我两个 $M(m, m)$ 的元素，分别对应 $f$ 和 $g$，它们的积将对应组合 $f \circ g$。这个组合总是存在，因为这些态射的源和目标都是同一个对象。它根据范畴法则满足结合律。恒等态射就是这个积的中性元素。因此，我们总能从范畴幺半群恢复集合幺半群。就所有实际目的而言，它们是一回事。

图 3.1 幺半群 hom-set 既可以看作态射，也可以看作集合中的点。

这里还有一个数学家可能会挑剔的小问题：态射不一定形成集合。在范畴世界中，有些东西比集合还大。任意两个对象之间的态射都形成集合的范畴称为局部小范畴。正如承诺的，我会基本忽略这些微妙之处，但还是应该把它记在这里。

范畴论中许多有趣现象都源于这样一个事实：hom-set 的元素既可以看作态射，遵循组合规则；也可以看作集合中的点。在这里，范畴 $M$ 中态射的组合转化为集合 $M(m, m)$ 中的幺半群积。

挑战

1. 从下面这些图生成自由范畴：

   • 一个节点、没有边的图。
   • 一个节点、一条有向边的图。提示：这条边可以与自身组合。
   • 两个节点，并且它们之间只有一个箭头的图。
   • 一个节点，并且有 26 条箭头，分别用字母表中的 a、b、c、...、z 标记。

2. 下面分别是哪种序？

   • 带有包含关系的集合之集：如果 $A$ 的每个元素也是 $B$ 的元素，就说 $A$ 包含于 $B$。
   • C++ 类型和如下子类型关系：如果指向 T1 的指针可以传给期待指向 T2 的指针的函数，并且不会触发编译错误，那么 T1 是 T2 的子类型。

3. 考虑 Bool 是由 True 和 False 两个值组成的集合。证明它分别关于 &&（AND）和 ||（OR）形成两个集合论意义上的幺半群。

4. 把带 AND 运算符的 Bool 幺半群表示为范畴：列出态射以及它们的组合规则。

5. 把模 3 加法表示为一个幺半群范畴。