数学联邦政治世界观
超小超大

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),接着再看更方便。

相关小说

我在冰上书写 连载中
我在冰上书写
Rhodamine
Япишунальду/Rhodamine-著——-陀氏・改编扩衍・十九世纪・一位女士的回忆手记录-第一人称・女主人公视角・穿插性描写-魔幻......
3.1万字9个月前
黄河与黄河队 连载中
黄河与黄河队
若慕小染
传承中华民族文化我国的母亲河——黄河值得被更多人了解认识想通过一个故事,让读者体会同名同姓的黄河。英勇一生,淳朴至善,永远适用于他。(本文已......
0.3万字9个月前
凤帝威武,夫君个个都妖娆 连载中
凤帝威武,夫君个个都妖娆
李朵儿
(已签约/已完结)作为凤凰一族下一任的王,17万岁就升为上神的凤惜居然被自己的父亲一脚给踢到了下等大陆?这真是该死的尴尬,一身灵力消失不见,......
57.7万字9个月前
小甜:你存在的意义 连载中
小甜:你存在的意义
.寄予星辰.
中考暂退小心超人:甜心,因为你的存在,让我的存在变得有了意义甜心超人:我喜欢上一个对我特殊的男生
1.9万字9个月前
快穿之手下留情啊殿下 连载中
快穿之手下留情啊殿下
来个西红柿吧
暂时停更——【第一篇:烈火红缨枪】✓【第二篇:一剑斩秋水】✓【第三篇:与兽共舞】❤️❤️❤️【已签约/原创作品/禁止抄袭、转载】快穿+系统+......
6.2万字9个月前
神明不会低语 连载中
神明不会低语
浔溺
【原创短篇】我暗恋的人,给我造了一个囚笼。
2.9万字9个月前