manbetx官网手机版于是单位半群 List a和单位半群 m 之间存在唯一的态射

当前位置:manbetx官网手机版 > manbetx官网手机版 > manbetx官网手机版于是单位半群 List a和单位半群 m 之间存在唯一的态射
作者: manbetx官网手机版|来源: http://www.sihmiaomu.com|栏目:manbetx官网手机版

文章关键词:manbetx官网手机版,自由半群

  在上一篇文章parker liu:从单位半群到单子中,已经给大家详细介绍了如何从单位半群一步步得到单子。但单子是如何构造出来的呢,即如何从类型得到单位半群,从函子得到单子呢?在这篇文章中,我将给大家介绍最一般的单位半群和单子的构造方式,即单位半群和单子的自由构造。

  我们知道一些具体的单位半群,如自然数、布尔值,那有没有一种方法从一般的类型构造出单位半群呢?答案是有的,这就是单位半群的自由构造。同样的,单子也存在着自由构造。

  我们先来看看单位半群的自由构造是怎么样的。我们知道单位半群有如下的定义:

  那我们如何来从类型 a 来构造出一个单位半群 m 呢?假装我们是万能的上帝,上帝说要有光,于是就有了光。我们说要有单位半群 m,于是就有了单位半群 m。

  上面的Nil是一个无参数构造子,等价于Unit(也就是()),即Hask这个幺半范畴的单位元i,而Cons则和Hask这个幺半范畴的张量积⊗等价。于是上面的List a的定义相当于定义了一个函子 F x = i + a ⊗ x,其中List a是函子 F x 的不动点,(List a, in)则是F x这个函子构造的 F-Alg 范畴的初始对象。可以证明函子 F x = i + a ⊗ x 的不动点是一个单位半群,manbetx官网手机版于是就有了单位半群List a。

  我们考虑以所有单位半群 m 为对象的由F x构造的 F-Alg 子范畴,因 (List a, in) 是F-Alg 范畴的初始对象,所以必然存在一个唯一的从 (List a, in) 到 (m, fm) 的态射,这个态射也是 List a 到 m 的态射。于是单位半群 List a和单位半群 m 之间存在唯一的态射。

  若我们把单位半群看成一个对象,则单位半群之间存在态射,于是所有单位半群构成了单位半群范畴Mon。上面的单位半群 List a是这个单位半群范畴Mon的初始对象,称之为自由单位半群。List a 是函子 F x 的不动点,我们将其展开,即不停的将x = i + a ⊗ x 代入到 i + a ⊗ x 中,得到下面的表达式:

  这样我们就有了从类型 a 到单位半群 List a 的最一般的构造方式,上式就是单位半群上的自由构造。

  对于由自函子构成的幺半范畴,其对象是自函子 F,单位元是自函子 Id,张量积是函子的组合运算 ◦,我们也同样的有从自函子到自函子的幺半范畴上的单位半群(就是自由单子)的最一般的构造方式,自由单子是高阶函子 HF (Free F) = Id + F ◦ Free F 的不动点,是所有单子构成的单子范畴的初始对象,这个自由单子的Haskell代码定义如下:

  我们可以看到,自由单子和自由单位半群类似,都是形如 F x = i + a ⊗ x 的函子的不动点。因此,自由单子也有类似自由单位半群的展开式:

  这就是单子的自由构造。我们使用自由单子的Haskell代码的定义,可以得到更直观的展开式:

  有了单位半群和单子的一般构造方式,我们就可以用来构造自由单位半群和自由单子,再将其求值到具体的特定的单位半群和单子。

  我们先来看单位半群,从任意类型 a 得到的自由单位半群List a定义如下:

  接下来我们来看单子的情况,从任意函子 F 得到的自由单子 Free F 定义如下:

  这也是函子 F x = i + a ⊗ x 的不动点 Fix F,(Fix F, in) 是这个函子构成的 F-Alg 范畴的初始对象。不过这里的函子 F 的定义中的 a 也是一个函子,函子 F 是一个高阶函子,即作用在函子上的函子。对应的F-Alg范畴也是高阶的,Fix F是一个函子,不是一个类型。用Haskell表示如下:

  liftMF是一个非常有用的函数,其将任意一个函子的值提升为自由单子的值,使得我们可以方便的构造自由单子。构造好自由单子后,再定义一个HAlg,我们就可以对自由单子Flist f求值了。下面我们定义了一个函子StackF,由这个函子构造了一个自由单子HFix (FreeMF StackF),然后定义了两个不同的HAlg,分别用于计算自由单子HFix (FreeMF StackF)的值,和打印自由单子HFix (FreeMF StackF)的表达式。

网友评论

我的2016年度评论盘点
还没有评论,快来抢沙发吧!