第 19 章：自由/遗忘伴随（Free/Forgetful Adjunctions）
原文：Bartosz Milewski, Category Theory for Programmers, Scala Edition, Chapter 19. 原书 PDF、
.tex源文件及相关图像采用 CC BY-SA 4.0；本译文按同一许可发布。
自由构造是伴随的一个强大应用。自由函子被定义为遗忘函子的左伴随。遗忘函子通常是相当简单的函子，它会遗忘某些结构。例如，许多有趣的范畴都建立在集合之上。但抽象这些集合的范畴对象没有内部结构，它们没有元素。尽管如此，这些对象通常仍携带着集合的记忆：从给定范畴 $C$ 到 $Set$ 存在一个映射，也就是一个函子。与 $C$ 中某个对象对应的集合，称为它的底层集合（underlying set）。
幺半群就是这样一种具有底层集合的对象，也就是元素集合。有一个从幺半群范畴 $Mon$ 到集合范畴的遗忘函子 $U$，它把幺半群映射到底层集合。它还把幺半群态射（同态）映射为集合之间的函数。
我喜欢把 $Mon$ 想象成有双重人格。一方面，它是一堆带有乘法和单位元的集合。另一方面，它是一个由无特征对象组成的范畴，这些对象的唯一结构编码在它们之间的态射中。每个保持乘法和单位元的集合函数，都会产生 $Mon$ 中的一个态射。
需要记住的几点：
- 可能有许多幺半群映射到同一个集合。
- 幺半群态射的数量少于（或最多等于）它们底层集合之间的函数数量。
作为遗忘函子 $U$ 左伴随的函子 $F$，就是从生成元集合构造自由幺半群的自由函子。这个伴随来自我们之前讨论过的自由幺半群通用构造1。
用 hom-set 表示，这个伴随可以写作：
Mon(F x, m) ~= Set(x, U m)
这个在 $x$ 和 $m$ 上自然的同构告诉我们：
- 对于由 $x$ 生成的自由幺半群 $F x$ 与任意幺半群 $m$ 之间的每个幺半群同态，都存在一个唯一函数，把生成元集合 $x$ 嵌入 $m$ 的底层集合。它是 $Set(x, U m)$ 中的一个函数。
- 对于每个把 $x$ 嵌入某个 $m$ 的底层集合的函数，都存在一个唯一幺半群态射，从由 $x$ 生成的自由幺半群到幺半群 $m$。（这就是我们在通用构造中称为 $h$ 的态射。）
直觉是，$F x$ 是可以基于 $x$ 构造出的“最大”幺半群。如果能看进幺半群内部，我们会看到，属于 $Mon(F x, m)$ 的任意态射，都会把这个自由幺半群嵌入另一个幺半群 $m$ 中。它这样做时，可能会等同某些元素。特别地，它会把 $F x$ 的生成元（也就是 $x$ 的元素）嵌入 $m$。伴随说明，右边由 $Set(x, U m)$ 中函数给出的 $x$ 的嵌入，会唯一决定左边的幺半群嵌入，反过来也一样。
在 Haskell 中，列表数据结构是一个自由幺半群（带有一些注意事项：参见 Dan Doel 的博客文章2）。列表类型 [a] 是以类型 a 表示生成元集合的自由幺半群。例如，类型 [Char] 包含单位元，也就是空列表 []；还包含像 ['a']、['b'] 这样的单元素列表，也就是自由幺半群的生成元。其余元素都通过应用“积”生成。在这里，两个列表的积只是把一个列表追加到另一个列表后面。追加满足结合律并且有单位元（也就是说有一个中性元素，这里是空列表）。由 Char 生成的自由幺半群，不过就是由 Char 中字符组成的所有字符串集合。在 Haskell 中它称为 String：
type String = [Char]
type String = List[Char]
type 定义的是类型同义词，也就是给已有类型起另一个名字。
另一个有趣例子是由单个生成元构造出的自由幺半群。它是 unit 列表类型 [()]。它的元素包括 []、[()]、[(), ()] 等等。每个这样的列表都可以用一个自然数来描述，也就是它的长度。unit 列表中没有编码更多信息。追加两个这样的列表，会产生一个新列表，其长度是组成它的两个列表长度之和。很容易看出，类型 [()] 同构于自然数（带零）的加法幺半群。下面两个互为逆的函数见证了这个同构：
toNat :: [()] -> Int
toNat = length
toLst :: Int -> [()]
toLst n = replicate n ()
def toNat: List[Unit] => Int =
_.length
def toLst: Int => List[Unit] =
n => List.fill(n)(())
为简单起见，我使用了 Int 而不是 Natural，但思想相同。函数 replicate 会创建一个长度为 n 的列表，并用给定值预填充；这里给定值是 unit。
19.1 一些直觉（Some Intuitions）
下面是一些不太严密的论证。这类论证远谈不上严格，但有助于形成直觉。
为了获得关于自由/遗忘伴随的直觉，记住函子和函数天生是有损的会有帮助。函子可能会折叠多个对象和态射，函数可能会把集合中的多个元素团在一起。它们的像也可能只覆盖陪域的一部分。
$Set$ 中一个“普通”hom-set 会包含整个函数谱系：从损失最少的函数开始（例如单射，或者可能是同构），一直到把整个定义域折叠成单个元素的常函数（如果存在这样的元素）。
我倾向于把任意范畴中的态射也想成有损的。这只是一个心智模型，但很有用，尤其是在思考伴随时，特别是其中一个范畴是 $Set$ 的那些伴随。
形式上，我们只能谈论可逆态射（同构）和不可逆态射。后者可以被想成有损。还有单态射和满态射的概念，它们推广了单射（不折叠）和满射（覆盖整个陪域）的想法，但一个态射可能既是单态射又是满态射，却仍然不可逆。
在自由 $\dashv$ 遗忘伴随中，左边有约束更多的范畴 $C$，右边有约束更少的范畴 $D$。$C$ 中的态射“更少”，因为它们必须保持某些额外结构。在 $Mon$ 的情况下，它们必须保持乘法和单位元。$D$ 中的态射不需要保持那么多结构，所以它们“更多”。
当把遗忘函子 $U$ 应用于 $C$ 中对象 $c$ 时，我们把它想成揭示 $c$ 的“内部结构”。事实上，如果 $D$ 是 $Set$，我们把 $U$ 看作定义了 $c$ 的内部结构，也就是它的底层集合。（在任意范畴中，除了通过对象与其他对象之间的连接，我们无法谈论对象内部；但这里我们只是在建立直觉。）
如果用 $U$ 映射两个对象 $c'$ 和 $c$，一般而言，我们预期 hom-set $C(c', c)$ 的映射只会覆盖 $D(U c', U c)$ 的一个子集。这是因为 $C(c', c)$ 中的态射必须保持额外结构，而 $D(U c', U c)$ 中的态射不必如此。
但由于伴随被定义为特定 hom-set 的同构，我们必须非常挑剔地选择 $c'$。在伴随中，$c'$ 并非从 $C$ 中任意位置选出，而是从自由函子 $F$ 的（大概更小的）像中选出：
C(F d, c) ~= D(d, U c)
因此，$F$ 的像必须由一些对象组成，这些对象有大量态射通向任意 $c$。事实上，从 $F d$ 到 $c$ 的保结构态射，必须和从 $d$ 到 $U c$ 的不保结构态射一样多。这意味着 $F$ 的像必须由本质上没有结构的对象组成（这样态射就没有结构需要保持）。这种“无结构”对象称为自由对象。
在幺半群例子中，自由幺半群除了由单位元和结合律生成的结构之外，没有其他结构。除此之外，所有乘法都会产生全新元素。
在自由幺半群中，2 * 3 不是 6，而是一个新元素 [2, 3]。因为 [2, 3] 和 6 没有被等同，从这个自由幺半群到任意其他幺半群 $m$ 的态射就可以分别映射它们。当然，它也可以把 [2, 3] 和 6（它们的积）都映射到 $m$ 中同一个元素。或者在加法幺半群中等同 [2, 3] 和 5（它们的和），如此等等。不同的等同会给出不同幺半群。
这导向另一个有趣直觉：自由幺半群并不执行幺半运算，而是累积传给它的参数。它们并不把 2 和 3 相乘，而是把 2 和 3 记在列表中。这种方案的优点是，我们不必预先指定将使用哪种幺半运算。我们可以继续累积参数，直到最后才把某个运算符应用到结果上。也正是在那时，我们可以选择应用哪个运算符。可以把这些数相加，或者相乘，或者执行模 2 加法，等等。自由幺半群把表达式的创建与求值分离开来。谈到代数时，我们还会再次看到这个想法。
这个直觉会推广到其他更复杂的自由构造。例如，可以在求值之前累积整棵表达式树。这种做法的优点是，我们可以变换这些树，让求值更快或更少消耗内存。例如，在实现矩阵微积分时就会这样做；如果急切求值，会导致大量临时数组分配，用来存储中间结果。
19.2 挑战（Challenges）
- 考虑一个由单元素集合作为生成元构造出的自由幺半群。说明从这个自由幺半群到任意幺半群 $m$ 的态射，与从单元素集合到 $m$ 的底层集合的函数之间存在一一对应。