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

在函数nlToInt中，NNil 对应了整数0，NCons对应了整数的加法运算+ ，() 对应了整数1，递归的NList部分则对应了函数nlToInt的递归调用nlToInt nl。

在函数nlToCharAs中，NNil 对应了空列表[]，NCons对应了加法运算+ ，() 对应了字母'A'，递归的NList部分则对应了函数nlToCharAs的递归调用nlToCharAs nl。

我们现在有了更清晰的自然数类型的定义NList，但是这个定义还是使用了递归的形式，在代数数据类型中不好表示和分析这个递归形式。我们接下来使用一些数学技巧来消除这个递归形式。

在上面的自然数类型NList的定义中，可以将NList看成一个非递归函数的不动点，即NList = NListF NList，可以看到，这个非递归的NListF 函数（这是一个类型上的函数）有一个参数，命名为x。当x 是类型NList时，这个函数的结果仍然是NList，于是用x 代替NList，则参考NList的定义我们可以得到这个非递归函数NListF 的定义：

data NListF x = NNilF

| NConsF () x -- 用x 代替了递归定义的NList

那如何从非递归函数NListF 得到其不动点类型NList 呢，我们定义一个如下的不动点函数Fix，其将计算得到任意一个存在不动点的非递归函数F 的不动点Fix F。

-- newtype 表示Fix f 和 f (Fix f) 是等价的，实际上在运行时里面是完全一样的。

newtype Fix f = Fix { unFix :: f (Fix f) } -- Fix f 是函数f 的不动点

-- Fix 和unFix 是一对同构函数

上面的Fix 的定义中，newtype 是Haskell 中的一种特殊的定义新数据类型的方式，表示newtype 定义的新数据类型Fix f 和原来的数据类型f (Fix f) 是等价的，在Haskell 的运行时里的表示是完全一样的，只是在Haskell 中的类型层面上是不同的表示。这样Fix 和unFix 就是一对同构函数，在类型f (Fix f) 和 Fix f 之间转换。为了清晰起见，区别类型上的函数Fix，我们后面用In 来代替Fix，用out 来代替unFix。

newtype Fix f = In { out :: f (Fix f) } -- Fix f 是函数f 的不动点

-- In 和 out 是一对同构函数

有了不动点函数Fix 的定义，我们就可以从非递归函数NListF 得到自然数类型NList 了。具体如下所示：

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

到此为止，我们得到了自然数的代数数据类型形式NListF。在代数数据类型的分析中，一般将定义的每个分支作为一个项，不同的分支的组合看成是项的加法。在NListF 的定义中，有两个项，分别是NNilF 和 NConsF () x，这两个项相加就是完整的NListF 的完整定义。另外，Haskell 中的所有类型可以看成是Hask 范畴，这是一个笛卡尔闭范畴（CCC 范畴）。于是，我们可以把NNilF用1 表示，NConsF 表示为乘法，类型() 是x 的一个常数系数，于是NListF 可以看成如下形式的代数数据类型。

Fx＝1＋() × x

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