上一篇：极限与余极限程序员

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

不管是在范畴论中仍是在编程中，幺半群都是个重要的观念。范畴对应着强类型的语言，而幺半群对应着无类型的语言。由于在幺半群里你能够复合任意两个箭头，就像无类型语言中你能够复合任意两个函数同样（固然，在你执行程序时可能以一个超时的错误而了结）。segmentfault

咱们已经看过幺半群能够描述成一个单对象的范畴，在那个范畴里全部的逻辑都被变成了态射的复合规则。这个范畴模型和更传统的集合论意义下的幺半群定义彻底等价，那个定义是说咱们把两个元素“相乘”获得第三个元素。这个“乘法”过程能够被进一步解剖为先构建一个元素的序对而后把这个序对指定为一个已有的元素——它们的“积”。app

咱们把乘法的第二部分——把序对指定为已有的元素——丢掉会发生什么？好比说，咱们能够从任意一个集合出发，构建全部可能的序对，而后把它们叫作新的元素。而后咱们用这些新的元素再次构建全部可能的序对，以此类推。这是一个链式反应——咱们会不不休止地加入新的元素。这样的结果是个无限集，几乎就是一个幺半群。但一个幺半群还须要一个单位元和结合律。固然没问题，咱们能够添加一个特殊的单位元而且令某些序对相等——刚恰好知足单位元和结合律。函数

让咱们看看在具体例子里这是怎么作的。咱们从一个有两个元素的集合{a, b}出发。咱们将会把它们叫作自由幺半群的生成元。首先，咱们添加一个特殊元素e做为单位元。接着，咱们加入元素的全部序对叫作“积”。a和b的积就是序对(a, b)。b和a的积就是序对(b, a)，a和a的积就是序对(a, a)，b和b的积就是序对(b, b)。咱们还能用e构建像(a, e)，(e, b)等这样的序对，但咱们会把它们指定成a，b，等等。因此这一轮咱们只添加了(a, a)，(a, b)，(b, a)和(b, b)，并获得了集合{e, a, b, (a, a), (a, b), (b, a), (b, b)}。spa

下一轮里咱们会加进来一些像(a, (a, b))，((a, b), a)等等的元素。这时咱们就必需要保证知足结合律，因此咱们会把(a, (b, a))指定为((a, b), a)等等。换句话说，咱们不须要内部括号。code

你能够猜一下这个过程的最后结果是什么：咱们会创造出a和b的全部可能的列表。实际上，若是咱们用空列表表示e，咱们就会看到咱们的“乘法”和列表链接没有任何不一样。对象

这种不断生成可能的元素组合而且作一个最小数目的指定——仅仅为了知足法则——的构造就叫一个自由构造。咱们刚刚作的就只是用生成元{a, b}构造了一个自由幺半群。blog

Haskell中的自由幺半群

Haskell中的两个元素的集合等价于Bool类型，这个集合生成的自由幺半群等价于[Bool]类型（Bool的列表）。（我故意忽略了无限大列表的问题）排序

Haskell的幺半群是用类型类定义的：

class Monoid m where
    mempty  :: m
    mappend :: m -> m -> m

这只是在说每一个Monoid必须有一个叫mempty的幺元和一个叫mappend的二元函数（乘法）。单位元（律）和结合律不能在Haskell中表达，必须在每次实例化幺半群的时候有程序员验证。

任意类型a的列表构成一个幺半群的事实由这个实例的定义描述：

instance Monoid [a] where
    mempty  = []
    mappend = (++)

这是说空列表[]是单位元，而列表链接运算(++)就是那个二元运算。

就像咱们已经看到的那样，一个a类型的列表对应着由集合a充当生成元的自由幺半群。天然数集带上乘法运算并非一个自由幺半群，由于咱们指定了太多的积。做为例子比较一下：

2 * 3 = 6
[2] ++ [3] = [2, 3] // 和[6]不一样

此处做者举的例子多少有些使人混淆。在原文的评论区也有不少人和做者讨论了该问题，想看相关内容的读者能够移步原文评论区。天然数的确不能够一个自由幺半群，就算选择素数集做为生成元， 2*3=3*2=6这样的交换律也是在自由幺半群定义以外的东西。此处做者的例子大概是想说在天然数中 2*3=6，而在自由幺半群中不能够把这样一个乘法算式的结果明确指定为像 6这样的某个既有的数字（即这种指定必定不是自由幺半群所必需的，从而导出的必然不是自由幺半群），只能表示为序对 [2, 3]的形式。译者注。

这很容易懂，但问题是，咱们可否在范畴论中表示这种自由构造，而在范畴论中咱们没法观察对象的内部？咱们将会用到咱们的主角：泛构造。

第二个感兴趣的问题是，是否任意一个幺半群都能经过一些，比那些仅仅知足法则的最少数目的指定更多的指定，来从自由幺半群得到？你会看到泛构造能够直接获得它。

自由幺半群的泛构造

若是你想一想咱们以前有关泛构造的经验，你可能就会注意到它并非那么像挑一个最符合某个模式的对象那样构造对象的。因此若是咱们想用泛构造“构造”一个自由幺半群的话，咱们必须考虑幺半群的一整个族而后从里面挑一个。咱们须要一整个要选取（对象）的幺半群的范畴。但幺半群能构成范畴吗？

让咱们先把幺半群看做带上附加结构的集合，附加结构由单位元和乘法定义。咱们要选一些保持幺半群结构的函数做为态射。这种能保持结构的函数被称做同态。一个幺半群的同态必须把两个元素的积映为这两个元素像的积：

h (a * b) = h a * h b

并且它必须把单位元映为单位元。

这个同态的定义就是抽象代数中的定义，注意，等号先后的两个乘法所在的幺半群是不同的。译者注。

好比，考虑一个从整数列表到整数的同态。若是咱们把[2]映为2，把[3]映为3，那咱们就必须把[2, 3]映为6，由于链接操做

[2] ++ [3] = [2, 3]

变成了乘法

2 * 3 = 6

如今让咱们忘掉那些个幺半群的内部结构，仅仅把它们看做这些对应的态射链接的对象。你就能获得一个幺半群范畴Mon。

好吧，可能刚刚咱们忘掉了内部结构，让咱们来看一个重要的性质。每一个Mon的对象都能平凡地映为一个集合。这就仅仅是它地元素组成的集合。这个集合叫作承载集。事实上，咱们不只能把Mon的对象映为集合，咱们还能把Mon的态射（同态）映为函数。仍是那句话，如今看起来有些无趣，但立刻就能用到了。这个从Mon到Set的态射其实是个函子。由于这个函子“忘掉”了幺半群的结构——一旦咱们到了扁平的集合上，咱们就不会再区分谁是单位元或者关心乘法了——它叫作遗忘函子。遗忘函子常常出如今范畴论中。

咱们如今有了两种不一样的看待Mon的视角。咱们能够像其余的包含对象和态射的范畴那样看它。这种视角下，咱们不会看到幺半群的内部结构。咱们对某个特定的对象所能说的就只有它经过态射和它本身以及其余对象相关联。态射的“乘法”表——复合规则——是来源于另外一个视角：做为集合的幺半群。就算步入了范畴论咱们也不能彻底丢掉这种视角——咱们仍然要经过遗忘函子使用它。

为了用泛构造，咱们须要定义一个特殊的性质，这个性质可让咱们对幺半群范畴排序而后挑出最好的那个看成自由幺半群。可是自由幺半群是经过它的生成元定义的。不一样的生成元的选择会导出不一样的自由幺半群（一个Bool列表和一个Int列表并不同）。咱们的构造必须从一个生成元的集合开始，因此咱们回到了集合！

这就是遗忘函子可以显身手的地方了。咱们能够用它给咱们的幺半群拍X光片。咱们能够在这些家伙的X片上指定生成元。它是这么工做的：

咱们从一个生成元集合x出发。这是个Set中的集合。

咱们想要匹配的模式由一个幺半群m——Mon的一个对象——和一个Set中的函数p构成：

p :: x -> U m

其中U就是咱们的从Mon到Set遗忘函子。这是个奇怪的异质模式——一半在Mon里一半在Set里。

想法是函数p会在m的X片中指定生成元的集合。在集合中指定一些点的函数（它们可能会坍缩这些点）有些讨厌，不过不要紧。它们都会在泛构造中排序，而这会挑出那个最好的表明。

这里可能有些使人费解，但只要注意到x是已经预先给定的的话，这一切就会瓜熟蒂落：也就是说，函数 p已知一个预先给定的生成元集合 x，而后把 x的每个元素都映为 m的集合中的某个元素，这就像是从 m的集合中挑一些元素做为其生成元集，而且这个新集合不能比 x更大。

咱们还必须定义候选者们的排名方式。假定咱们还有另外一个候选者：一个幺半群n和在它的X片中指定生成元的一个函数：

q:: x -> U n

咱们说m比n更好是说存在一个幺半群的态射（保持结构的同态）：

h :: m -> n

它在U下的像（记住，U是个函子，因此它会把态射映为函数）经过p因式化了（其余这样的函数）：

q = U h . p

若是你把p看做选取m的生成元；q看做在n中选择“一样的”生成元；而后你就能把h看做两个幺半群的生成元间的映射了。记住,由定义，h能够保持幺半群的结构。这就意味着一个幺半群的两个生成元的积会映射到第二个幺半群的两个对应的生成元的积，以此类推。

这种排名方式就能用来找到最好的那个候选者——自由幺半群了。这儿是定义：

咱们说 m（连同函数 p）是生成元为 x的自由幺半群当且仅当有 惟一的从 m到其余幺半群 n（连同函数 q）的知足上述因式分解性质的态射 h。
（容我再自做多情地提醒一下，全部用泛构造方式所作的定义中的惟一均是指在同构的意义下惟一，这里也不例外，译者注。）

刚好，这就能够回答咱们的第二个问题。函数U h就能够把U m的多个对象坍缩成U n的一个对象。这个坍缩对应了在自由幺半群中对更多的元素进行指定的过程。所以，任意的由生成元x获得的幺半群均可以经过对x上自由幺半群进行一些指定来获得。而自由幺半群就是仅进行最小数目的指定而获得的那个。

咱们在讲到伴随时还会遇到自由幺半群。

挑战

1. 你可能会以为（就像我最初那样）幺半群同态要保持单位元的条件是多余的。毕竟，咱们知道 对于全部的a

   h a * h e = h (a * e) = h a

   因此h e就是一个右结合的单位元（相似地，左结合的单位元）。问题在于对全部的a， h a可能只能取到靶幺半群的一个子群。这样在h的像以外就可能有个“真正”的单位元。 请证实两个幺半群之间保持乘法的态射必须自动地保持单位元。

2. 考虑一个从带有列表链接操做的整数列表到带有乘法的整数的幺半群同态。空列表[]的像是什么？假定全部的单元素列表被映射为他们中的那个整数，就是说[3]映为3，等等。[1, 2, 3, 4]的像是什么？有多少个不一样的列表映为整数12？这两个幺半群之间是否还有别的同态？
3. 单例集生成的自由幺半群是什么？你能不能把它当作什么东西的同构？

致谢

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

下一篇：可表函子