原文见 http://bartoszmilewski.com/20...c++

-> 上一篇：『Kleisli 范畴』编程

沿着箭头

古希腊剧做家 Euripides 曾说过：『每一个人都像他尽力维护的同伴』。咱们被咱们的人际关系所定义。在范畴论中更是这样。若是想刻画范畴中的一个对象，只能经过描述这个对象与其余对象（或其自身）之间的关系模式来实现。segmentfault

范畴论中有一个常见的构造，叫作泛构造（Universal Construction），它就是经过对象之间的关系来定义对象，其方式之一就是拮取一个模式——由对象与态射构成的一种特殊的形状，而后在范畴中观察它的各个方面。若是这个模式很常见并且范畴也很大，你就会有大量的机会命中它。技巧是如何对这些命中机会进行排序，并选出最好的那个。网络

这个过程就相似于咱们进行网络搜索时所采用的方式。一次查询就是一个模式。一次很是宽泛的查询会召来大量的命中。其中有些多是你所关注的，其余的则不是。为了消减无关的命中，你会对查询进行优化，来提升它的命中精度。最终，搜索引擎会对命中的结果划分等级，颇有可能你想要的结果就位于命中结果等级序列的顶端。dom

初始对象

最简单的形状是单个的对象。显然，这种形状有许多实例，由于给定的范畴中有许多对象。可选对象过多。咱们须要将它们划分等级，去寻找处于最上层的那个对象。这意味着咱们要根据态射来划分对象的等级（译注：不然范畴中还有什么？）。若是将态射想象为箭头，它们可能会造成一张网，在这张网中，箭头从范畴的一端流向另外一端。在有序的范畴中会出现这种状况，例如偏序范畴。能够将对象前后次序的概念推广一下，即：若是说对象 a 比对象 b 更靠前，那么必定存在一个箭头（态射）是从 a 到 b 的。若是有一个对象，它发出的箭头指向全部其余的对象，那么这个对象就叫作初始对象。显然，对于一个给定的范畴，可能没法保证其中初始对象的存在，这还好说，更大的问题是其中可能有不少个初始对象：召来的东西都挺不错，可是精度不够。不过，能够从有序的范畴那里获得一些启示——任意两个对象之间，它们只容许最多存在 1 个箭头：小于或等于另一个对象。通过有序范畴的引导，咱们这样定义初始对象：ide

初始对象，这种对象有且仅有一个态射指向范畴中的任意一个对象。函数

然而，即便这样定义初始对象也没法担它的惟一性（若是它存在），可是这个定义能担保最好的一件事是：在同构意义下，它具备惟一性。同构（Isomorphism）在范畴论中很是重要，过会儿再谈它。如今，咱们只须要认定，初始对象的定义主要是为了让初始对象在同构意义下具有惟一性。性能

在此，给出几个与初始对象有关的例子：偏序集（一般称为 poset）的初始对象是那个最小的对象。有些偏序集没有初始对象——例如整数集。优化

在集合范畴中，初始对象是是空集。记住，在 Haskell 中，空集至关于 Void 类型（C++ 中没有相对应的类型），并且从 Void 到任意类型的多态函数是惟一的，它叫 absurd：搜索引擎

absurd :: Void -> a

它是一个态射族，由于它的存在，Void 才会成为类型范畴中的初始对象。

终端对象

继续考察单对象模式，如今改变一下划分对象等级的方式。若是有一个态射从对象 b 到对象 a，那么认为 a 比 b 更靠后。咱们要在范畴中寻找比任何其余对象都靠后的那个对象，而且坚持认定它也具有着这样的惟一性：

终端对象，这种对象有且仅有一个态射来自范畴中的任意对象。

一样，终端对象在同构意义下具备惟一性。同构是什么鬼，后面会讲。来看几个例子。在偏序集内，若是存在着终端对象，那么它是那个最大的对象。在集合范畴中，终端对象是一个单例。咱们已经讨论过单例，它们至关于 C++ 中的 void 类型，也至关于 Haskell 中的 unit 类型 ()。单例就是只有一个值的类型，在 C++ 中是隐匿的，在 Haskell 中是显式的。咱们已经肯定，有且仅有一个纯函数，它从任意类型到 unit 类型：

unit :: a -> ()
unit _ = ()

所以，对于单例而言，终端对象的全部条件都是可以知足的。

注意，上面示例中，惟一性的条件是很是重要的，由于有些集合（其实是除了空集的全部集合）会有来自其余集合的态射。例如，有一个布尔类型的函数（谓词），它的定义适合全部类型：

yes :: a -> Bool
yes _ = True

可是 Bool 并非一个终端对象，由于至少还存在一个一样是适合全部类型的布尔类型的函数：

no :: a -> Bool
no _ = False

坚持惟一性可以获得足够的精度，能够将终端对象的定义紧缩为一种类型。

对偶

你确定已经注意到了初始对象与终端对象是对称的。两者之间惟一的区别是态射的方向。事实上，对于任意范畴 C，咱们总能定义一个相反的范畴 C'，只需将 C 中的箭头都反转一下，而后再从新定义一下态射的复合方式，那么相反的范畴就可以天然知足全部的范畴法则。若是原始态射 f::a->b 和 g::b->c 用 h=g∘f 复合为 h::a->c，那么逆向的态射 f'::b->a 与 g'::c->b 可经过 h'=f'∘g' 复合为 h'::c->a。恒等箭头保持不变。

对偶是范畴的一个很是重要的性质，由于它可以让数学家在范畴论中的工做事半功倍。你所提出的每一种构造，都有其对偶的构造；你所证实的任何一个定理，都会获得它的一个免费版本。相反的范畴中的构造，一般冠以『co（余）』，所以就有了 product（积）与coproduct（余积），monad（单子） 与 comonad（余单子），cone（锥）与 cocone（余锥）等等。没有 cocomonad（余余单子），由于箭头反转两次又回到初始状态。

一个范畴中的终端对象，在相反范畴中就是初始对象。

同构

做为程序猿，咱们深知相等不是那么容易定义。两个对象相等是什么意思？它们是占据相同的位置（指针相等）么？或者它们全部成员的值相等么？两个复数，若是其中一个用实部与虚部来表示，另外一个用模与幅角来表示，它们是相等的么？你可能会认为数学家可以描述出相等的意义，但实际上他们也作不到。他们不得不定义出来多种相等，有命题相等、内涵相等、外延相等，还有拓扑类型理论中的路径相等之类。因而，就出现了一种弱化的相等概念——同构。

直觉上，同构的对象看上去是同样的，也就是说它们有相同的形状。这意味着一个对象的每个部分都能与另外一个对象的某一个部分造成一对一的映射，直到咱们的『仪器』可以检测出这两个对象是彼此的拷贝。在数学上，这意味着存在一个从对象 a 到对象 b 的映射，同时也存在着一个从对象 b 到对象 a 的映射，这两个映射是互逆的。在范畴论中，咱们用态射取代了映射。一个同构是一个可逆的态射；或者是一对互逆的态射。

咱们能够经过复合与恒等来理解互逆：若是态射 g 与态射 f 的复合结果是恒等态射，那么 g 是 f 的逆。这体现为如下两个方程，由于两个态射存在两种复合形式：

f . g = id
g . f = id

前面我说过，初始（终端）对象在同构意义下具备惟一性，个人意思就是任意两个初始（终端）对象都是同构的。这实际上很容易看出来。假设两个初始对象 $i_1$ 与 $i_2$，由于 $i_1$ 是初始对象，所以有惟一的态射 f 从 $i_1$ 到 $i_2$，同理也有惟一的态射 g 从 $i_2$ 到 $i_1$。这两个态射的复合结果是什么？

图中全部的态射都具备惟一性

g∘f 确定是从 $i_1$ 到 $i_1$ 的态射，由于 $i_1$ 是初始对象，所以它只允许一个从 $i_1$ 到 $i_1$ 的态射的存在。由于咱们是在一个范畴中，咱们知道从 $i_1$ 到 $i_1$ 的态射就是一个恒等态射，所以 g∘f 等于恒等态射。同理，f∘g 的结果也是恒等态射。这样就证实了 f 与 g 是互逆的，所以两个初始对象就是同构的。

注意，在上述证实中，咱们使用的是从初始对象到它自己的态射的惟一性。若是没有这个前提条件，咱们就没法证实『同构意义下』这部分。可是，为何须要 f 与 g 也是惟一的？由于初始对象不只在同构意义下具备惟一性，并且这个同构是惟一的。理论上，两个对象之间可能存在不止一种同构关系，虽然它们未在这里出现。这种『在同构意义下具备惟一性，并且这个同构是惟一的』是全部泛构造的一个重要性质。

积

还有一个泛构造，叫作积。咱们知道两个集合的笛卡尔积：序对的集合。可是积集合与成分集合（译注：参与积运算的集合），它们之间存在着什么样的链接模式？若是咱们能说清楚它，那么就可以将积推广到其余范畴。

从积到每一个成分，存在两个投影。在 Haskell 中，这两个函数被称为 fst 与 snd，它们分别从序对中拮取第一与第二个成员：

fst :: (a, b) -> a
fst (x, y) = x

snd :: (a, b) -> b
snd (x, y) = y

在此，这两个函数是采用参数的模板匹配来定义的，即对于任意序对 (x, y)，模板匹配能够从中抽取变量 x 与 y。

这些定义能够用通配符做进一步简化：

fst (x, _) = x
snd (_, y) = y

在 C++ 中，可使用模板函数来模拟，例如：

template<class A, class B>
A fst(pair<A, B> const &p) {
    return p.first;
}

借助这看上去很是有限的知识，咱们试着去定义集合范畴中对象与态射的模式，这种模式能够引导咱们去构造两个集合 a 与 b 的积。这个模式由对象 c 与两个态射 p 与 q 构成，p 与 q 将 c 分别连向 a 与 b：

p :: c -> a
q :: c -> b

全部的适合这种模式的 c 都会被认为是候选积，由于这样的 c 可能有不少。

例如，从 Haskell 类型中选择 Int 与 Bool，让它们相乘，并将 Int 与 Bool 做为候选积。

假设 Int 是候选积。Int 可以被认为是 Int 与 Bool 相乘的候选积吗？是的，它能，由于它具备如下投影：

p :: Int -> Int
p x = x

q ::  Int -> Bool
q _ = True

虽然至关无聊，但它符合候选积的条件。

还有一个 (Int, Int, Bool)，这是个三元组。它也是个合法的候选积，由于存在：

p :: (Int, Int, Bool) -> Int
p (x, _, _) = x

q :: (Int, Int, Bool) -> Bool
q (_, _, b) = b

可能你会注意到，第一个候选积过小了——它只覆盖了乘积的 Int 维，而第二个候选积又太大了——它复制了一个不必的 Int 维。

咱们尚未探索这个泛构造的其余部分：等级划分。咱们但愿可以比较这种模式的两个实例，也就是说对于候选积 c 与候选积 c'，咱们想对它们作一些比较，以便做出 c 比 c'『更好』这样的结论。若是有一个从 c' 到 c 的态射 m，虽然能够基于这个态射认为 c 比 c' 更好，可是这样仍是太弱了。由于咱们还但愿 c 伴随的投影 p 与 q 比 c' 的 p' 与 q' 『更好』或『更泛』，这意味着能够经过态射 m 从 q 与 q 分别构造出 p' 与 q'：

p' = p . m
q' = q . m

从另外一个角度来看，这些方程像是 m 因式化了 p' 与 q'。若将上面的这两个方程想象为天然数，将点符号想象为相乘，那么 m 就是 p' 与 q' 的公因式了。

上面只是为了创建一些直觉，如今来看一下伴随序对 (Int, Bool) 的两个经典的投影，fst 与 snd，它们要比刚才我给出的那两个候选积的投影更好。

第一个候选积的 m 是：

m :: Int -> (Int, Bool)
m x = (x, True)

这个候选积的两个投影可重构为：

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

对于第二个候选积而言，m 彷佛是惟一的：

m (x, _, b) = (x, b)

咱们说了 (Int, Bool) 要比前两个候选积更好。如今给出咱们的理由。问一下本身，咱们能找到某个 m'，它可以帮助咱们从伴随候选积的 p 与 q 重构出 fst 与 snd 么？

fst = p . m'
snd = q . m'

对于第一个候选积，q 老是返回 True，而咱们知道存在第 2 个元素是 False 的序对，所以没法从 q 重构 snd。

第二个候选积就不一样了，咱们可以在 p 或 q 运行后保留足够的信息，可是对于 fst 与 snd 而言，它们存在着多种因式化方式，由于 p 与 q 会忽略三元组的第 2 个元素，这就意味着咱们的 m' 能够在第 2 个元素的位置听任意东西，例如：

m' (x, b) = (x, x, b)

或

m' (x, b) = (x, 42, b)

等等。

总而言之，对于给定的任意类型 c，它伴随着两个投影 p 与 q，存在着惟一的一个 m 可将 c 映射为笛卡尔积 (a, b)，而这个 m 对 p 与 q 的因式化就是将 p 与 q 组合成序对：

m :: c -> (a, b)
m x = (p x, q x)

这样就决定了笛卡尔积 (a, b) 是最好的候选积，这意味着这种泛构造对于集合范畴是有效的，它涵盖了任意两个集合的积。

如今，咱们忘记集合，使用相同的泛构造来定义任意范畴中两个对象的积。这样的积并不是老是存在，可是一旦它存在，它就在同构意义下具备惟一性，并且这个同构是惟一的。

对象 a 与对象 b 的积是伴随两个投影的对象 c。对于任何其余伴随两个投影的对象 c' 而言，存在惟一的从 c' 到 c 的态射，这个态射能够因式化这两个投影。

一个高阶函数可以生成因子 m，这个高阶函数有时被称为因子生成器。对于本文的示例中，它是这样的函数：

factorizer :: (c -> a) -> (c -> b) -> (c -> (a, b))
factorizer p q = \x -> (p x, q x)

余积

同范畴论中每一个构造同样，积有一个对偶，叫作余积。将积的范式中的箭头反转，就能够获得一个对象 c，它伴随两个入射 i 与 j——从 a 到 c 的态射与从 b 到 c 的态射。

i :: a -> c
j :: b -> c

等级也反转了：对象 c 比 c' 『更好』的条件是，存在从 c 到 c' 的态射 m，它能够因式化入射：

i' = m . i
j' = m . j

『最好』的对象就是，具备惟一的态射从其自己指向其余模式，这种对象就叫作余积，而且若是它存在，那么它就在同构意义下具备惟一性，并且这个同构是惟一的。

两个对象 a 与 b 的余积是对象 c，当且仅当 c 伴随着两个入射，并且任何一个其余的伴随两个入射的对象 c'，只存在惟一的从 c 到 c' 的态射 m，而且 m 能够因式化这些入射。

在集合的范畴中，余积就是两个集合的不相交求并运算。集合 a 与集合 b 的不相交求并结果中的一个元素，要么是 a 中的元素，要么是 b 中的元素。若是两个集合有交集，那么不相交求并的结果会包含两个集合公共部分的两份拷贝。你能够将不相交求并运算结果的一个元素想象为贴着它所属集合的标签的元素。

对于程序猿而言，余积很容易理解，它不过是两种类型的带标签的联合。C++ 有联合类型，只不过它们没标签。若是你在程序中想跟踪哪一个联合的成员有效，必须用枚举类型自行定义标签。例如，int 与 char const * 的一个标签化联合类型以下：

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

两个射入能够实现为构造子或函数。例如，下面是第一个射入的函数实现：

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

它将一个整型类型射入 Contact。

带标签的联合被称为变体（Variant），boost 库里实现了一个泛型的变体 boost::variant。

在 Haskell 中，你能够将任意数据类型组合为带标签的联合，只需用竖线隔开数据构造子便可。上面 C++ 的 Contact 的示例能够翻译为：

data Contact = PhoneNum Int | EmailAddr String

这里，PhoneNum 与 EmailAddr 都是构造子（入射），也能够做为模式匹配（之后会讲）时所用的标签。例如，将电话号码构造为一个 Contact：

helpdesk :: Contact;
helpdesk = PhoneNum 2222222

对于 Haskell 而言，与基于内建的序对而实现的『正统』积不一样，『正统』的余积的既有实现是标准库中定义的 Either 数据类型：

Either a b = Left a | Right b

这个数据类型接受两个参数 a 与 b，它还拥有两个构造子：Left 接受类型 a 的值，Right 接受类型 b 的值。

正如咱们刚才所定义的积的因式生成器同样，咱们也能够为余积定义一个。对于给定的候选余积 c 以及两个候选入射 i 与 j，为 Either 生成因式函数的的因式生成器可定义为：

factorizer :: (a -> c) -> (b -> c) -> Either a b -> c
factorizer i j (Left a)  = i a
factorizer i j (Right b) = j b

非对称

咱们已经见识了两种对偶结构：终端对象可由初始对象的箭头反转而得到，余积可由积的箭头的反转而得到。不过，在集合的范畴中，初始对象与终端对象有着显著的区别，余积与积也有着显著区别。之后会看到积的行为像是乘法运算，终端对象扮演者 1 的角色，而余积的行为更像求和运算，初始对象扮演着 0 的角色。在特殊状况下，对于有限集，积的尺寸就是各个集合的尺寸的积，而余积的尺寸是各个集合的尺寸之和。

这一切都代表了集合的范畴不会随箭头的反转而出现对称性。

注意，空集能够向任意一个集合发出惟一的态射（absurd 函数），可是它没有其余集合发来的态射。单例集合拥有任意集合发来的惟一的态射，但它也能向任一集合（除了空集）发出态射。由终端对象发出的态射在拮取其余集合中的元素方面扮演了重要的角色（空集没有元素，所以没什么东西可拮取的）。

单例做为积与它做为余积有着天壤之别。要将单例 () 做为品质低劣的候选积，须要给它配备两个投影 p 与 q。因为积是泛构造，所以存在一个从 () 到积的态射 m。这个态射从积集合中选出一个元素——序对，它也因式化了两个投影：

p = fst . m
q = snd . m

这两个投影做用于单例的值 ()，上面那两个方程就变为：

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

由于 m () 是 m 从积集合中拮取的元素，p 所拮取的是第一个参与积运算的集合中的元素，结果是 p ()，而 q 所拮取的是第二各参与积运算的集合中的元素，结果是 q ()。这彻底符合咱们对积的理解，即参与积运算的集合中的元素造成积集合中的序对。

若单例做为候选的余积，就不会它做为候选的积那样简单了。咱们能够经过投影从单例中抽取元素，可是向单例入射就显得没有意义了，由于它们的『源』在入射时会丢失。从真正的余积到做为候选余积的单例的态射也不是惟一的。集合的范畴，从初始对象的方向去看，与从终端对象的方向去看，是有显著差别的。

这其实不是集合的性质，而是是咱们在 Set 中做为态射使用的函数的性质。函数，一般是非对称的，下面我来解释一下。

函数是创建在它的定义域（Domain）上的（在编程中，称之为全函数），它没必要覆盖余定义域（Codomain，译注：可能叫陪域更正式一些）。咱们已经看到了一些极端的例子（实际上，全部定义域是空集的函数都是极端的）：定义域是单例的函数，意味着它只在余定义域上选择了一个元素。若定义域的尺度远小于余域的尺度，咱们一般认为这样的函数是将定义域嵌入余定义域中了。例如，咱们能够认为，定义域是单例的函数，它将单例嵌入到了余定义域中。我将这样的函数称为嵌入函数，可是数学家给从相反的角度进行命名：覆盖了余定义域的函数称为满射（Surjective）函数或映成（Onto）函数。

函数的非对称性也表现为，函数能够将定义域中的许多元素映射为余定义域上的一个元素，也就是说函数坍缩了。一个极端的例子是函数使整个集合坍缩为一个单例，unit 函数干的就是这事。这种坍缩只能经过函数的复合进行混成。两个坍缩函数的复合，其坍缩能力要强过两者单兵做战。数学家为非坍缩函数取了个名字：内射（Injective）或一对一（One-to-one）映射。

固然，有许多函数即不是嵌入的，也不是坍缩的。它们被称为双射（Bijection）函数，它们是彻底对称的，由于它们是可逆的。在集合范畴中，同构就是双射的。

$$ \cdot $$

挑战

1. 证实终端对象在同构意义下具备惟一性，并且这个同构是惟一的。
2. 偏序集内的两个对象的积是什么？提示：使用泛构造。
3. 偏序集内的两个对象的余积是什么？
4. 用你喜欢的语言（Haskell 除外），实现与 Haskell 的 Either 等价的泛型类型。
5. 证实 Either 是比 int 更好的余积。int 伴随的两个入射是：

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

提示：定义一个函数

int m(Either const & e);

用它因式化 i 与 j。

6. 继续上一个问题，如何证实 int 不会比 Either 更好？

7. 依然继续上述第 5 个问题：下面的入射怎么样？

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

8. 针对 int 与 bool，给出一个品质低劣的候选余积，使之有多个态射抵达 Either。

参考文献

1. The Catsters, Products and Coproducts video.

致谢

感谢 Gershom Bazerman 对这篇文档的审阅以及针对性的讨论。

-> 下一篇：『简单的代数数据类型』