Haskell和自然数之基础篇（一） (5-3)

自然数上的归纳函数的定义是对于自然数n ，对其进行归纳的初始值是z ，每一个归纳步调用函数step 。自然数n 是由几个S 构造的，我们就以z 为参数递归调用几次step 函数。比如当自然数n 的值是S (S (S O)时，这是由3 个S 构造的，于是我们就递归调用3 次step 函数，于是结果是step (step (step z)) 。

对于加法，我们是这样定义的，给定一个自然数m，加上一个值为S (S O)的自然数n 时，其结果等于值为S (S m)的自然数。用归纳函数来定义就相当于初始值z 是m ，step 是S 也就是succN ，我们对加数n 做归纳法，也就是自然数n 中由几个S 构造的，我们就递归调用几步S 。于是有了结果的值是S (S m)。

当m 的值是S O 也就是1 ，n 的值也是S O 即1 时，我们有(S O) + (S O) = S (S O)，根据上面的数的对应关系，我们有1 + 1 = 2 。完成了证明，解决了我多年来的疑问。

对于乘法，两个自然数m 和n 相乘，就相当于把n 个m 加起来。用归纳函数来定义就相当于初始值是O，step 是(m +) 也就是plus m ，我们对乘数n 做归纳法。于是乘以一个值为S (S O)的自然数，我们就递归调用两步递归步plus m，于是得到结果值是plus m (plus m O)，就是m + m。

对于幂运算，则和乘法类似，自然数m 的n 次幂的值就等于把n 个m 乘起来。用归纳函数来定义就相当于初始值是S O，step 是(m *) 也就是mult m ，我们对幂数n 做归纳法。于是求m 的一个值为S (S O) 的n 次幂的自然数的值，我们就递归调用两步递归步plus m，于是得到结果值是mult m (mult m (S O))，就是m * m。

减法的定义比较复杂，因为自然数没有负数，因此需要比较两个数的大小来实现减法，这个放到后面一起来定义。

用皮亚诺公理来定义的自然数只是自然数表示的一种形式，我们可以用其他同构的形式来定义和表示自然数。接下来我们将使用列表和函数来表示自然数。

• 用列表表示自然数

列表是包含了同类型元素的一种数据类型，多个同类型的数据列在一起，就组成了列表。当列表内的元素的类型是 () 时，列表就只剩下长度信息了，我们可以用其来表示自然数。

Haskell中列表的定义如下：

data [a] = []

| a : [a]

列表的类型是[a]，当列表内的元素的类型也就是a 为() 时，我们有一个特殊的列表类型[()]。这个列表类型的元素是无具体信息的，其有用的信息就是列表的长度，因此我们可以使用列表类型[()]来表示自然数。比如用[(), (), ()] 来表示皮亚诺形式的自然数S (S (S O))。列表表示的自然数和数的关系如下：

0 ： []

1 ： [()]

2 ： [(), ()]

3 ： [(), (), ()]

......

我们使用Haskell来定义如下的用列表类型[()] 表示的自然数运算。

-- | 先定义几个基本函数，用于给后面的运算定义使用

-- 0函数

zero = []

-- 后继函数

succList = (():)

-- 前驱函数

predList [] = error "zero hasn't predecessor"

predList (_:xs) = xs

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