1.5 自然数的同构

自然数不仅可以和自己的子集同构，例如奇偶数、平方数、斐波那契数，还可以和其他事物同构，包括计算机程序中的数据结构。下面是列表的定义：

用数据结构的观点来解释，一个类型为A的列表或者为空，记为nil；或者包含两部分：一个含有类型A数据的节点和一个包含剩余部分的子列表。函数cons把一个类型为A的元素和另一个类型为A的列表“链接”起来[11]。图1.9描述了一个含有6个节点的链表。

由于这种特点，列表也被称为“链表”。传统的计算机程序中，链表通常定义为一个结构[12]，例如：

我们也可以用自然数的同构来解释列表。根据皮亚诺公理1，nil相当于零；根据皮亚诺公理2，对于任何列表，我们都可以用cons，在其左侧链接一个类型为A的新元素。因此cons相当于自然数中的succ。这里的变化有两点。其一是列表携带类型A的元素，因而cons（1，cons（2，cons（3，nil）））、cons（2，cons（1，cons（3，nil）））、cons（1，cons（4，cons（9，nil）））以及cons（' a'，cons（' b'，cons（' c'，nil）））都是不同的列表。其二是与直觉不同，新元素不是加入列表的右侧末尾，而是加入左侧的头部。增长的方向是向左，而非向右。

用嵌套的cons表示较长的列表很不方便，我们将cons（1，cons（2，cons（3，nil）））简记为[1,2,3]，用符号“:”表示cons。因此这一列表也可以写为1:[2,3]或者1:（2:（3:nil））。针对A为字母的特殊情况，我们用带双引号的字符串来表示，例如用“hello”来简记表示为[' h'，' e'，' l'，' l'，' o']。

同构于自然数的加法，定义列表的连接运算如下：

列表的连接运算包含两条规则。首先空列表和任何列表连接的结果仍然等于该列表本身；并且某个列表的“后继”和另一个列表相连接，等于这两个列表连接结果的后继。和自然数的加法对比，它们呈现出有趣的镜像对称形式。

这种同构提示我们，可以利用递推公理证明列表连接的结合律。为了证明，我们首先证明x=nil时的起始情况：

然后再证明递推情况。假设，我们要证明。

这样我们就证明了列表连接操作的结合律。但是和自然数不同，列表不满足交换律[13]。例如，但交换后的结果却是[7,11,2,3,5]。

考虑和自然数同构，我们也可以定义列表的抽象叠加操作。为此，我们仿照自然数定义一个抽象的起始值c和一个抽象的二元运算h。这样就可以定义列表的递归形式：

进一步，令f=foldr(c,h)，就可以抽象出列表的叠加操作。我们将其命名为foldr，以表明这种叠加操作是自右向左进行的。

使用foldr，我们可以定义各种列表上的操作。例如我们可以把一个列表中的各个元素累加或累乘起来：

以sum为例，首先是空列表：sum(nil)=foldr(0,+,nil)=0；然后是若干个元素的列表：

sum([1,3,5,7])=foldr(0,+,1:[3,5,7])

=1+foldr(0,+,3:[5,7])

=1+(3+foldr(0,+,5:[7]))

=1+(3+(5+foldr(0,+,cons(7,nil))))

=1+(3+(5+(7+foldr(0,+,nil))))

=1+(3+(5+(7+0)))

=16

我们还可以计算列表的长度。这本质上是把一个列表映射成自然数。

这样我们就可以用|x|=length(x)来计算列表的长度。我们还可以用foldr定义连接操作：

这相当于自然数的（+m）运算。类似自然数乘法，我们可以定义列表“乘法”，将一个“列表的列表”全部连接起来。

例如：concat（[[1,1]，[2,3,5]，[8]]）的结果是[1,1,2,3,5,8]。我们接下来再用foldr定义两个重要操作：选择和逐一映射[13]。选择也称为过滤，是根据某个条件选择列表中的元素组成一个新的列表。为此，我们需要引入条件表达式的概念[14]。它通常写为，也就是给定变量x，若条件p(x)成立，则结果为f(x)，否则为g(x)，我们也会用if p(x)then f(x)else g(x)来描述条件表达式。

为了理解这一定义，我们来看一个例子：从一组自然数中，选择出偶数。

filter(even,[1,4,9,16,25])

和sum的例子类似，首先是一系列的展开过程，h(1,h(4,h(9,…)))直到列表的最右侧cons(25,nil)。根据foldr的定义，传入nil的结果为c，故而接下来，要计算h(25,nil)，而其中h为条件表达式。为此我们先将函数even·1st应用到一对值(25,nil)上。1st取得25，由于它是奇数，故而even条件不成立。因此接下来对这对值执行2nd，得到结果nil。此后计算进入上一层h(16,nil)。先用1st获得偶数16，此时even成立。这样就映射到cons(16,nil)，结果为[16]。然后计算又进入更上一层h(9,[16])，通过条件表达式映射到2nd，故而结果仍然为[16]。这时计算进入h(4,[16])，条件表达式映射到cons(4,[16])，其结果为[4,16]；最后计算达到顶层h(1,[4,16])，由条件表达式映射到2nd得到最终结果[4,16]。

逐一映射的概念是将列表中的每个元素通过f映射成另一个值，从而组成一个新的列表。即map(f,x₁,x₂,…,x_n}={f(x₁),f(x₂),…,f(x_n)}。它可以用foldr定义如下：

这种把函数映射到一对值中的第一个之上的操作称为first，即first(f,(x,y))=(f(x),y)，我们在此后讲解范畴的时候还会再仔细讨论它。使用first，逐一映射可以定义为map(f)=foldr(nil,cons·first(f))。

求列表的长度也可以利用逐一映射来实现。首先将列表的所有元素都映射为1，然后再将这些1加起来就等于列表的长度。

len=sum·map(one)

one(x)=1

练习1.3

1.表达式foldr（nil,cons）定义了什么？

2.读入一串数字（数字字符串），用foldr将其转换成十进制数。如果是16进制怎么处理？如果含有小数点怎么处理？

3.乔恩·本特利在《编程珠玑》中给出了一个求最大子序列和的问题。给定整数序列{x₁,x₂,…,x_n}，求哪段子序列i,j，使得和x_i+x_i+1+…+x_j最大。请用foldr解决这道题。

4.最长无重复字符子串问题。任给一个字符串，求出其中不包含重复字符的最长子串。例如“abcabcbb”的最长无重复字符子串为“abc”。请使用foldr求解。