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

在上一篇文章 parker liu：Haskell和自然数之基础篇中，我们定义了什么是自然数，给出了自然数的几种定义形式。在这篇文章中，我们继续来探讨自然数，看看自然数的代数结构，自然数和递归、幺半群、F-代数、自由幺半群的关系。

我们再来看一下自然数的定义：

data N = O

| S N -- 使用了递归定义

deriving (Show)

我们可以看到，在这个定义里使用了递归的方式来定义自然数，其中S N是递归步，O是递归的终止。自然数具有一个递归形式，递归层数就是该自然数的大小。于是我们就有了自然数类型N 的形式定义。

我们可以写这么一个函数来将上面定义的自然数N 转换为我们常见的正整数。

nToInt :: N -＞ Int

nToInt O = 0

nToInt (S n) = 1 + nToInt n

--- 在ghci中的运行结果如下

＞ nToInt (S (S (S O))

3

也可以写这么一个函数，将上面定义的自然数N 转换为字母a 组成的字符串。

nToCharAs :: N -＞ [Char]

nToCharAs O = []

nToCharAs (S n) = 'A' : nToCharAs n

--- 在ghci中的运行结果如下

＞ nToCharAs (S (S (S O))

"AAA"

可以看到这两个函数的实现非常的相似，有着同样的结构。如果我们对自然数的定义稍作修改，将自然数N 的构造子S 变换为Cons ()，上面的函数的实现就有着更直观的对应。我们来看修改后的自然数定义：

data NList = NNil

| NCons () NList -- 使用了递归定义

deriving (Show)

我们可以看到，NList 实际上就是类型为()的列表。我们用这个新的自然数定义重新实现上面两个转换函数，于是有：

nlToInt :: NList -＞ Int

nlToInt NNil = 0

--^ NNil

nlToInt (NCons () nl) = 1 + (nlToInt nl)

--^ () NCons NList

--- 在ghci中的运行结果如下

＞ nlToInt (NCons () (NCons () (NCons () NNil))

3

nlToCharAs :: NList -＞ [Char]

nlToCharAs NNil = []

--^ NNil

nlToCharAs (NCons () nl) = 'A' : (nlToCharAs nl)

--^ () NCons NList

--- 在ghci中的运行结果如下

＞ nlToCharAs (NCons () (NCons () (NCons () NNil))

"AAA"

在上面的两个新的转换函数中，NNil 和NCons、() ，以及递归的NList有了直接的一一对应。

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