![同构:编程中的数学](https://wfqqreader-1252317822.image.myqcloud.com/cover/165/48213165/b_48213165.jpg)
1.5 自然数的同构
自然数不仅可以和自己的子集同构,例如奇偶数、平方数、斐波那契数,还可以和其他事物同构,包括计算机程序中的数据结构。下面是列表的定义:
用数据结构的观点来解释,一个类型为A的列表或者为空,记为nil;或者包含两部分:一个含有类型A数据的节点和一个包含剩余部分的子列表。函数cons把一个类型为A的元素和另一个类型为A的列表“链接”起来[11]。图1.9描述了一个含有6个节点的链表。
![](https://epubservercos.yuewen.com/7F4CCD/27732751902824706/epubprivate/OEBPS/Images/22_04.jpg?sign=1734456352-at8ra4EeuLOn1kM4g8Y8tAzczto2wFyO-0-c8f2d58e2186359cdb8add9bd0481809)
图1.9 链表
由于这种特点,列表也被称为“链表”。传统的计算机程序中,链表通常定义为一个结构[12],例如:
![](https://epubservercos.yuewen.com/7F4CCD/27732751902824706/epubprivate/OEBPS/Images/23_01.jpg?sign=1734456352-jU7LPF3prUvUVFzmNP9vGVSbz6E3GcR1-0-fe1bf31c81581f7dd3e2a974bc25f0f5)
我们也可以用自然数的同构来解释列表。根据皮亚诺公理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']。
同构于自然数的加法,定义列表的连接运算如下:
![](https://epubservercos.yuewen.com/7F4CCD/27732751902824706/epubprivate/OEBPS/Images/23_02.jpg?sign=1734456352-vrrjIjBJOVc3dY7hw9vpwAYIkykuxydI-0-2abd9314a4d0c9d818b44ed2f0d1c043)
列表的连接运算包含两条规则。首先空列表和任何列表连接的结果仍然等于该列表本身;并且某个列表的“后继”和另一个列表相连接,等于这两个列表连接结果的后继。和自然数的加法对比,它们呈现出有趣的镜像对称形式。
![](https://epubservercos.yuewen.com/7F4CCD/27732751902824706/epubprivate/OEBPS/Images/23_03.jpg?sign=1734456352-VPGGTmJ4bRybihmBXuhUiO0ddDfahU9U-0-cb644739f9e45c3a65931bc58c117896)
这种同构提示我们,可以利用递推公理证明列表连接的结合律。为了证明,我们首先证明x=nil时的起始情况:
![](https://epubservercos.yuewen.com/7F4CCD/27732751902824706/epubprivate/OEBPS/Images/23_06.jpg?sign=1734456352-j64QcCeGR9a12OkXlI9yQqKGPwJLXk9N-0-d551bafb0abb491bc7a1e7f8a02b39f0)
然后再证明递推情况。假设,我们要证明
。
![](https://epubservercos.yuewen.com/7F4CCD/27732751902824706/epubprivate/OEBPS/Images/23_10.jpg?sign=1734456352-h0ShrXp6fOQqT1Ademb6bdiG5kC2UPQe-0-87439609dcb35e8290c1c4245bffe2ea)
![](https://epubservercos.yuewen.com/7F4CCD/27732751902824706/epubprivate/OEBPS/Images/24_01.jpg?sign=1734456352-x55phfVsCdcKbuKubJ16IJVhOJE7k60t-0-ea0a410aff034a9bf23b1b9bfe2bb401)
这样我们就证明了列表连接操作的结合律。但是和自然数不同,列表不满足交换律[13]。例如,但交换后的结果却是
[7,11,2,3,5]。
考虑和自然数同构,我们也可以定义列表的抽象叠加操作。为此,我们仿照自然数定义一个抽象的起始值c和一个抽象的二元运算h。这样就可以定义列表的递归形式:
![](https://epubservercos.yuewen.com/7F4CCD/27732751902824706/epubprivate/OEBPS/Images/24_04.jpg?sign=1734456352-9I8ENOidGsds4jsZ47GBG3Z6i7DosN3h-0-ea3e2a2d3a5e9cbb98ca162bd31925db)
进一步,令f=foldr(c,h),就可以抽象出列表的叠加操作。我们将其命名为foldr,以表明这种叠加操作是自右向左进行的。
![](https://epubservercos.yuewen.com/7F4CCD/27732751902824706/epubprivate/OEBPS/Images/24_05.jpg?sign=1734456352-23qjIVUYqlfx2CJmiIHaMpBZR4Om1UL6-0-61132bcb4f9be0a0e74b55a08954fb9d)
使用foldr,我们可以定义各种列表上的操作。例如我们可以把一个列表中的各个元素累加或累乘起来:
![](https://epubservercos.yuewen.com/7F4CCD/27732751902824706/epubprivate/OEBPS/Images/24_06.jpg?sign=1734456352-HtN5rWKcvpI1dzb1hJVeVN9xp86FMz9R-0-ffacbc0d39a5d393630e865e04c26230)
以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
我们还可以计算列表的长度。这本质上是把一个列表映射成自然数。
![](https://epubservercos.yuewen.com/7F4CCD/27732751902824706/epubprivate/OEBPS/Images/24_07.jpg?sign=1734456352-F5LrL9rPEkPE5aXqFMk2d0sxPf1PS7pZ-0-0c32de84b8166c79467c8a5f4c901bc7)
这样我们就可以用|x|=length(x)来计算列表的长度。我们还可以用foldr定义连接操作:
![](https://epubservercos.yuewen.com/7F4CCD/27732751902824706/epubprivate/OEBPS/Images/25_01.jpg?sign=1734456352-AflVNZPX6P4TUVSVmG7f7jdJAG6Q7F3W-0-d13a5f52bfd64429965563428465a276)
这相当于自然数的(+m)运算。类似自然数乘法,我们可以定义列表“乘法”,将一个“列表的列表”全部连接起来。
![](https://epubservercos.yuewen.com/7F4CCD/27732751902824706/epubprivate/OEBPS/Images/25_02.jpg?sign=1734456352-Gg5mjwDckga00dvPG15US3GZ7PKfbfJ1-0-8cbf868a1352e85a6e6e987592f04262)
例如: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)来描述条件表达式。
![](https://epubservercos.yuewen.com/7F4CCD/27732751902824706/epubprivate/OEBPS/Images/25_04.jpg?sign=1734456352-w9wIKdsxMZbBYi4nrENNAHeaEdZxVCSC-0-47afd499c33b65d0ebe163fe8291b041)
为了理解这一定义,我们来看一个例子:从一组自然数中,选择出偶数。
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,x1,x2,…,xn}={f(x1),f(x2),…,f(xn)}。它可以用foldr定义如下:
![](https://epubservercos.yuewen.com/7F4CCD/27732751902824706/epubprivate/OEBPS/Images/25_05.jpg?sign=1734456352-tz1WgmXzVFmLtorztv7BM1CKSRhoPZST-0-ef7825e829972e69089091b23f1ff37d)
这种把函数映射到一对值中的第一个之上的操作称为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.乔恩·本特利在《编程珠玑》中给出了一个求最大子序列和的问题。给定整数序列{x1,x2,…,xn},求哪段子序列i,j,使得和xi+xi+1+…+xj最大。请用foldr解决这道题。
4.最长无重复字符子串问题。任给一个字符串,求出其中不包含重复字符的最长子串。例如“abcabcbb”的最长无重复字符子串为“abc”。请使用foldr求解。