1.4 自然数的结构

有了加法和乘法，我们就可以定义更复杂的计算。第一个例子是累加：0+1+2+…

第二个例子是阶乘n!

这两个例子非常相似。智慧生命和智能机器的一大区别就是能否“跳出系统”，到更高的层次进行抽象。这是我们人类心智中最强大、神秘、复杂、难以捉摸的一部分[5]。

我们发现累加和阶乘都有一个针对自然数零的起始值，累加始自零，阶乘始自一。针对递归情况，它们都将某一操作应用到一个自然数和它的后继上。累加是n′+sum(n)，阶乘是n′·fact(n)。如果我们把起始值抽象为c，把递归中的操作抽象为h，就可以用一个统一的形式概括累加和阶乘。

这是一个在自然数上的递归结构。我们观察一下它在前几个自然数上的表现。

其中，hn(c)表示我们叠加在c上重复进行n次h操作。它是原始递归形式的一种[6]。更进一步，如果观察此前我们定义的函数foldn，就会发现它们之间的关系：

细心的读者会观察到，我们最初定义的foldn带有三个参数，为什么这里只有两个了呢？实际上我们可以写成f(n)=foldn(c,h,n)。当我们仅传递给三元函数foldn前两个参数，它实际上就成为接受一个自然数为参数的一元函数了。我们可以这样看待它：foldn(c,h)(n)。

我们称foldn为自然数上的叠加（fold）操作。令c为zero，h为succ，我们就得到了自然数。如同上面的表格，我们可以得到一个序列：

zero,succ(zero),succ(succ(zero)),…succn(zero),…

如果c不是zero，h不是succ，则foldn(c,h)就描述了和自然数同构[5]的某种事物。我们来看几个例子：

(+m)=foldn(m,succ)

这个例子描述了将自然数n增加m的操作，将它依次作用到自然数上可以产生和自然数同构的序列m,m+1,m+2,…,n+m,…

(·m)=foldn(0,(+m))

这个例子描述了将自然数n乘以m的操作，将它依次作用到自然数上可以产生和自然数同构的序列0,m,2m,3m,…,nm,…

m()=foldn(1,(·m))

这个例子描述了对自然数m取n次幂的操作，将它依次作用到自然数上可以产生和自然数同构的序列1，m,m2，m3,…,mn,…

那么，我们思考出的这个抽象工具foldn能否描述累加和阶乘呢？我们观察下面的这个表格：

这里的关键问题是h必须是个二元操作，它能够对n′和f(n)进行运算。为此，我们将c也定义为一个二元数(a,b)[6]。然后针对二元数(a,b)定义某种类似“succ”的操作。最终为了获取结果，我们还需要定义从二元数中抽取a和b的函数：

这样我们就可以定义累加和阶乘了。首先是累加的定义：

我们看看，从起始值（0,0）开始，怎样递推出累加的结果。

类似地，我们用foldn定义出阶乘。

在累加和阶乘的定义中，我们使用了符号“·”来连接两个函数2nd和foldn(c,h)。我们称之为函数组合，f·g表示先将函数g应用到变量上，然后再将函数f应用到结果上。即(f·g)(x)=f（g(x)）。

为了展示这一抽象工具的强大，我们再来看一个例子：斐波那契数列。这一数列是用中世纪数学家斐波那契（见图1.6）命名的。斐波那契来自拉丁文filius Bonacci，意思是波那契之子。斐波那契的父亲当时是商人，在北非以及地中海一带经商，斐波那契逐渐向当地阿拉伯人学习了印度-阿拉伯的数字系统并通过他的著作《算盘书》(Liber Abaci)将其介绍到欧洲。中世纪的欧洲一直使用罗马数字系统，我们今天在一些钟表盘上仍然可以看到罗马数字。例如2018年的罗马数字表示为MMXVIII，其中一个M代表1000，两个M代表2000，X代表10，V表示5，三个I表示3。把这些加起来得到2018。斐波那契引入欧洲的是我们今天仍然使用的位值制十进制系统。它使用了印度数学发明的零，不同的数字在不同的位置上含义不同。这一先进的数字系统极大地方便了计算，广泛应用在记账、利息、汇率等方面。《算盘书》更是对欧洲的数学复兴产生了深远的影响。

斐波那契数列来自《算盘书》中的一个问题（见图1.7）：兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？开始时有一对兔子。第一个月小兔尚未具备繁殖能力，所以仍然只有一对兔子。第二个月它们生下一对小兔，共有两对。第三个月大兔子又生下一对小兔，而上月生的小兔还在成长，总共有2+1=3对。第四个月有两对大兔子产下两对小兔，加上原有的三对兔子，总共有3+2=5对。按照这样，我们可以得到一个序列：

1,1,2,3,5,8,13,21,34,55,89,144,…

这个数列很有规律，从第三项后，任何一项都等于前两项的和。我们可以这样思考它的原理，如果前一个月有m对兔子，这个月有n对兔子，那么增加的一定都是新产下的小兔，共有n-m对，而剩下的都是成年兔子，共m对。到下个月时，这n-m对小兔刚刚成熟，而m对成兔又产下了m对小兔。所以下个月的兔子总数等于小兔加上成兔为(n-m)+m+m=n+m对。根据这一推理，我们可以给出斐波那契数列的递归定义：

通常将斐波那契数列的起始值定义为0和1[7]。注意到斐波那契数列的起始值是一对自然数，并且递推关系也是一对值。我们可以利用抽象工具foldn给出下面的定义[8]：

也许读者会好奇，真实的计算机程序能实现这样的定义么？这是不是太理想化了？下面是一段的Haskell语言的程序代码[9]，执行fib 10会输出斐波那契数55[10]。

练习1.2

1.使用foldn定义平方（　）2。

2.使用foldn定义（　）m，计算给定自然数的m次幂。

3.使用foldn定义奇数的和。它会产生怎样的序列？

4.地面上有一排洞（无限多个），一只狐狸藏在某个洞中。每天狐狸会移动到相邻的下一个洞里。如果每天只能检查一个洞，请给出一个捉到狐狸的策略，并证明这个策略有效（参见图1.8）。如果狐狸每天移动的不止一个洞呢[7]？