Haskell和自然数之基础篇

分享 未结
1 1 0 56
小编 14天前发布
收藏 点赞
来源: https://zhuanlan.zhihu.com/p/298996358

对自然数的理解,是随着自己的成长而不断深入的。在小学的时候觉得很自然就理解了,很自然就用起来了,加、减、乘和整除很自然就学会了,感觉没有什么障碍。到了初中的某一天,突然想到一个问题:1 + 1为什么就是等于2呢?没有理由的就指定了是2,没有推导和证明的过程,感觉很不自然。于是自己思考了好几个月,觉得似乎想通了,写了一篇文章,然后被一些同学嘲笑了。现在也想不起来当时写的是什么了,那篇文章也不知道遗失到哪里去了,不过应该还是没有写清楚究竟为什么1 + 1等于2,要不然我是不会忘记写的是什么的。于是这个令人疑惑的问题一直困扰着我,一直到参加工作,也依然时不时会惦记着这个问题。

直到我学习了Haskell,看到一篇关于自然数的表示文章,用Haskell清晰的定义了自然数,定义了自然数的加法和乘法。我终于明白了1 + 1为什么就是等于2,这个从自然数的定义和加法的定义很自然就可以推导得到了,证明起来很容易。在这之后,又看了皮亚诺公理的自然数定义,对自然数的定义更加清楚了。在这之前,我听说过皮亚诺公理,但是并不感兴趣,还感受不到自然数公理化的意义,所以并没有去看。

大概两个月前,我收到了刘新宇的新书《同构--编程中的数学》,看到了这本书中对自然数的论述,然后又重温了丘奇数的概念。觉得可以写点关于自然数的东西了。这是一个系列,有两篇文章:第一篇讲自然数和丘奇数的基础概念和构造,以及在其上的基本运算,第二篇讲自然数的变换,结合F-Alg来讲如何消除自然数的结构得到其他的类型的值。

好了,让我们从一无所知的状态来开始了解什么是自然数吧。我们最早了解自然数是从数数开始的,当我们不知道桌上一堆东西有多少个时,最简单的办法就是数一数有多少个。数一下手指头是1 个,数两下手指头是2 个,数三下手指头是3 个,这样一直数下去,直到数完了这堆东西。于是我们就得到了一系列的数:1, 2, 3, ...,这些数和数手指头的次数的对应关系如下。

1 : 数一下手指头
2 : 数两下手指头
3 : 数三下手指头
......

当桌上没有东西的时候,我们就不用数手指头了,因为什么都没有,所以什么也不用做。这个时候我们用0 个来表示桌上东西的数量。于是有下面这个新的数和数手指头的次数的对应关系。

0 : 什么也不做
1 : 数一下手指头
2 : 数两下手指头
3 : 数三下手指头
......

因为我们一无所知,就像幼儿园的小朋友一样,还弄不明白两下、三下是怎么来的,是什么意思。我们再来看一遍我们数数的过程,一开始是什么也不做,然后将一个东西摆到桌子的另一边,做一次数手指头的动作,再将一个东西摆到桌子的另一边,再做一次数手指头的动作,这样每将一个东西摆到桌子的另一边,我们都接着做一次数手指头的动作,直到把桌子上的东西数完。于是我们就得到一个数手指头的动作的序列,这个数手指头动作的序列的次数就是东西的个数。因此有下面的数和数手指头的动作序列的对应关系。

0 : 什么也不做
1 : 数手指头 什么也不做
2 : 数手指头 (数手指头 什么也不做)
3 : 数手指头 (数手指头 (数手指头 什么也不做))
......

我们把上面的什么也不做用O 来表示,把数手指头这个动作用S 来表示,于是上面的数和数手指头的动作序列的对应关系就变成了下面这样。

0 : O
1 : S O
2 : S (S O)
3 : S (S (S O))
......

我们可以这样认为,最开始存在一个自然数O,然后我们开始做一个数手指头的动作,就得到一个新的自然数S O,再做一个数手指头的动作,又得到一个新的自然数S (S O)。再继续下去,我们就得到了自然数的序列:O, S O, S (S O), S (S (S O), ...。我们用N 来表示所有自然数的集合,也就是自然数类型,这样每做一次数手指头的动作,我们就得到了一个自然数n ∈ N 的后继S n,这也是一个自然数。我们可以使用Haskell来定义自然数:

data N = O
       | S N

于是我们就得到了所有的自然数。我们可以通过皮亚诺公理来验证这一点,皮亚诺公理的表述如下:

1. 0 是自然数。

2. 每个自然数都有它的下一个自然数,称为它的后继。

3. 0 不是任何自然数的后继。

4. 不同的自然数有不同的后继数。

5. 如果自然数的某个子集包含 0,并且其中每个元素都有后继元素。那么这个子集就是全体自然数。

这里得到自然数的后继用动作S 来表示,也可把S 看成是自然数集合上的自函数。皮亚诺公理确保了0(也就是我们前面用O来表示的数)是第一个自然数,然后通过不停的获取自然数的后继,我们就得到了所有的自然数。其中皮亚诺公理的第4条确保了S 是一个单射,第5条确保了S 是一个满射,因此S 是一个自同构(这一点在下一篇中会用到)。

另外第5条公理还有如下的等价描述:

任意关于自然数的命题,如果证明了它对自然数 0 是对的,又假定它对自然数 n 为真时,可以证明它对 n的后继n′ 也真,那么命题对所有自然数都真。

这保证了数学归纳法的正确性,使得自然数上可以有归纳函数iter 。因此也叫归纳公理。

我们有了严格定义的自然数,现在可以在这个定义的基础上定义加法、乘法和幂运算了。我们使用Haskell来定义这些运算:

-- | 先定义几个基本函数,用于给后面的运算定义使用
zero = O
succN = S
predN O = error "zero hasn't predecessor"
predN (S n) = n

-- | 这是自然数上的归纳函数
iter :: a -> (a -> a) -> N -> a
iter z step O     = z
iter z step (S n) = step $ iter z step n

-- | 这是加法的定义,使用了归纳法 
plus :: N -> N -> N
plus m n = iter m succN n

-- | 这是乘法的定义,使用了归纳法 
mult :: N -> N -> N
mult m n = iter O (plus m) n

-- | 这是幂运算的定义,使用了归纳法 
pow :: N -> N -> N
pow m n = iter 1 (mult m) n

(未完待续)

用列表表示自然数。

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

用函数表示自然数(丘奇数)。

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

参考链接:

  1. 《同构--编程中的数学》



回帖
  • 消灭零回复