数学基础

范畴与函子

范畴把对象和它们之间的箭头打包在一起,只需满足结合律和单位律;函子是两个这样的世界之间保持结构的翻译,而一旦固定了"事物如何相互关联",对象本身就只在一个唯一同构的意义下被确定。

直观同一种形状,不同的外衣

一位翻译者、一张图、一张由路线连接的车站网络、一组由"必须先于"关系连接的任务——这些都共享同一个骨架:一些事物(对象)以及它们之间可以串联的箭头。范畴让这个骨架变得精确;函子则是把这样一张网络重新画进另一张网络中,同时保持每一条箭头链条完整的方法。

对象作为节点,态射作为有向边;把两条相继的边合成得到第三条边,这正是范畴所记录的数据。

大学范畴:对象、态射、合成

定义: 范畴

范畴 $\mathcal{C}$ 由一族对象 $A, B, C, \dots$ 以及每一对对象之间的一个态射集合 $\mathrm{Hom}_{\mathcal{C}}(A,B)$ 组成,再加上把 $f : A \to B$ 与 $g : B \to C$ 送到 $g \circ f : A \to C$ 的合成规则,以及每个对象上的恒等态射 $1_A : A \to A$ 。

h \circ (g \circ f) = (h \circ g) \circ f

两条公理使这些数据成为一个范畴:合成满足结合律( $h \circ (g \circ f) = (h \circ g) \circ f$ ,因此一条箭头链无论括号怎么放都只有一个明确的合成),恒等态射是中性的( $1_B \circ f = f = f \circ 1_A$ ,因此与 $1_A$ 或 $1_B$ 合成永远不会改变一个态射)。

1_B \circ f = f = f \circ 1_A

协变函子与反变函子
种类	对态射的作用	典型例子
协变	把 $f : A \to B$ 送到 $F(f) : F(A) \to F(B)$ ,方向相同	列表函子、遗忘函子
反变	把 $f : A \to B$ 送到 $F(f) : F(B) \to F(A)$ ,方向相反	对偶空间函子、预层Hom(-,A)

进阶函子与自然变换

函子 $F : \mathcal{C} \to \mathcal{D}$ 把 $\mathcal{C}$ 的每个对象 $A$ 送到 $\mathcal{D}$ 的一个对象 $F(A)$ ,把每个态射 $f$ 送到一个态射 $F(f)$ ,并保持合成与恒等: $F(g \circ f) = F(g) \circ F(f)$ 且 $F(1_A) = 1_{F(A)}$ 。两个函子 $\mathcal{C} \to \mathcal{D}$ 之间的自然变换 $\eta : F \Rightarrow G$ 给每个对象 $A$ 指派 $\mathcal{D}$ 中的一个态射 $\eta_A : F(A) \to G(A)$ ,并满足自然性方块:对每个 $f : A \to B$ , $G(f) \circ \eta_A = \eta_B \circ F(f)$ 。

F(g \circ f) = F(g) \circ F(f)

G(f) \circ \eta_A = \eta_B \circ F(f)

定理: 终对象在唯一同构意义下是唯一的

如果 $T_1$ 与 $T_2$ 都是 $\mathcal{C}$ 的终对象(从任意对象到它们各自都恰有一个态射),那么 $T_1 \cong T_2$ :它们之间存在一个同构,且它是唯一的态射 $T_1 \to T_2$ 。对偶命题对始对象成立,把同样的论证用到候选锥的范畴上,对积也同样成立。

为什么成立?

没有这个事实,"终对象"或"积"就不是良定义的——积的不同构造(比如有序对与其他编码方式)需要可以互相替换,而"在唯一同构意义下唯一"正是它们"相同"这一说法的精确含义。

证明

因为 $T_2$ 是终对象,所以每个对象——特别是 $T_1$ ——到它都恰有一个态射;记为 $u : T_1 \to T_2$ 。因为 $T_1$ 是终对象,对称地恰有一个 $v : T_2 \to T_1$ 。

考察合成 $v \circ u : T_1 \to T_1$ 。因为 $T_1$ 是终对象, $T_1 \to T_1$ 的态射恰有一个,而 $1_{T_1}$ 就是这样一个态射;由于 $v \circ u$ 也是一个 $T_1 \to T_1$ 的态射,唯一性迫使 $v \circ u = 1_{T_1}$ 。

用 $T_2$ 的终对象性作对称的论证,合成 $u \circ v : T_2 \to T_2$ 必须等于 $1_{T_2}$ : $u \circ v = 1_{T_2}$ 。

一个具有双侧逆的态射按定义就是一个同构,所以 $u$ 是一个具有逆 $v$ 的同构 $T_1 \cong T_2$ 。它是唯一的态射 $T_1 \to T_2$ ,因为 $T_2$ 的终对象性本身就说明这样的态射恰好只有一个—— $u$ 从一开始就被唯一确定,而它恰好可逆这件事只是后来发现的。

定理: 函子保持同构

如果 $F : \mathcal{C} \to \mathcal{D}$ 是一个函子, $f : A \to B$ 是 $\mathcal{C}$ 中一个具有逆 $g : B \to A$ 的同构,那么 $F(f) : F(A) \to F(B)$ 是 $\mathcal{D}$ 中的一个同构,逆为 $F(g)$ 。

为什么成立?

这正是函子成为可信翻译的原因:函子绝不会把一个等价关系意外拆成两个真正不同的对象,所以"在同构意义下"对对象进行分类这一问题是函子所尊重的。

证明

因为 $f$ 与 $g$ 互为逆, $g \circ f = 1_A$ 且 $f \circ g = 1_B$ 。

对第一个等式应用 $F$ 。函子保持合成,故 $F(g \circ f) = F(g) \circ F(f)$ ;函子保持恒等,故 $F(1_A) = 1_{F(A)}$ 。把这些与 $g \circ f = 1_A$ 结合得到 $F(g) \circ F(f) = 1_{F(A)}$ 。

以同样方式对第二个等式应用 $F$ : $F(f \circ g) = F(f) \circ F(g)$ 且 $F(1_B) = 1_{F(B)}$ ,于是由 $f \circ g = 1_B$ 得到 $F(f) \circ F(g) = 1_{F(B)}$ 。

这两个等式恰好说明 $F(g)$ 是 $F(f)$ 的双侧逆。具有双侧逆的态射就是同构,所以 $F(f) : F(A) \to F(B)$ 是一个以 $F(g)$ 为逆的同构,正如所述。

大学应用:函数式编程与数据库迁移

每一种主流函数式语言都有 `Functor` 类型类,原因正是列表、树以及 `Maybe`/`Option` 这样的容器,是类型与函数范畴上的函子:`fmap` 就是作用在态射上的 $F$ ,而函子律 $\mathrm{fmap}\,\mathrm{id} = \mathrm{id}$ 、 $\mathrm{fmap}\,(g \circ f) = \mathrm{fmap}\,g \circ \mathrm{fmap}\,f$ 恰好就是上面的公理。`Monad` 用两个自然变换(`return` 与 `join`)进一步精细化,满足类似自然性方块的相容律。在编程之外,David Spivak的函子式数据迁移把数据库模式建模为一个小范畴(表为对象,外键为态射),把模式迁移建模为两个这样范畴之间的一个函子,于是"正确地迁移数据"字面上就意味着"是一个函子"——保持合成的性质保证了经由中间模式迁移与直接迁移得到相同的结果。

例题: 检验列表的函子律

取列表上的 $\mathrm{fmap}$ ,定义为把函数应用到每个元素上: $\mathrm{fmap}\,f\,[x_1,\dots,x_n] = [f(x_1),\dots,f(x_n)]$ 。用具体列表 $[1,2,3]$ 、 $f(x)=x+1$ 与 $g(x)=2x$ 验证两条函子律。

解答

第一条律, $\mathrm{fmap}\,\mathrm{id} = \mathrm{id}$ :逐元素应用恒等函数得到 $\mathrm{fmap}\,\mathrm{id}\,[1,2,3] = [\mathrm{id}(1),\mathrm{id}(2),\mathrm{id}(3)] = [1,2,3]$ ,这恰好就是 $\mathrm{id}\,[1,2,3]$ 。这对任意列表都成立,不只是这个列表,因为对每个元素应用"什么都不做"对列表也什么都不做。

第二条律, $\mathrm{fmap}\,(g \circ f) = \mathrm{fmap}\,g \circ \mathrm{fmap}\,f$ :先计算左边。 $(g \circ f)(x) = 2(x+1)$ ,所以 $\mathrm{fmap}\,(g\circ f)\,[1,2,3] = [2\cdot2, 2\cdot3, 2\cdot4] = [4,6,8]$ 。

再看右边: $\mathrm{fmap}\,f\,[1,2,3] = [2,3,4]$ ,然后 $\mathrm{fmap}\,g\,[2,3,4] = [4,6,8]$ 。

两边都等于 $[4,6,8]$ ,在这个例子上验证了该律;一般证明是用 $x_i$ 代替 $1,2,3$ 的同样计算,因为 $\mathrm{fmap}$ 从不重新排序或丢弃元素。

例题: 作为函子的模式迁移

模式 $\mathcal{S}_1$ 有表 `Person` 与 `City`,外键为 `livesIn : Person -> City`。新模式 $\mathcal{S}_2$ 把 `Person` 拆分为 `Person` 与 `Contact`,有 `hasContact : Person -> Contact` 与 `livesIn2 : Contact -> City`。把这次迁移描述为一个函子,并解释保持合成能带来什么好处。

解答

把每个模式建模为一个范畴:对象是表,态射是自由合成的外键(因此 $\mathcal{S}_1$ 中有生成元 $\texttt{livesIn} : \texttt{Person} \to \texttt{City}$ 的合成)。迁移 $F : \mathcal{S}_1 \to \mathcal{S}_2$ 把 $\texttt{Person} \mapsto \texttt{Person}$ 、 $\texttt{City} \mapsto \texttt{City}$ ,并把态射 $\texttt{livesIn}$ 送到 $\mathcal{S}_2$ 中的合成态射 $\texttt{livesIn2} \circ \texttt{hasContact} : \texttt{Person} \to \texttt{City}$ 。

要使 $F$ 成为函子,它必须把恒等送到恒等(这里是显然的),并尊重合成:在 $\mathcal{S}_1$ 中由 $\texttt{livesIn}$ 构成的任何外键链,都必须映射到由 $F(\texttt{livesIn}) = \texttt{livesIn2} \circ \texttt{hasContact}$ 构成的同一条链,顺序相同,不跳步也不重排。

这正是"函子保持合成"这一定理给工程师带来的好处:如果旧模式中的某个查询通过 $\texttt{livesIn}$ 把 $\texttt{Person}$ 连接到 $\texttt{City}$ ,那么先逐表翻译并把 $\texttt{livesIn}$ 映射为两步路径,再执行连接,得到的结果与把整个查询作为一个整体翻译得到的结果完全相同——按表迁移的数据与按查询迁移的数据保证一致,正是因为 $F(g \circ f) = F(g) \circ F(f)$ 。

哪一对方程是范畴的两条公理?

反变函子把 $f : A \to B$ 送到哪个方向的态射?

在Spivak的函子式数据迁移中,模式迁移对应于什么?

如果 $u : T_1 \to T_2$ 是两个终对象之间唯一的态射,定理对 $u$ 说了什么?

参考文献

Saunders Mac Lane (1998). Categories for the Working Mathematician
Emily Riehl (2016). Category Theory in Context
David I. Spivak (2012). Functorial Data Migration · arXiv:1009.1166