Haskell和自然之代数篇 (5-3)

这是一个一次多项式，一次项的系数是类型()。在Hask 范畴中，多项式函数是存在不动点的。这个F 函数（NListF 函数）的不动点就是自然数NList，因F 是类型上的函数，定义域是Hask 范畴，值域也是Hask 范畴，所以这是一个Hask 范畴上的自函子。所以也是自函子F （自函子NListF）。

自函子F 的类型变量x 除了可以取值为自函子F 的不动点，即自然数NList，还可以取为Hask 范畴上的其他值。当类型变量x 取值为不动点，即自然数NList 时，由不动点函数的定义，我们有In 函数来将类型F (Fix F) 的值变换为类型Fix F 的值，其有如下的类型签名：

newtype Fix f = In { out :: f (Fix f) }

In :: f (Fix f) -＞ Fix f

type NList = Fix NListF -- NList 是NListF 的不动点

In :: NListF NList -＞ NList

In NNilF = NNil

In (NConsF () n) = NCons () n

当类型变量x 取值不是自函子F 的不动点时，我们同样有一个函数将类型F x 的值变换为x 的值，定义如下：

alg :: f x -＞ x

alg :: NListF x -＞ x

当类型变量x 分别取值Int 和String 时，函数alg 分别有如下的实现：

algInt :: NListF Int -＞ Int

algInt NNilF = 0

algInt (NConsF () i) = 1 + i

algAs :: NListF String -＞ String

algAs NNilF = []

algAs (NConsF () as) = 'A' : as

现在可以看到，自函子F 的类型变量x 每取一个值对应了一个alg 函数，将这两者拼在一起就有(x, alg)。我们可以将(x, alg) 看成一个对象，而类型变量x 和y 之间的函数g :: x -＞ y 和各自的alg 函数满足如下的关系：

g . alg_x = alg_y . F g

nlToInt . In = algInt . NListF nlToInt

nlToCharAs . In = algAs . NListF nlToCharAs

因此，g 可以看成对象(x, alg_x) 和对象(y, alg_y) 之间的态射，x 和y 称为承载对象，所有的(x, alg) 对象和这些对象之间的态射构成了一个范畴，我们称之为F-Alg 范畴。这个范畴的初始对象是(NList, In)，对任意一个承载对象x，都存在一个唯一的态射f: (NList, In) -＞ (x, alg)。

FNList Ff Fx

ln αlg

NList f x

F-Alg范畴初始对象和态射

Fx Fg Fy

αlg-x αlg-y

x g y

F-Alg范畴对象之间的态射

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。