Haskell和自然数之基础篇（二） (3-1)

我们用一个新的数据类型Church来定义丘奇数，这实际上就是以函数f 为参数得到多个函数f 组合的函数的lambda函数的封装类型，其本质就是一个lambda函数，这个lambda函数的返回结果是多个函数f的组合。

当类型Church的lambda的函数参数是(+1) 时，如果这个丘奇数表示的是自然数S (S (S O))，那lambda函数返回的结果是(+1) . (+1) . (+1)，也是一个函数，将这个函数应用到参数0，我们得到了3。可以看到类型Church（丘奇数）本身的定义就是归纳的，因此其归纳函数iter 的实现就是将归纳步step 直接作为参数传递给类型Church的lambda函数，然后将结果函数应用到初始值z ，就得到了归纳函数iter 的结果。

因为丘奇数本身的定义就是归纳的，所以我们就不需要用归纳法来实现加法了，直接用Church本身的定义来实现加法就可以了。比如当丘奇数m 的值为Church (\f -＞ f . f . f)，丘奇数n 的值为Church (\f -＞ f . f) 时，m 加上n 的丘奇数的lambda函数返回的结果是(f . f . f . f . f)，也就是Church (\f -＞ (f . f) . (f . f . f))，因此加法就是由函数的组合运算来实现。

类似的，丘奇数的乘法也使用其本身的定义来实现。当丘奇数m 的值为Church (\f -＞ f . f . f)，丘奇数n 的值为Church (\f -＞ f . f) 时，m 乘以n 的丘奇数的lambda函数返回的结果是(\g -＞ g . g) (f . f . f)，得到Church ((\g -＞ g . g) . (\f -＞ f . f . f))，结果是Church (\f -＞ (f . f . f) . (f . f . f))，因此乘法就是由丘奇数的lambda函数的组合来实现的。

最后，丘奇数的幂运算也可以使用其本身的定义来实现。当丘奇数m 的值为Church (\f -＞ f . f . f)，丘奇数n 的值为Church (\f -＞ f . f) 时，m 的n 次幂的丘奇数的lambda函数返回的结果是(\g -＞ g . g) (\h -＞ h . h . h)，得到Church (\f -＞ ((\g -＞ g . g) (\h -＞ h . h . h)) f)，将g 替换为(\h -＞ h . h . h) 有Church (\f -＞ ((\h -＞ h . h . h) . (\h -＞ h . h . h)) f)，结果是Church (\f -＞ (f . f . f) . (f . f . f) . (f . f . f))，因此幂运算就是将一个丘奇数的lambda函数应用到另一丘奇数的lambda函数的方式来实现的。

丘奇数和前面两个自然数表示形式所不同的是丘奇数的前驱的实现比较难，不像皮亚诺形式的和列表形式的那么简单直观。

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