第 5 章：积与余积（Products and Coproducts）

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

古希腊剧作家欧里庇得斯曾说：“每个人都像他习惯交往的同伴。”我们由关系定义。在范畴论中，没有什么比这更真实。如果想在一个范畴中挑出某个特定对象，我们只能描述它与其他对象以及它自身的关系模式。这些关系由态射定义。

范畴论中有一种常见构造，称为通用构造（universal construction），用于根据对象的关系来定义对象。一种做法是选择一个模式，也就是由对象和态射构成的特定形状，然后寻找这个模式在范畴中的所有出现。如果模式足够常见，而范畴又足够大，就很可能会有大量命中。技巧在于：在这些命中之间建立某种排序，并挑选可以被认为是最佳匹配的那个。

这个过程让人想起 Web 搜索。查询就像一个模式。非常泛化的查询会带来很高的召回率（recall），也就是大量命中。其中一些可能相关，另一些无关。为了去掉无关命中，你会细化查询，这会提高精确率（precision）。最后，搜索引擎会给命中排序，并希望你感兴趣的那个结果排在列表顶部。

5.1 始对象（Initial Object）

最简单的形状是单个对象。显然，在给定范畴中有多少对象，就有多少这种形状的实例。可选项太多了。我们需要建立某种排序，并尝试找到这个层级顶部的对象。我们唯一可用的手段是态射。如果把态射想成箭头，那么可能存在一种总体箭头流，从范畴一端流向另一端。例如，在有序范畴中，特别是在偏序中，就是这样。可以推广这种对象优先级概念：如果有一个从对象 $a$ 到对象 $b$ 的箭头，就说对象 $a$ 比对象 $b$ “更初始”。于是我们把始对象定义为有箭头指向所有其他对象的对象。

显然，并不能保证这样的对象存在，这没关系。更大的问题是，可能存在太多这样的对象：召回率很好，但精确率不足。解决办法是借鉴有序范畴，它们在任意两个对象之间最多允许一个箭头：一个对象小于等于另一个对象的方式只有一种。这引出始对象的定义：

始对象是这样一个对象：从它到范畴中任意对象都恰好有一个态射。

始对象

不过，即便这样也不能保证始对象唯一，如果它存在的话。但它保证了次优性质：在同构意义下唯一（unique up to isomorphism）。同构在范畴论中非常重要，所以稍后会讨论。现在，我们先同意“在同构意义下唯一”足以证明在始对象定义中使用“the”是合理的。

来看一些例子。偏序集中的始对象通常称为它的最小元素。有些偏序集没有始对象，例如所有整数集合（包含正数和负数），以小于等于关系作为态射。

在集合与函数的范畴中，始对象是空集。记住，空集对应 Scala 中的 Nothing 类型。从 Nothing 到任意其他类型的唯一多态函数叫 absurd：

def absurd[A]: Nothing => A

正是这个态射族让 Nothing 成为类型范畴中的始对象。

5.2 终对象（Terminal Object）

继续使用单对象模式，但改变对象排序方式。我们说，如果有一个从 $b$ 到 $a$ 的态射，那么对象 $a$ 比对象 $b$ “更终结”。注意方向反了。我们寻找一个比范畴中任何其他对象都更终结的对象。同样，我们坚持唯一性：

终对象是这样一个对象：范畴中任意对象到它都恰好有一个态射。

终对象

同样，终对象在同构意义下唯一，稍后会说明。先看一些例子。在偏序集中，如果终对象存在，它就是最大对象。在集合范畴中，终对象是单元素集合。前面已经讨论过单元素集合，它对应 C++ 中的 void 类型，也对应 Scala 和 Haskell 中的 unit 类型。它只有一个值，在 Scala 中写作 ()。我们也已经确定，从任意类型到 unit 类型恰好有一个纯函数：

def unit[A]: A => Unit = _ => ()

所以终对象的所有条件都满足。

注意，在这个例子中，唯一性条件至关重要，因为还有其他集合，实际上除了空集以外所有集合，都有来自每个集合的入射态射。例如，对每个类型都可以定义一个返回 Boolean 的函数，也就是谓词：

def yes[A]: A => Boolean = _ => true

但 Boolean 不是终对象。对每个类型（除了 Nothing，因为两个函数都等于 absurd）至少还有另一个返回 Boolean 的函数：

def no[A]: A => Boolean = _ => false

坚持唯一性，给了我们恰当的精确率，让终对象定义收窄到唯一类型。

5.3 对偶性（Duality）

你很难不注意到始对象和终对象定义之间的对称性。两者唯一的差别是态射方向。事实证明，对任意范畴 $C$，都可以通过反转所有箭头来定义反范畴（opposite category）$C^op$。只要同时重新定义组合，反范畴会自动满足范畴的所有要求。如果原来的态射 $f: a -> b$ 和 $g: b -> c$ 组合为 $h: a -> c$，并且 $h = g \circ f$，那么反向态射 $f^op: b -> a$ 和 $g^op: c -> b$ 会组合为 $h^op: c -> a$，并且 $h^op = f^op \circ g^op$。反转恒等箭头则是一个 no-op。

对偶性是范畴的重要性质，因为它让每个从事范畴论工作的数学家生产力翻倍。你提出的每个构造都有它的反向构造；你证明的每个定理都会免费得到一个对偶定理。反范畴中的构造通常加上 co 前缀，所以有 product 和 coproduct、monad 和 comonad、cone 和 cocone、limit 和 colimit，等等。不过没有 cocomonad，因为反转两次箭头会回到原状态。

因此，终对象就是反范畴中的始对象。

5.4 同构（Isomorphisms）

作为程序员，我们很清楚定义相等并不是平凡任务。两个对象相等是什么意思？它们必须占据内存中的同一位置吗，也就是指针相等？还是只要所有组件值相等就够了？如果一个复数用实部和虚部表示，另一个用模长和角度表示，它们相等吗？你也许会以为数学家早就搞清了相等的含义，但他们没有。他们也面对多个相互竞争的相等定义：命题相等、内涵相等、外延相等，以及同伦类型论中作为路径的相等。然后还有更弱的同构概念，以及更弱的等价概念。

直觉上，同构对象看起来一样，它们有相同形状。这意味着一个对象的每个部分都通过一一映射对应到另一个对象的某个部分。就我们的仪器所能判断的范围而言，这两个对象是彼此的完美拷贝。数学上，这意味着存在从对象 $a$ 到对象 $b$ 的映射，也存在从对象 $b$ 回到对象 $a$ 的映射，并且二者互为逆。在范畴论中，我们用态射替代映射。同构就是可逆态射，或者说一对态射，其中一个是另一个的逆。

我们通过组合和恒等来理解逆：如果态射 $g$ 是态射 $f$ 的逆，那么它们的组合是恒等态射。实际上有两个等式，因为两个态射有两种组合方式：

f compose g == identity _
g compose f == identity _

当我说始对象或终对象在同构意义下唯一时，意思是任意两个始对象或任意两个终对象都是同构的。这其实很容易看出来。假设有两个始对象 $i_1$ 和 $i_2$。由于 $i_1$ 是始对象，存在唯一态射 $f$ 从 $i_1$ 到 $i_2$。同理，因为 $i_2$ 是始对象，存在唯一态射 $g$ 从 $i_2$ 到 $i_1$。这两个态射的组合是什么？

始对象唯一性证明图

图 5.1 图中的所有态射都是唯一的。

组合 $g \circ f$ 必须是从 $i_1$ 到 $i_1$ 的态射。但 $i_1$ 是始对象，所以从 $i_1$ 到 $i_1$ 只能有一个态射。由于我们处在一个范畴中，知道存在从 $i_1$ 到 $i_1$ 的恒等态射；既然只容得下一个，那就一定是它。因此 $g \circ f$ 等于恒等。同样，$f \circ g$ 也必须等于恒等，因为从 $i_2$ 回到 $i_2$ 也只能有一个态射。这证明 $f$ 和 $g$ 必然互为逆。因此，任意两个始对象都是同构的。

注意，在这个证明中，我们使用了从始对象到它自身的态射唯一性。没有它，就无法证明“在同构意义下”这一部分。但为什么还需要 $f$ 和 $g$ 的唯一性？因为始对象不仅在同构意义下唯一，而且在唯一同构意义下唯一。原则上，两个对象之间可能有多个同构，但这里不是这样。“在唯一同构意义下唯一”是所有通用构造的重要性质。

5.5 积（Products）

下一个通用构造是积。我们知道两个集合的笛卡尔积是什么：它是 pair 的集合。但连接积集合与其组成集合的模式是什么？如果弄清这一点，就能把它推广到其他范畴。

我们能说的是，存在两个函数，也就是投影，从积到每个组成部分。在 Scala 中，这两个函数可以写成 fst 和 snd，分别取 pair 的第一个和第二个分量：

def fst[A, B]: ((A, B)) => A = {
  case (x, y) => x
}

def snd[A, B]: ((A, B)) => B = {
  case (x, y) => y
}

这里，函数通过对参数做模式匹配来定义：匹配任意 pair 的模式是 (x, y)，它把组成分量提取到变量 x 和 y。这些定义还可以用通配访问进一步简化：

def fst[A, B]: ((A, B)) => A = _._1
def snd[A, B]: ((A, B)) => B = _._2

有了这些看似非常有限的信息，我们试着在集合范畴中定义对象和态射的模式，让它引出两个集合 $a$ 和 $b$ 的积。这个模式由一个对象 $c$ 以及两个态射 $p$ 和 $q$ 组成，它们分别把 $c$ 连接到 $a$ 和 $b$：

def p: C => A
def q: C => B

积模式

所有符合这个模式的 $c$ 都会被视为积的候选者。这样的候选可能很多。

积候选者

例如，选择两个 Scala 类型 Int 和 Boolean 作为组成对象，并取一些它们的积候选。

这里有一个候选：Int。Int 可以被认为是 Int 和 Boolean 的积候选吗？可以，下面是它的投影：

def p: Int => Int = x => x

def q: Int => Boolean = _ => true

这很蹩脚，但符合条件。

另一个候选是 (Int, Int, Boolean)。这是包含三个元素的 tuple，也就是 triple。下面两个态射让它成为合法候选：

def p: ((Int, Int, Boolean)) => Int = _._1

def q: ((Int, Int, Boolean)) => Boolean = _._3

你可能已经注意到，第一个候选太小，只覆盖了积的 Int 维度；第二个候选又太大，凭空复制了一份 Int 维度。

但我们还没有探索通用构造的另一部分：排序。我们希望能比较两个模式实例。也就是比较一个候选对象 $c$ 及其两个投影 $p$ 和 $q$，与另一个候选对象 $c'$ 及其两个投影 $p'$ 和 $q'$。我们想说，如果有一个从 $c'$ 到 $c$ 的态射 $m$，那么 $c$ 比 $c'$ “更好”。但这太弱了。我们还希望它的投影比 $c'$ 的投影“更好”，或者“更通用”。意思是，$p'$ 和 $q'$ 可以通过 $m$ 从 $p$ 和 $q$ 重构出来：

p1 == p compose m
q1 == q compose m

积候选排序

另一种看这些等式的方式是：$m$ 分解（factorizes）了 $p'$ 和 $q'$。可以假装这些等式是在自然数中，而点是乘法：$m$ 是 $p'$ 和 $q'$ 共享的公因子。

为了建立一些直觉，我来说明 pair (Int, Boolean) 以及两个标准投影 fst 和 snd，确实比前面两个候选更好。

不是积的候选

对第一个候选，映射 m 是：

def m: Int => (Int, Boolean) = x => (x, true)

两个投影 p 和 q 确实可以重构为：

def p: Int => Int = x => fst(m(x)) // == x
def q: Int => Boolean = x => snd(m(x)) // == true

第二个例子中的 m 也类似地被唯一确定：

def m: ((Int, Int, Boolean)) => (Int, Boolean) = {
  case (x, _, b) => (x, b)
}

我们已经能说明 (Int, Boolean) 比这两个候选都更好。再看看为什么反过来不成立。能否找到某个 m1，帮助我们用 p 和 q 重构 fst 和 snd？

fst == p compose m1
snd == q compose m1

在第一个例子中，q 总是返回 true，而我们知道有些 pair 的第二个分量是 false。因此，无法从 q 重构 snd。

第二个例子不同。运行 p 或 q 后保留的信息足够多，但分解 fst 和 snd 的方式不止一种。因为 p 和 q 都忽略 triple 的第二个分量，所以 m1 可以在其中放任何东西。可以有：

def m1: ((Int, Boolean)) => (Int, Int, Boolean) = {
  case (x, b) => (x, x, b)
}

或者：

def m1: ((Int, Boolean)) => (Int, Int, Boolean) = {
  case (x, b) => (x, 42, b)
}

等等。

综合起来，给定任意类型 C 以及两个投影 p 和 q，存在唯一的 m 从 C 到笛卡尔积 (A, B)，可以分解它们。事实上，它只是把 p 和 q 组合成一个 pair：

def m: C => (A, B) = x => (p(x), q(x))

这使笛卡尔积 (A, B) 成为最佳匹配，也就是说，这个通用构造在集合范畴中有效。它挑出了任意两个集合的积。

现在忘掉集合，用同一个通用构造定义任意范畴中两个对象的积。这样的积并不总是存在；但如果存在，它在唯一同构意义下唯一。

两个对象 $a$ 和 $b$ 的积是一个对象 $c$，配备两个投影；并且对任何其他配备两个投影的对象 $c'$，都存在唯一态射 $m$ 从 $c'$ 到 $c$，能够分解那些投影。

一个从两个候选投影产生分解函数 m 的高阶函数，有时称为分解器（factorizer）。在我们的例子中，它是：

def factorizer[A, B, C]: (C => A) => (C => B) => (C => (A, B)) =
  p => q => x => (p(x), q(x))

5.6 余积（Coproduct）

像范畴论中的每个构造一样，积也有对偶，称为余积。当反转积模式中的箭头时，会得到一个对象 $c$，配备两个注入（injections）i 和 j：从 $a$ 和 $b$ 到 $c$ 的态射。

def i: A => C
def j: B => C

余积模式

排序也被反转：配备注入 $i$ 和 $j$ 的对象 $c$，如果存在一个从 $c$ 到 $c'$ 的态射 $m$，能够分解注入，就比配备注入 $i'$ 和 $j'$ 的对象 $c'$ “更好”：

i1 == m compose i
j1 == m compose j

余积候选排序

这种对象中的“最佳”者，也就是与任何其他模式之间都有唯一态射连接的那个，称为余积；如果它存在，则在唯一同构意义下唯一。

两个对象 $a$ 和 $b$ 的余积是一个对象 $c$，配备两个注入；并且对任何其他配备两个注入的对象 $c'$，都存在唯一态射 $m$ 从 $c$ 到 $c'$，能够分解那些注入。

在集合范畴中，余积是两个集合的不交并（disjoint union）。$a$ 和 $b$ 的不交并中的元素，要么是 $a$ 的元素，要么是 $b$ 的元素。如果两个集合有重叠，不交并会包含公共部分的两个副本。可以把不交并中的元素想成带有一个标识来源的标签。

对程序员来说，用类型理解余积更容易：它是两个类型的带标签联合。C++ 支持 union，但它们没有标签。这意味着在程序中必须以某种方式跟踪 union 的哪个成员有效。要创建带标签联合，需要定义一个标签，也就是枚举，并把它和 union 组合起来。例如，int 和 char const * 的带标签联合可以实现为：

struct Contact {
    enum { isPhone, isEmail } tag;
    union { int phoneNum; char const * emailAddr; };
};

两个注入既可以实现为构造器，也可以实现为函数。例如，第一个注入可以实现为函数 PhoneNum：

Contact PhoneNum(int n) {
    Contact c;
    c.tag = isPhone;
    c.phoneNum = n;
    return c;
}

它把一个整数注入到 Contact 中。

带标签联合也称为变体（variant），C++17 标准中有一个非常通用的变体实现：std::variant。

在 Scala 中，可以用 sealed trait 与 case class 把任意数据类型组合成带标签联合。Contact 例子可以写成：

sealed trait Contact
case class PhoneNum(num: Int) extends Contact
case class EmailAddr(addr: String) extends Contact

这里，PhoneNum 和 EmailAddr 既作为构造器（注入），也作为模式匹配的标签。比如，可以这样用电话号码构造一个联系人：

def helpdesk: Contact = PhoneNum(2222222)

与 Scala 中内建 tuple 作为积的标准实现不同，余积的标准实现通常是类似 Either 的数据类型：

sealed trait Either[A, B]
case class Left[A](v: A) extends Either[A, Nothing]
case class Right[B](v: B) extends Either[Nothing, B]

它由两个类型 A 和 B 参数化，并有两个构造器：Left 接收 A 类型的值，Right 接收 B 类型的值。

就像为积定义分解器一样，也可以为余积定义分解器。给定候选类型 C 以及两个候选注入 i 和 j，Either 的分解器会产生分解函数：

def factorizer[A, B, C]: (A => C) => (B => C) => Either[A, B] => C =
  i => j => {
    case Left(a) => i(a)
    case Right(b) => j(b)
  }

5.7 不对称性（Asymmetry）

我们已经见过两组对偶定义：通过反转箭头方向，可以从始对象定义得到终对象定义；类似地，也可以从积定义得到余积定义。然而在集合范畴中，始对象与终对象非常不同，余积与积也非常不同。后面会看到，积的行为像乘法，终对象扮演一的角色；余积更像加法，始对象扮演零的角色。特别是，对于有限集合，积的大小是各集合大小的乘积，而余积的大小是各集合大小之和。

这说明集合范畴相对于箭头反转并不对称。

注意，空集到任意集合都有唯一态射，也就是 absurd 函数，但没有态射返回空集。单元素集合有来自任意集合的唯一态射，但它也有指向每个集合（空集除外）的出射态射。如前所见，这些从终对象出发的出射态射，扮演了从其他集合中选取元素的重要角色。空集没有元素，所以无物可选。

单元素集合与积之间的关系，让它区别于余积。考虑使用由 unit 类型 Unit 表示的单元素集合作为积模式的另一个候选，当然是非常差的候选。给它配备两个投影 p 和 q，也就是从单元素集合到各组成集合的函数。每个投影都会从相应集合中选择一个具体元素。因为积是通用的，所以也存在一个从我们的候选者，也就是单元素集合，到积的唯一态射 m。这个态射会从积集合中选取一个元素，也就是一个具体 pair。它也分解两个投影：

p == fst compose m
q == snd compose m

当作用在单元素集合唯一元素 () 上时，这两个等式变成：

p(()) == fst(m(()))
q(()) == snd(m(()))

由于 m(()) 是由 m 从积中选出的元素，这些等式告诉我们：p 从第一个集合中选出的元素 p(())，正是 m 选出的 pair 的第一个分量。类似地，q(()) 等于第二个分量。这与我们对积元素的理解完全一致：积的元素就是来自组成集合的元素对。

余积没有这种简单解释。可以尝试把单元素集合作为余积候选，试图从中提取元素，但在那里会有两个注入进入它，而不是两个投影从它出来。它们不会告诉我们关于源对象的任何信息，事实上前面已经看到，它们会忽略输入参数。从余积到单元素候选的唯一态射也不会告诉我们这些信息。从始对象方向看集合范畴，与从终对象方向看它，确实很不一样。

这不是集合本身的内在性质，而是函数的性质，因为我们在 $Set$ 中把函数用作态射。函数总体上是不对称的。解释如下。

函数必须为定义域集合中的每个元素定义，在编程中我们称之为全函数（total function），但它不必覆盖整个陪域。前面见过一些极端情况：从单元素集合出发的函数，只在陪域中选择一个元素。实际上，从空集出发的函数才是真正的极端。当定义域大小远小于陪域大小时，我们常常把这种函数想成把定义域嵌入陪域。例如，可以把从单元素集合出发的函数想成把它的唯一元素嵌入陪域。我称它们为嵌入（embedding）函数，但数学家更喜欢给相反情况命名：紧密填满陪域的函数称为满射（surjective）或 onto。

另一个不对称来源是，函数允许把定义域中的多个元素映射到陪域中的一个元素。它们可以折叠元素。极端情况是把整个集合映射到单元素集合的函数。前面已经见过正是这么做的多态 unit 函数。折叠只会在组合中进一步叠加。两个折叠函数的组合比单个函数更加折叠。数学家也给非折叠函数起了名字：单射（injective）或 one-to-one。

当然，也有一些函数既不是嵌入，也不是折叠。它们称为双射（bijections），并且真正对称，因为它们可逆。在集合范畴中，同构与双射是一回事。

挑战

证明终对象在唯一同构意义下唯一。
偏序集中两个对象的积是什么？提示：使用通用构造。
偏序集中两个对象的余积是什么？
在你最喜欢的语言（Haskell 除外）中，实现等价于 Haskell Either 的泛型类型。
证明 Either 比配备两个注入的 int 是“更好”的余积候选：

int i(int n) { return n; }
int j(bool b) { return b ? 0: 1; }

提示：定义一个函数：

int m(Either const & e);

它可以分解 i 和 j。

继续上一题：你会如何论证，带有两个注入 i 和 j 的 int 不可能比 Either “更好”？
继续上一题：下面这些注入又如何？

int i(int n) {
    if (n < 0) return n;
    return n + 2;
}

int j(bool b) { return b ? 0: 1; }

为 int 和 bool 的余积想出一个较差候选。它不能比 Either 更好，因为它允许从自身到 Either 存在多个可接受态射。

参考资料

The Catsters, Products and Coproducts video.

5.1 始对象（Initial Object）​

5.2 终对象（Terminal Object）​

5.3 对偶性（Duality）​

5.4 同构（Isomorphisms）​

5.5 积（Products）​

5.6 余积（Coproduct）​

5.7 不对称性（Asymmetry）​

挑战​

参考资料​