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

我们在前面已经说过，丘奇数的前驱就是从由n 个函数f 组合成的函数中去除一个函数f ，变为由n-1 个函数f 组合成的函数。比如丘奇数的lambda 返回结果是f . f . f，这个丘奇数的前驱的lambda 返回的结果是f . f。最简单的实现就是找到函数f 的反函数f⁻¹，于是有f⁻¹ . f . f .f 等于f . f。但是我们没有办法在Haskell中找到任意一个函数的反函数，看来这个实现方式是行不通的。那既然我们做不到逆转世界，那停止世界是可以的，我们可以使用const x 函数来停止世界，将\x -＞ \f -＞ f x 用为\x -＞ \f -＞ x 即\x -＞ const x 来替换，就去除了一次函数f 的作用，相当于没有调用过函数f 。顺着这个思路，我们于是有了如下这个丘奇数前驱的实现。

-- 前驱函数，从n个函数f的组合得到n-1个函数f的组合

predChurch n = Church $ \f x -＞ runChurch n (\g h -＞ h (g f)) (const x) id

• 自然数的减法和整除的实现

有了自然数的前驱函数，我们就可以实现减法了。前面说过，自然数没有负数，所以我们需要可以比较两个自然数，当自然数m 小于自然数n 时，m - n 的结果是0 。

我们可以将自然数实现为Eq 和Ord 类型类的实例，就可以比较两个自然数了。Haskell的实现如下：

instance Eq N where

O == O = True

S _ == O = False

O == S _ = False

S n1 == S n2 = n1 == n2

instance Ord N where

O `compare` O = EQ

S _ `compare` O = GT

O `compare` S _ = LT

S n1 `compare` S n2 = n1 `compare` n2

listToN :: [()] -＞ N

listToN [] = O

listToN (_:xs) = S $ listToN xs

-- 因为有instance Eq ()，所以有下面的

-- instance Eq [()]

-- 因为有instance Ord ()，所以有下面的

-- instance Ord [()]

churchToN :: Church -＞ N

churchToN c = runChurch c S O

instance Eq Church where

c1 == c2 = churchToN c1 == churchToN c2

instance Ord Church where

c1 `compare` c2 = churchToN c1 `compare` churchToN c2

我们通过自然数的前驱来实现减法，皮亚诺形式的自然数减法实现如下所示：

minus :: N -＞ N -＞ N

minus m n

| m＞n = iter m predN n

| otherwise = O

列表形式的自然数减法实现如下所示：

minus :: [()] -＞ [()] -＞ [()]

minus m n

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