第 13 章：自由幺半群（Free Monoids）

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

幺半群在范畴论和编程中都是重要概念。范畴对应强类型语言，幺半群对应无类型语言。这是因为在幺半群中，可以组合任意两个箭头，正如在无类型语言中可以组合任意两个函数一样（当然，执行程序时最终可能得到运行时错误）。

我们已经看到，幺半群可以描述为只有一个对象的范畴，其中所有逻辑都编码在态射组合规则中。这个范畴模型与更传统的集合论幺半群定义完全等价；在集合论定义中，我们把集合中的两个元素“相乘”得到第三个元素。这个“乘法”过程还可以进一步拆解为：先形成两个元素的 pair，然后把这个 pair 与某个已有元素，也就是它们的“积”，等同起来。

如果放弃乘法的第二部分，也就是不再把 pair 与已有元素等同，会发生什么？例如，可以从任意集合开始，形成所有可能的元素对，并把它们称为新元素。然后把这些新元素与所有可能元素继续配对，如此反复。这是一个链式反应，我们会不断添加新元素，永远不会停止。结果是一个无限集合，它几乎是一个幺半群。

但幺半群还需要单位元和结合律。没问题，可以加入一个特殊单位元，并把某些 pair 等同起来，只做足够支持单位律和结合律的等同。

来看一个简单例子。先从两个元素的集合 {a, b} 开始。我们把它们称为自由幺半群的生成元。首先，加入一个特殊元素 e 作为单位元。接下来，加入所有元素对，并把它们称为“积”。a 和 b 的积就是 pair (a, b)。b 和 a 的积是 (b, a)，a 和 a 的积是 (a, a)，b 和 b 的积是 (b, b)。还可以形成带 e 的 pair，例如 (a, e)、(e, b) 等，但我们会把它们分别等同为 a、b 等。所以在这一轮中，只会加入 (a, a)、(a, b)、(b, a) 和 (b, b)，得到集合 {e, a, b, (a, a), (a, b), (b, a), (b, b)}。

下一轮会继续加入元素，例如 (a, (a, b))、((a, b), a) 等。此时必须确保结合律成立，所以要把 (a, (b, a)) 与 ((a, b), a) 等同起来。换句话说，我们不需要内部括号。

你可以猜到这个过程的最终结果：我们会创建所有可能由 a 和 b 组成的列表。事实上，如果把 e 表示为空列表，就能看到我们的“乘法”只不过是列表连接。

这种构造不断生成所有可能的元素组合，并执行最少数量的等同，也就是只做足以维护定律的等同，称为自由构造（free construction）。我们刚刚做的事情，就是从生成元集合 {a, b} 构造自由幺半群。

13.1 Haskell 中的自由幺半群（Free Monoid in Haskell）

Haskell 中的双元素集合等价于类型 Bool，由这个集合生成的自由幺半群等价于类型 [Bool]（Bool 的列表）。（我有意忽略无限列表带来的问题。）

Haskell 中的幺半群由类型类定义：

class Monoid m where
    mempty :: m
    mappend :: m -> m -> m

trait Monoid[M] {
  def mempty: M
  def mappend(m1: M, m2: M): M
}

这只是说，每个 Monoid 都必须有一个中性元素，称为 mempty，以及一个二元函数（乘法），称为 mappend。单位律和结合律无法在 Haskell 中表达，必须由程序员在每次实例化幺半群时验证。

任意类型的列表都形成幺半群，这个事实由下面的实例定义描述：

instance Monoid [a] where
    mempty = []
    mappend = (++)

object Monoid {
  implicit def listMonoid[A]: Monoid[List[A]] = new Monoid[List[A]] {
    def mempty: List[A] = List()
    def mappend(m1: List[A], m2: List[A]): List[A] = m1 ++ m2
  }
}

它说明空列表 [] 是单位元，列表连接 (++) 是二元运算。

如我们所见，类型 a 的列表对应一个自由幺半群，其中集合 a 作为生成元。带乘法的自然数集合不是自由幺半群，因为我们等同了大量乘积。比如比较：

2 * 3 = 6
[2] ++ [3] = [2, 3] -- not the same as [6]

2 * 3 == 6
List(2) ++ List(3) == List(2, 3)

这很简单，但问题是：能否在范畴论中执行这种自由构造，在那里我们不允许观察对象内部？我们会使用老工具：通用构造。

第二个有趣问题是：任意幺半群能否都通过从某个自由幺半群出发，并等同比定律所要求的最少数量更多的元素而得到？我会说明，这可以直接从通用构造推出。

13.2 自由幺半群的通用构造（Free Monoid Universal Construction）

如果你还记得之前关于通用构造的经验，可能会注意到，它并不是真的在构造某物，而是选择一个最符合给定模式的对象。所以，如果想用通用构造“构造”自由幺半群，就必须考虑一大堆幺半群，并从中选出一个。我们需要整个幺半群范畴来选择。但幺半群形成范畴吗？

先把幺半群看作配有额外结构的集合，这些结构由单位元和乘法定义。我们选择保持幺半结构的函数作为态射。这种保持结构的函数称为同态（homomorphism）。幺半群同态必须把两个元素的积映射为这两个元素的像的积：

h (a * b) = h a * h b

h(a * b) == h(a) * h(b)

并且必须把单位元映射为单位元。

例如，考虑一个从整数列表（带连接）到整数（带乘法）的同态。如果把 [2] 映射为 2，把 [3] 映射为 3，就必须把 [2, 3] 映射为 6，因为连接：

[2] ++ [3] = [2, 3]

List(2) ++ List(3) == List(2, 3)

会变成乘法：

2 * 3 = 6

2 * 3 == 6

现在忘掉单个幺半群的内部结构，只把它们看作带有相应态射的对象。这样得到幺半群范畴 $Mon$。

好吧，在忘掉内部结构之前，先注意一个重要性质。$Mon$ 中每个对象都可以平凡地映射为一个集合，也就是它的元素集合。这个集合称为底层集合。事实上，不仅可以把 $Mon$ 的对象映射到集合，也可以把 $Mon$ 的态射（同态）映射到函数。这同样看起来有些平凡，但很快就会有用。这个从 $Mon$ 到 $Set$ 的对象与态射映射实际上是函子。由于这个函子“遗忘”了幺半结构，一旦进入普通集合，就不再区分单位元，也不再关心乘法，所以它称为遗忘函子（forgetful functor）。遗忘函子在范畴论中经常出现。

现在我们有了 $Mon$ 的两种不同视角。可以把它当作普通范畴，只含对象和态射。在这个视角中，看不到幺半群的内部结构。关于 $Mon$ 中某个特定对象，能说的只有它通过态射连接到自身以及其他对象。态射的“乘法”表，也就是组合规则，来自另一个视角：作为集合的幺半群。进入范畴论并没有完全丢掉这个视角，因为仍然可以通过遗忘函子访问它。

要应用通用构造，需要定义一个特殊性质，让我们能在幺半群范畴中搜索，并选出自由幺半群的最佳候选者。但自由幺半群由它的生成元定义。不同生成元选择会产生不同自由幺半群（Bool 的列表不同于 Int 的列表）。我们的构造必须从生成元集合开始。所以又回到了集合！

这正是遗忘函子发挥作用的地方。可以用它给幺半群拍 X 光。我们可以在这些团块的 X 光图像中识别生成元。做法如下：

从生成元集合 x 开始。它是 $Set$ 中的集合。

要匹配的模式由一个幺半群 m（$Mon$ 中的对象）和 $Set$ 中的函数 p 组成：

p :: x -> U m

val p: X => U[M]

其中 U 是从 $Mon$ 到 $Set$ 的遗忘函子。这是一个奇怪的异质模式，一半在 $Mon$ 中，一半在 $Set$ 中。

思想是，函数 p 会在 m 的 X 光图像中识别生成元集合。函数在识别集合中的点时可能表现很差（它们可能把点折叠起来），但没关系。通用构造会处理这一切，并选择这个模式的最佳代表。

还必须定义候选者之间的排序。假设有另一个候选者：幺半群 n，以及在它的 X 光图像中识别生成元的函数：

q :: x -> U n

val q: X => U[N]

我们会说 m 优于 n，当且仅当存在一个幺半群态射，也就是保持结构的同态：

h :: m -> n

val h: M => N

它在 U 下的像（记住，U 是函子，所以会把态射映射为函数）通过 p 分解：

q = U h . p

val q = uh compose p

如果把 p 看作在 m 中选择生成元，把 q 看作在 n 中选择“同一批”生成元，那么可以把 h 看作在两个幺半群之间映射这些生成元。记住，h 按定义保持幺半结构。这意味着，一个幺半群中两个生成元的积，会被映射为第二个幺半群中对应两个生成元的积，依此类推。

这个排序可用于寻找最佳候选者，也就是自由幺半群。定义如下：

如果存在从 m 到任意其他幺半群 n（连同函数 q）的唯一态射 h，并且它满足上面的分解性质，那么我们说 m（连同函数 p）是由生成元 x 生成的自由幺半群。

顺便说一句，这回答了第二个问题。函数 U h 有能力把 U m 中的多个元素折叠为 U n 中的一个元素。这种折叠对应于等同自由幺半群中的某些元素。因此，任意带生成元 x 的幺半群，都可以通过从基于 x 的自由幺半群出发，并等同某些元素而得到。自由幺半群是只做最少必要等同的那个。

讨论伴随时，我们还会回到自由幺半群。

13.3 挑战（Challenges）

1. 你可能会认为（我最初也这样想），要求幺半群同态保持单位元是多余的。毕竟，对所有 a，我们知道：

h a * h e = h (a * e) = h a

所以 h e 像一个右单位元（类似地，也是左单位元）。问题在于，所有 h a 可能只覆盖目标幺半群的一个子幺半群。真正的单位元可能位于 h 的像之外。说明：保持乘法的幺半群同构会自动保持单位元。

2. 考虑一个从带连接的整数列表到带乘法的整数的幺半群同态。空列表 [] 的像是什么？假设所有单元素列表都映射到其中包含的整数，也就是说 [3] 映射到 3，等等。[1, 2, 3, 4] 的像是什么？有多少个不同列表映射到整数 12？这两个幺半群之间还有其他同态吗？
3. 由单元素集合生成的自由幺半群是什么？你能看出它同构于什么吗？