上一篇：声明式编程html

原文地址:https://bartoszmilewski.com/2...编程

彷佛在范畴论中全部事情都是相互联系的，而且均可以用不少角度观察。就拿积的泛构造来举例吧，既然咱们已经对函子和天然变换了解更多了，咱们能不能简化积的泛构造，或者也许，推广它？让咱们试试。segmentfault

积的构造始于选取咱们想要构造积的两个对象a和b。但选择对象到底是什么意思？咱们可否用更加范畴论的语言从新描述这个动做？两个对象构成了一个模式——很是简单的模式。咱们能够把这种模式抽象成一个范畴——一个很是简单的范畴，即使如此也是个范畴。咱们称之为2。它包含了两个对象，1和2，而且除了必要的两个恒等态射外没有其余态射。如今咱们把在C中选取两个对象重述为定义了一个从2到C的函子D。函子把对象映为对象，因此它的像就只是两个对象而已（或者若是这个函子坍缩了对象的话，也能够是一个，那也是ok的）。它也会映射态射——这里就仅仅是把恒等态射映为恒等态射。安全

这种方式的好处是创建在范畴的概念上，从而避免了诸如“选择对象”这样不精确的，狩猎采集时代的祖先们就在用的描述。不只如此，它还顺带了一个易推广的好处，由于彻底能够用些比2更加复杂的范畴来定义咱们的模式。markdown

不过，先让咱们继续（构造积）。定义一个积的下一步是选取候选对象c。一样地，咱们能够用一个从单例范畴出发的函子来重述这个选取。若是咱们用Kan延拓（Kan extension，中文不知道叫什么，有知道的童鞋告诉我啊，译者注）的话，确实不会有什么问题，可咱们还不能讲Kan延拓，因此咱们用另外一种技巧：从同一个2范畴到C的常函子Δ。在C中选取一个c能够用Δ_c。记住，Δ_c把全部对象都映为c而且把全部态射都映为id_c。架构

如今咱们有了两个从2到C的函子Δ_c和D，因此彻底能够求求它们之间的天然变换。由于2中只有两个对象，那么一个天然变换就会有两个份量。2的对象1被Δ_c映为c而被D映为a。因此Δ_c和D之间的天然变换在1上的份量就是从c到a的态射。咱们把它记做p。一样地，第二个份量是从c到b的态射q——b是2的对象2在D下的像。这就像极了咱们以前原始的积的定义中的那两个投影。因此咱们再也不说选取对象和投影这样的话了，而是说选取函子和天然变换。在这种简单的情形下变换的天然性以一种平凡的方式知足了，由于2中根本没有非平凡的态射（除了恒等态射）。app

若是把这种结构推广到不是2的范畴——例如，包含了非平凡态射的范畴——那么就要加上Δ_c和D天然变换的天然性条件。咱们把这样的变换叫作一个锥，由于Δ的像就像锥/金字塔的顶点，而锥的腰由天然变换的份量组成。而D的像就是这样一个锥的底。函数

通常来讲，为了构造一个锥，咱们会从一个定义了某种模式的范畴I出发。它是一个小范畴，一般来讲都是有限的。咱们选取一个从I到C的函子D称之（或D的像）为一个图表。咱们选取C中的某个c做为锥的顶点，并用它定义从I到C的常函子Δ_c。而后，Δ_c到D的天然变换就是咱们的锥了。对于一个有限大的I，锥就只是一族链接c到图表的态射：而图表是I在D下的像。ui

天然性须要保证图中全部的三角形（也就是金字塔的面）是交换的。事实上，选择I的任意态射f，函子D会把它映为C中的一个态射D f，它是某个三角形的底。而常函子Δ_c会把f映为c上的恒等态射。Δ把态射的两个端压为一个对象，而后四方交换图就变成了交换三角形。这个三角形的两臂就是天然变换的份量。spa

这就是一个锥了。咱们感兴趣的是那个泛锥（universal cone）——就像咱们从积定义中选了一个最普适的对象那样。

作这件事有不少方法。好比，给定一个函子D，咱们能够定义一个锥范畴。范畴中的对象就是锥。然而并非C中的每一个c均可以成为一个锥的顶点，由于从Δ_c和D之间可能不存在天然变换。

要让其成为一个范畴，咱们还须要定义锥之间的态射。而它们会被锥顶点之间的态射所彻底决定。但并非全部这样的态射均可以。回忆一下，在咱们的积的构造里，咱们引入了一个条件：候选对象（顶点）之间的态射必须是各个投影的公因子。好比：

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

在通常的情形下，这个条件就是说那些以“因子态射”做为一条边的三角形都要可交换。

链接两个锥的可交换三角形，h是因子态射（这里，比较低的锥是更“泛”的，它以 Lim D为顶点）

上面这句话是图注。因为思否的markdown基本不支持html，以后个人图注都会以引用来代替。（第一部分的译者也是如此作的）译者注。

咱们就把这些因子态射做为锥范畴中的态射。很容易检查这些态射能够复合，而且（锥范畴的）恒等态射就是恒等因子态射。所以锥能够造成一个范畴。

如今咱们就能够定义泛锥了。他就是锥范畴的终端对象。终端对象的定义是说全部其余对象到它都有一个惟一的态射。具体来讲，就是其余锥的顶点都有一个惟一的因子态射指向泛锥的顶点。这个泛锥就称做图表D的极限，Lim D（在印刷体里，你会常常看到在Lim符号下面有个指向I的左箭头）。一般，为了方便，咱们就把泛锥的顶点叫极限（或极限对象）

关于 Lim下的左箭头，译者目前没有在网上找到相应的印刷体资料，但左箭头总以为怪怪的。猜想颇有可能实际上是右箭头。译者注。

直觉上来讲极限把整个图表的性质体如今单个的对象上。例如，咱们的双对象图表的极限就是两个对象的积。积（和两个投影一块儿）包含了两个对象的全部信息，而且它是泛的，也就是它不包含冗余信息。

做为天然同构的极限

仍然有一些东西是如今这个极限的定义不能知足的。个人意思是，如今的极限定义已经可使用了，但咱们须要链接任意两个锥的三角形们的交换性条件。若是咱们能把它替换成某个天然性条件的话就优雅多了。但这要怎么操做呢？

咱们再也不讨论单独的锥而是关注一整个锥集（实际上，是锥范畴）。若是极限存在（——说的清楚点——如今不能保证它必定存在），那么这些锥当中就有那个泛锥。对于每一个其余的锥咱们有一个惟一的因子态射来把它的顶点c映为泛锥的顶点Lim D。（实际上，我能够省略“其余”这个词，由于有恒等态射把泛锥映到它本身，即泛锥自己平凡地因式化了本身。）让我重复一下重点：给定任意一个锥，那就有惟一的某个具体的态射。咱们就有了从锥到具体的态射的映射，而且是一一映射。

这个具体的态射是hom集C(c, Lim D)里的某个家伙。这个hom集里的其余伙伴就很不幸了，个人意思是它们不能因式化锥之间的映射。咱们想要作的是对于每个c,可以从集合C(c, Lim D)里挑出一个态射——一个可以知足特殊的交换性条件的态射。这听起来不是很像定义一个天然变换吗？确实是这样！

但和这个变换相关的函子是什么？

一个是c到集合C(c, Lim D)的映射。这是一个从C到Set的函子——它把对象映为集合。
这实际上是一个逆变函子。接下来是定义它在态射上的行为：咱们取一个c'到c的态射f:

f :: c' -> c

咱们的函子把c'变成了C(c', Lim D)。要定义函子在f上的行为（换句话说，要提高f），咱们必须定义C(c, Lim D)和C(c', Lim D)之间的映射。咱们选取C(c, Lim D)中的一个元素u而后看看可否把它映为C(c', Lim D)里的某个元素。hom集的元素是态射，因此咱们有：

u :: c -> Lim D

咱们把u在f前复合一下就获得了：

u . f :: c' -> Lim D

这就是C(c', Lim D)的一个元素了——因此咱们确实找到了一个态射的映射：

contramap :: (c' -> c) -> (c -> Lim D) -> (c' -> Lim D)
contramap f u = u . f

注意逆变函子的特征：c和c'的顺序是反的。

要定义一个天然变换，咱们还须要另外一个从C映到Set的函子。但这一次咱们考虑锥的集合。锥就是天然变换而已，因此咱们来看看天然变换的集合Nat(Δ_c, D)。从c到这个特殊的天然变换集之间的映射是一个（逆变）函子。咱们怎么证实？一样，让咱们定义它对态射的行为：

f :: c' -> c

f的提高应该是关于I到C的两个函子间天然变换（全体）的映射：

Nat(Δ_c, D) -> Nat(Δ_c', D)

咱们怎么样映射天然变换（全体）呢？每一个天然变换都是一种态射的选取——也就是它的份量——每一个I的元素选一个态射。某个α（Nat(Δ_c, D)里的一个家伙）在a(I的一个对象)上的份量是一个态射：

α_a :: Δ_c(a) -> D a

或者，带入常函子Δ的定义，

α_a :: c -> D a

给定f和α，咱们必须构造一个Nat(Δ_c', D)的元素β，它在a的份量也应该是一个映射

β_a :: c' -> D a

咱们很容易就能够把前者在f前复合一下来获得后者：

β_a = α_a . f

把这些份量合起来就是一个天然变换也是很容易证实的。

给定一个态射f，咱们就能这样按份量构造出两个天然变换间的映射。而这个映射就定义了该函子的contramap：

c -> Nat(Δ_c, D)

我所作的只是向你展现了两个C到Set的（逆变）函子。我尚未作任何假设——这些函子老是存在的。

附带一提，第一个函子在范畴论中扮演了重要的角色，咱们会在讲到米田引理的时候再次看到它。这种从任意范畴C到Set的逆变函子有个名字：“预层”。第一个仍是一个可表预层。第二个函子也是个预层。

如今咱们有两个函子了。咱们能够聊聊它们的天然变换了。好，再也不啰嗦别的，结论是：一个I到C的函子D有一个极限Lim D当且仅当我刚刚定义的这两个函子间有个天然同构。

C(c, Lim D) ≃ Nat(Δ_c, D)

我来提醒你一下天然同构是什么。天然同构就是一个每一个份量都是一个同构——也就是一个可逆的态射——的天然变换。

我不打算证实这个陈述。若是不用冗长的证实，那这个过程很是直接。当处理天然变换时，你一般会关注份量，它们就是些态射。这里，由于两个函子的终点都是Set，因此天然同构的份量就会是些函数，它们是些高阶函数，由于它们从hom集映到天然变换的集合。又一次，你能够分析一个函数，看看它对它的参数作了什么：这里的参数是个态射——一个C(c, Lim D)的家伙——它的结果是个天然变换——一个Nat(Δ_c, D)的家伙，或者是咱们说的锥。而后，这个天然变换的份量又是一些态射。因此作到底以后它们都是态射，若是你能跟踪它们，你就能证实这个结论。

最重要的结果是这个同构的天然性条件就刚恰好是锥映射的交换性条件。

做为一些更具诱惑力的东西的铺垫，咱们说集合Nat(Δ_c, D)能够当作是函子范畴里的hom集；因此咱们的天然同构关联了两个hom集，这揭露一种甚至更广泛的关系，伴随。

极限的例子

咱们已经看到了范畴积就是由一个简单的叫作2的范畴生成的图表的极限。

有一个甚至更为简单的极限的例子：终端对象。你的第一反应多是想用单例范畴导出终端对象，但事实比那还简单：终端对象是由空范畴生成的极限。一个空范畴上的函子不会选择任何对象，因此锥就仅仅缩成了顶点。泛锥就是那个从其余顶点出发有惟一的态射到达的孤单的顶点。你能够看到这就是终端对象的定义。

下一个有意思的极限叫等化子。它是一个由含有两个对象的范畴生成的极限，这个范畴在那两个对象上有两个平行态射（以及，必定会有的，恒等态射）。这个范畴在C中选择了一个由两个对象a和b以及两个态射f和g组成的图表：

f :: a -> b
g :: a -> b

为了经过这个图标构建一个锥，咱们必须加上顶点c和两个投影：

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

咱们有两个必须交换的三角形：

q = f . p
q = g . p

这告诉咱们q能够被其中一个式子惟一地决定，好比q = f . p，而且咱们能够把它从图中省略。所以剩下的就只有一个条件：

f . p = g . p

考虑这个条件的方法以下，若是咱们只关注Set，那么函数p的像会选择a的一个子集。当限制在这个子集上时，f和g是相等的。

好比，取a为由x和y参数化的二维平面，取b为实直线，而后取：

f (x, y) = 2 * y + x
g (x, y) = y - x

这两个函数的等化子就是实数集（也就是那个顶点c）和函数：

p t = (t, (-2) * t)

注意(p t)定义了二维平面上的一条直线。在这条直线上，这两个函数相等。

固然，还有其余的集合c'和函数p'能够知足等式：

f . p' = g . p'

但它们会被p唯一地因式化。好比说，咱们能够取单例集()做为c'和函数

p' () = (0, 0)

这是一个好的锥，由于 f (0, 0) = g (0, 0)。但它并非泛的，由于它能够经过h惟一的因式化：

p' = p . h
h () = 0

所以一个等化子就能解形如f x = g x的方程。但它更加通常，由于它是从对象和态射的角度定义的，而不是用代数学。

一个更加通常的解方程的思路体如今另外一个极限上——回拉。咱们仍然有想要让其相等的两个态射，但此次它们的定义域不一样。咱们从一个形状像1->2<-3的三对象范畴出发。这个范畴对应的图表有三个对象a，b和c，以及两个态射：

f :: a -> b
g :: c -> b

这个图表一般被称做一个余扩张。

在这个图表上构造的锥由一个顶点d和三个态射组成：

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

交换性条件是说r被其余态射彻底地决定了，能够从图中略去。因此咱们就只剩下下面的条件：

g . q = f . p

一个回拉是具备下面这种形状的泛锥。

像刚刚那样，若是你只关注集合的话，你就能够把对象d当作一些分别来自a和c的元素的序对，对它们来讲f在第一个份量上做用的结果与g在第二个份量上的相等。若是这么说仍是有些通常，考虑一个特殊的情形：g是常数函数g _ = 1.23（假定b是实数集）。也就是你实际上要解方程：

f x = 1.23

这时，c的选择可有可无（只要它不是空集就行），因此咱们能够取单例集。集合a，比方说，能够是个三维向量的集合，而f计算向量长度。那么这个回拉就是序对(v, ())的集合，其中v是长度是1.23的向量（也就是方程sqrt (x^2+y^2+z^2) = 1.23的解），而()是单例集的那个无趣的元素。

但回拉还有更通常的应用，编程中也有这样的应用。好比，把C++的类想成一个范畴，其中的态射是链接子类和父类的箭头。咱们会把继承想成一种传递性，因此若是C继承了B而B继承了A那么C继承了A（毕竟，你给建立一个指向C指针就须要一个指向A的指针）。而且，咱们假定C继承了C本身，因此对每一个类咱们都有了恒等态射。这样子类就和子类型匹配了。C++也支持多继承，因此你能够构造出一个菱形继承表，B和C继承了A，第四个类D多继承了B和C。通常来讲，D会有两个A的拷贝，但这不是咱们所指望的；但你能够利用虚继承来只获得一个A的拷贝。

让D成为这个图表的一个回拉到底是什么意思？这是说任意一个多继承B和C的类E也是D的一个子类。这一点在子类型没有实质意义的C++里并不能直接表示出（C++编译器不会推断这种类关系——它须要“鸭子类型”）。但咱们能够放下子类型关系，转而问从E到D的一个转换是否安全。若是D是B和C的最最瘦的结合方式，没有新增数据和方法的重载，那么这种转换就是安全的。固然，若是B和C的某些方法有命名冲突的话，就没有这样的回拉了。

回拉在类型推导里还有更出色的应用。咱们常常会有求两个表达式的一致类型的须要。好比，假如编译器想要推断下面的函数的类型：

twice f x = f (f x)

编译器要先给全部变量和子表达式赋初始类型。特别地，它能够赋成：

f       :: t0
x       :: t1
f x     :: t2
f (f x) :: t3

这时编译器会推断出：

twice :: t0 -> t1 -> t3

编译器也会基于函数应用的规则想出一个约束的集合：

t0 = t1 -> t2 —— 由于f做用在了x上
t0 = t2 -> t3 —— 由于f做用在了(f x)上

这些约束必须在寻找一组类型（或类型变量）时同时（一致地）知足，当把这些未知类型带入这两个表达式时，可以获得同一种类型。一个这样的代换是：

t1 = t2 = t3 = Int
twice :: (Int -> Int) -> Int -> Int

可是呢，明显，这不是最通常的那个。最通常的代换能够用一个回拉得到。我不会讲那些细节，由于它们超出了这本书的范围，但你能够相信这个结果应该是：

twice :: (t -> t) -> t -> t

其中t是一个自由的类型变量。

余极限

像范畴论中全部的构造同样，极限在反范畴中也有一个对偶的样子。你把一个锥的全部箭头的方向都反转一下，就获得了一个余锥，而最泛的那个就叫余极限。注意这种反转也会影响因子态射，它如今从那个最泛的余锥射到其余余锥。

余锥和链接两个顶点的因子态射。

余极限的典型例子就是余积，它对应的是咱们以前在积的定义中用到的2范畴生成的图表。

积和余积各自以不一样的方式体现了一对对象的本质。

就像终端对象是一个极限同样，初始对象是对应由空范畴生成的图表的余极限。

回拉的对偶叫作外推。它基于一个由范畴1<-2->3生成的叫作扩张的图表。

连续性

我早前说过，从函子从不破坏既有的联系（态射）这一点上说，它很是接近范畴中的连续映射的想法。一个从范畴C到范畴C'的连续函子F的实际定义还包括了一个保持极限的条件。每一个C中的图表D能够经过简单地复合两个函子映射为C'中的图表F ∘ D。F的连续性条件是说，若是图表D有极限Lim D，那么图表F ∘ D也有一个极限，而且等于F (Lim D)。

注意，由于函子把态射映为态射，把复合映为复合，一个锥的像也老是一个锥。一个交换的三角形夜总会映为一个交换的三角形（由于函子保持复合）。这一点对因子态射也是成立的：因子态射的像也是一个因子态射。因此每一个函子都是几乎连续的。可能出错的是惟一性条件。C'中的因子态射可能不惟一。C'中也可能会有一些在C中不成立的其余的“更好的锥”。

hom函子就是一个连续函子的例子。回忆一下hom函子C(a, b)，它在第一个变量上是逆变的，在第二个变量上是协变的。换句话说，它是一个函子：

C^op x C -> Set

看过第一章的朋友应该见过C ^op，它是范畴C的经过把全部箭头反向导出的反范畴。

固定它的第二个参数，hom集函子（这时它是个可表预层）会把C的余极限映为Set的极限；固定它的第一个参数，它就把极限映为极限。

在Haskell中，一个hom函子就是将两个类型映为一个函数类型的映射，因此它就仅仅是一个参数化的函数类型。当咱们固定第二个参数时，好比取为String，咱们获得了逆变函子：

newtype ToSring a = ToString (a -> String)
instance Contravariant ToString where
    contramap f (ToString g) = ToString (g. f)

连续性是说ToString应用到一个余极限上时，好比说余积Either b c，就会获得一个极限；在如今这种状况下就是两个函数类型的积：

ToString (Either b c) ~ (b -> String, c -> String)

这没错，Either b c上的任意函数都会用一个带有两种情形的case语句来实现，这要提供一对函数。

相似地，当固定hom集的第一个参数时，咱们获得了熟悉的reader函子。它的连续性是说，好比吧，任何返回一个积的函数都等价于一个函数的积；具体来讲就是：

r -> (a, b) ~ (r -> a, r -> b)

我知道你如今在想什么：你不须要范畴论就能够想出它们，而且你是对的！尽管如此，这些结果只用一些不涉及到比特和字节、处理器架构、编译技术或甚至lambda演算的基本原理就能获得仍是让我震撼。

若是你对“极限”和“连续性”的命名由来很好奇的话，其实它们是对应的微积分观念的一个推广。在微积分中，极限和连续性是用开集来定义的。开集定义了拓扑，而拓扑构成了一个范畴（偏序集）。

挑战

1. 你会如何在C++的类范畴中描述外推？
2. 证实恒等函子Id :: C -> C的极限是初始对象。[事实上，Id对应的锥只有一个，它自动就成了最通常的那个，译者注]
3. 一个给定集合的全部子集构成了一个范畴。若是一个子集是另一个子集的子集，那么它们之间就有一个箭头做为态射（即态射定义为“包含于”，译者注）。在这个范畴里两个集合的回拉是什么？外推呢？初始对象和终端对象呢？
4. 你能不能猜一猜等化子是什么？
5. 证实，在一个具备终端对象的范畴里，指向终端对象的回拉是积。
6. 相似地，证实从初始对象（若是存在的话）指出的外推是余积。

致谢

感谢Gershom Bazerman检查个人数学和逻辑，和André van Meulebrouck在编辑上的帮助。

下一篇：自由幺半群