第 1 章：范畴：组合的本质（Category: The Essence of Composition）
原文：Bartosz Milewski, Category Theory for Programmers, Scala Edition, Chapter 1. 原书 PDF、
.tex源文件及相关图像采用 CC BY-SA 4.0；本译文按同一许可发布。
范畴是一个简单到令人尴尬的概念。一个范畴由对象（objects）以及对象之间的箭头（arrows）组成。这也是为什么范畴很容易用图来表示：对象可以画成圆圈或点，而箭头就是箭头。为了变化一点，我偶尔会把对象画成小猪，把箭头画成烟花。不过，范畴的本质是组合（composition）。或者，如果你愿意，也可以说组合的本质就是范畴。箭头可以组合：如果有一个从对象 $A$ 到对象 $B$ 的箭头，又有一个从对象 $B$ 到对象 $C$ 的箭头，那么就必须存在一个从 $A$ 到 $C$ 的箭头，也就是它们的组合。
图 1.1 在一个范畴中，如果存在一个从 $A$ 到 $B$ 的箭头，以及一个从 $B$ 到 $C$ 的箭头，那么也必须存在一个从 $A$ 到 $C$ 的直接箭头，它就是前两个箭头的组合。这个图还不是完整范畴，因为它缺少恒等态射，后面会讨论。
1.1 作为函数的箭头（Arrows as Functions）
这些内容已经太像抽象废话了吗？不要绝望。我们来谈点具体的东西。可以把箭头，也称为态射（morphisms），想成函数。你有一个函数 $f$，它接收类型 $A$ 的参数并返回 $B$。你还有另一个函数 $g$，它接收 $B$ 并返回 $C$。你可以把 $f$ 的结果传给 $g$，从而组合它们。这样，你刚刚定义了一个新函数：它接收 $A$ 并返回 $C$。
在数学中，这种组合用函数之间的小圆圈表示：$g \circ f$。注意组合是从右到左读的。对有些人来说，这会令人困惑。你可能熟悉 Unix 中的管道记法，例如：
lsof | grep Chrome
或者 F# 中的 >>，它们都是从左到右流动。但在数学和 Haskell 中，函数组合是从右到左的。把 $g \circ f$ 读成“先 $f$ 后 $g$”，会有帮助。
为了让这一点更明确，我们先写一点 C 代码。这里有一个从 A 到 B 的函数 f：
B f(A a);
还有另一个函数：
C g(B b);
它们的组合是：
C g_after_f(A a)
{
return g(f(a));
}
这里再次可以看到从右到左的组合：g(f(a))，这次是在 C 中。
我希望能告诉你，C++ 标准库里有一个模板，可以接收两个函数并返回它们的组合，但并没有。换成 Scala 试试。下面是一个从 A 到 B 的函数声明：
val f: A => B
类似地：
val g: B => C
它们的组合是：
g compose f
一旦看到 Scala 或 Haskell 中这些事情有多简单，就会觉得 C++ 难以表达直截了当的函数式概念有点尴尬。
这里得到第一条 Scala 版阅读提示：A => B 表示从类型 A 到类型 B 的函数类型。你可以用 compose 把两个函数组合起来。g compose f 表示先执行 f，再执行 g。
1.2 组合的性质（Properties of Composition）
任何范畴中的组合都必须满足两个极其重要的性质。
第一，组合是结合的。如果有三个可以组合的态射 $f$、$g$ 和 $h$，也就是说它们的对象首尾匹配，那么组合它们时不需要括号。用数学记法表示为：
$$ h \circ (g \circ f) = (h \circ g) \circ f = h \circ g \circ f $$
在伪 Scala 中可以写成：
val f: A => B
val g: B => C
val h: C => D
h compose (g compose f) === (h compose g) compose f === h compose g compose f
这里说“伪”，是因为函数之间的相等性并没有一般定义。处理函数时，结合律相当直观；但在其他范畴中，它可能没有这么显然。
第二，对每个对象 $A$，都有一个作为组合单位元的箭头。这个箭头从对象出发又回到它自身。所谓组合单位元，是指当它与任何从 $A$ 出发或以 $A$ 结束的箭头组合时，会分别得到原来的箭头。对象 $A$ 的单位箭头称为 $id_A$，也就是 $A$ 上的恒等（identity）。用数学记法说，如果 $f$ 从 $A$ 到 $B$，那么：
$$ f \circ id_A = f $$
并且：
$$ id_B \circ f = f $$
处理函数时，恒等箭头由恒等函数实现。恒等函数只是返回它的参数。对每种类型来说，实现都是一样的，这意味着这个函数是普遍多态的。在 C++ 中，可以把它定义成模板：
template<typename T> T id(T x) { return x; }
当然，在 C++ 里事情从来没这么简单，因为不仅要考虑传什么，还要考虑怎么传，比如按值、按引用、按 const 引用、按移动等。
在 Scala 中，恒等函数可以这样写：
def identity[A](a: A): A = a
可以看到，在 Scala 中定义多态函数也很直接。方括号中的 A 是类型参数，表示这个函数对任意类型都适用。
函数定义由函数名、类型参数、值参数、返回类型和函数体组成。这里的函数体只是 a。函数体是表达式，而这个表达式的值就是函数结果。
恒等律可以写成伪 Scala：
f compose identity[A] == f
identity[B] _ compose f == f
你可能会问：为什么有人会关心恒等函数这种什么都不做的函数？换个角度，为什么我们关心数字零？零是“无”的符号。古罗马人的数字系统里没有零，但他们仍然修建了卓越的道路和水渠，其中一些至今仍存。
像零或 $id$ 这样的中性值，在处理符号变量时非常有用。这也是为什么不熟悉零概念的罗马人不擅长代数，而熟悉零概念的阿拉伯人和波斯人在这方面更进一步。因此，恒等函数在作为高阶函数的参数或返回值时非常方便。高阶函数让函数的符号化操作成为可能，它们就是函数的代数。
总结一下：一个范畴由对象和箭头（态射）组成。箭头可以组合，并且组合满足结合律。每个对象都有一个恒等箭头，它在组合下充当单位元。
1.3 组合是编程的本质（Composition is the Essence of Programming）
函数式程序员处理问题的方式很特别。他们会先问一些很有禅意的问题。例如，设计交互式程序时，他们会问：什么是交互？实现 Conway 的生命游戏时，他们可能会沉思生命的意义。本着这种精神，我要问：什么是编程？
在最基本层面上，编程就是告诉计算机该做什么。“取内存地址 x 中的内容，并把它加到寄存器 EAX 的内容上。”但即使在汇编中编程，我们给计算机的指令也是某种更有意义的东西的表达。我们在解决非平凡问题；如果问题是平凡的，也就不需要计算机帮助了。
我们如何解决问题？把大问题分解成小问题。如果小问题仍然太大，就继续分解，如此往复。最后，我们编写代码解决所有小问题。然后，编程的本质出现了：我们把这些代码片段组合起来，创建更大问题的解。如果不能把碎片重新组合起来，分解就没有意义。
这种层次化分解与重新组合的过程，并不是计算机强加给我们的。它反映的是人类心智的限制。我们的大脑一次只能处理少量概念。心理学中一篇广为引用的论文《神奇数字 7 加减 2》曾提出，我们只能在头脑中保留 $7 \pm 2$ 个信息块。我们对人类短期记忆细节的理解也许会变化，但可以确定的是，它是有限的。
关键在于，我们无法处理一锅对象汤，也无法处理一团意大利面式代码。我们需要结构，并不是因为结构良好的程序看起来赏心悦目，而是因为否则大脑无法高效处理它们。我们经常说某段代码优雅或美丽，但真正的意思是：它易于被有限的人类心智处理。优雅的代码会创造大小合适、数量恰当的信息块，让我们的心智能够消化吸收。
那么，适合程序组合的信息块应该是什么样？它们的表面积必须比体积增长得更慢。我喜欢这个类比，因为几何对象的表面积随尺寸平方增长，而体积随尺寸立方增长，表面积增长得更慢。这里，表面积是组合这些块所需的信息；体积是实现这些块所需的信息。想法是，一旦某个块被实现，就可以忘记它的实现细节，转而专注于它如何与其他块交互。在面向对象编程中，表面是对象的类声明，或者说抽象接口。在函数式编程中，表面是函数声明。这里略有简化，但要点如此。
范畴论是极端的，因为它主动劝阻我们查看对象内部。范畴论中的对象是抽象而朦胧的实体。你所能知道的一切，就是它如何与其他对象相关，也就是它如何用箭头与其他对象连接。互联网搜索引擎正是通过分析传入和传出的链接来给网站排名，作弊时除外。在面向对象编程中，理想化对象只通过抽象接口可见，也就是纯表面、无体积，而方法扮演箭头的角色。一旦你必须深入对象实现才能理解如何把它与其他对象组合起来，你就失去了所用编程范式的优势。
挑战
- 在你最喜欢的语言中尽可能实现恒等函数。如果你最喜欢的语言恰好是 Haskell，就用第二喜欢的语言。
- 在你最喜欢的语言中实现组合函数。它接收两个函数作为参数，并返回它们的组合。
- 编写一个程序，尝试测试你的组合函数是否遵守恒等律。
- 万维网在某种意义上是一个范畴吗？链接是态射吗？
- 如果把人作为对象、把好友关系作为态射，Facebook 是一个范畴吗？
- 有向图在什么时候是一个范畴？