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

F-Alg 范畴中初始对象到其他对象到态射可以由其他对象的alg 函数得到，将其他对象的alg 函数变换为初始对象到该对象的态射的变换函数称为cata 函数，其定义如下：

type Alg f a = f a -＞ a

cata :: Functor f =＞ Alg f a -＞ Fix f -＞ a

cata alg = go alg

where go alg = alg . fmap (go alg) . out

我们在前一篇文章中定义了自然数N 的加法，同样的NList 也存在加法，定义如下：

plus :: NList -＞ NList -＞ NList

plus NNil nl2 = nl2

plus (NCons () nl) nl2 = NCons () (plus nl nl2)

通过这个加法定义，可以容易的证明其满足如下的单位元定律和结合律。

plus NNil nl == nl plus nl NNil == nl -- 左右单位元定律

plus nl1 (plus nl2 nl3) == plus (plus nl1 nl2) nl3 -- 结合律

因此，自然数类型NList是一个幺半群（monoid），单位元是NNil，二元运算是plus。实际上，对于自函子Fx＝1＋() × x ，我们可以证明这个自函子的F-Alg 范畴中的承载对象x 是一个幺半群。而(NList, In) 是这个范畴的初始对象，因此存在一个唯一的态射f: (NList, In) -＞ (x, alg)，也即f: NList -＞ x，其中f = cata alg，所以NList 是所有承载对象x 构成的幺半群范畴的初始对象，我们称这个初始对象NList 为自由幺半群。

我们适当扩展一下，把自函子Fx＝1＋() × x 中固定的() 作为一个参数a，于是我们就得到如下的自函子：

G α x＝1＋α × x

Haskell形式的定义为：

data ListF a x = NilF

| Cons a x

这也是一个一次多项式，一次项的系数是类型参数a，因此这个自函子G a，即自函子ListF a，也存在一个不动点，我们称之为List a，其定义如下：

data List a = Nil

| Cons a (List a)

令Ga = G a，有自函子Gα＝1＋α × x，我们也同样得到了Ga-Alg 范畴，同理可得，x 也是一个幺半群，自函子Ga 的不动点List a 也是一个自由幺半群。List a就是类型a 的列表，是Haskell中常见的列表类型[a]。

我们再次扩展一下，把自函子G a 中的参数a 扩展为一个函子，乘法× 扩展为函子的张量积运算⨂，而x 则扩展为函子g，1 则是Id 函子。这样有了一个高阶自函子HF f g 的定义：

Hғ f g＝1＋f ⨂ g

这同样是一个一次多项式，一次项的系数是函子参数f ，因此这个自函子HF f，也存在一个不动点。当张量积运算是函子的组合，即(f⨂g)α＝f(g α) 时，自函子HF f 的定义是：

data FreeMF f g a = PureMF a

| FreeMF (f (g a))

其不动点也是一个函子，我们称之为自由单子(Free Monad)，其定义如下：

data Free f a = Pure a

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