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

-- | 这是自然数上的归纳函数

iter :: a -＞ (a -＞ a) -＞ N -＞ a

iter z step [] = z

iter z step (_:xs) = step $ iter z step xs

-- | 这是加法的定义，就是将两个列表连接起来

plus :: N -＞ N -＞ N

plus m n = m ++ n

-- | 这是乘法的定义， 使用了归纳法

mult :: N -＞ N -＞ N

mult m n = iter [] (plus m) n

-- | 这是幂运算的定义，使用了归纳法

pow :: N -＞ N -＞ N

pow m n = iter [()] (mult m) n

列表上的归纳函数的定义是对于列表n，对其进行归纳的初始值是z ，每一个归纳步调用函数step 。列表n 是由元素组成的，我们就以z 为参数递归调用几次step 函数。比如当列表n 的值是[(), (), ()] 时，这是由3 个元素组成的，于是我们就递归调用3 次step 函数，于是结果是step (step (step z)) 。

对于加法，直接用两个列表的连接运算来定义。即将两个列表m 和n 连接起来就实现了列表的加法。

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

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

• 用函数表示自然数（丘奇数）

在纯函数编程语言中（比如Haskell），函数也是一个值，因此我们也可以用函数来表示自然数。这种表述方式时阿隆佐.丘奇发明的，因此也叫丘奇数。

我们知道，函数是可以组合起来，即我们可以把函数f 和g 组合起来得到g . f ，这里运算符. 就是组合运算（按普遍的定义，是反序的）。那我们把相同的两个函数f 组合起来就得到了f . f，把三个函数f 组合起来就得到了f . f . f，以此类推，我们就可以得到n 个函数f 的组合f . f . f . f ...。我们可以用函数f 的组合来表示自然数，由几个函数f 组合的函数就表示自然数几，比如用f 表示S O ，用f . f 表示S (S O) ，用f . f . f 表示S (S (S O))。至于自然数O ，则用函数id 来表示。丘奇数和数的对应关系如下：

0 ： \f -＞ id

1 ： \f -＞ f

2 ： \f -＞ f . f

3 ： \f -＞ f . f . f

......

于是就有了如下使用Haskell来实现的自然数的函数表示的定义和基本运算。

-- | 用函数来表示自然数的数据类型，就是给定一个函数f得到多个函数f的组合函数。

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