本书介绍了各种广泛使用的算法，用纯函数式编程语言表达它们，使读者更清楚地理解它们的结构和操作。在第1章中，介绍了构成使用的格式变体的特殊符号。第2章介绍了函数式编程中许多更简单、更通用的模式。第3～7章介绍和解释数据结构、排序、组合结构、图表和子列表搜索。在整本书中，作者用Scheme编程语言的纯函数版本介绍了算法。本书配有练习题，适用于编程技术方面的本科和研究生课程。
更方便地识别和抽象出函数之间交互的一般模式
算法的研究源于人类寻求问题答案的渴望。我们更喜欢找到问题的真相，而且是使用客观的方法得出的答案。这种偏好的原因是很实际的。如果能够了解世界的本真面目，我们的行动就更有可能取得令人满意的结果，因此我们不断探求真理。如果人们能够独立地验证问题的答案，那么就更容易为实现共同目标达成共识与合作，因此在探求真理时，我们使用他人可验证的方法。
有时我们会发现许多问题都有相似的结构，而且都是同一类问题的实例。在这种情况下，可能存在一种能够解决这类问题的共同方法。这种方法就是算法：一种有效的、逐步求解的计算方法。依照这种方法，人们可以获得一般的、形式化的问题的任何实例的答案。
在计算机出现之前，执行一个需要大量步骤或大量数据的算法，需要非凡的耐心、细心和执着。即便如此，所得的结果往往也是有缺陷的。例如，从1853年到1873年，一位名叫威廉·尚克斯（William Shanks）的计算狂热爱好者把他大部分的业余时间都用在计算π的高精度值上，并且计算到小数点后707位。直到1944年，人们才发现尚克斯犯了一个错误，影响了第528位和所有随后的数字，在这之前，尚克斯一直保持着这个计算的记录。在没有机械辅助的情况下，人类有史以来进行的最大规模的计算可能是1880年的美国人口普查，它花了七八年的时间才完成，几乎可以肯定的是，其中充满了错误的结果。
电子存储程序计算机的发明和发展在很大程度上消除了这种对计算复杂性的限制。我们现在可以在几分之一秒内算出π的707位值，而完成1880年的美国人口普查计算或许只需要耗时一分钟。如今的大规模计算可能是诸如计算π的5000亿位数这样的任务，我们希望计算的结果是完全正确的。如今的大规模数据集可能是以太字节（terabyte）为单位计量的。
直到20世纪中叶，算法的发明和应用的另一个障碍是缺少用于记录算法的清晰易懂的通用符号。用日常语言描述算法时，人们常常难以确切地表述实现的方法。这样的描述往往会遗漏细节，无法解释对特殊情况的处理，或者需要实现者猜测某些关键的过程。例如，如果你学过长除法（其中除数包含多位数字）的手动演算，你可能还记得计算时必须估计商的下一位数字，如果估计错误，则必须返回修正。
高级编程语言的发明和发展也在很大程度上消除了这一障碍。对于算法的发明者来说，以计算机程序的形式准确、完整、明确地表达算法现在已经司空见惯。
然而，人类读者在第一次看到算法时，可能无法从执行算法的计算机程序源代码中判断出算法的底层结构。对于人类读者来说，其中一个阅读难点是许多高级编程语言都基于同一种计算模型，在这种计算模型中，程序通过反复改变适当初始化的存储设备的状态来实现计算。理解这些变化的相互作用和累积效应往往是很困难的。
解决这一难点的办法是使用不同的计算模型。在纯函数程序设计语言中，人们认为计算是数学函数应用于参数值，并给出结果值。如果一个计算又长又复杂，那么可以用其他简单的函数来定义这个数学函数，而这些简单的函数又可以用其他更简单的函数来定义。但是，在每个级别上，这些函数都是无状态的，在给定相同的参数时，它们会返回相同的结果。一旦我们理解了函数能够根据输入参数返回计算结果的规则，就可以将函数视为具有固定和可预测行为的可靠组件。这种模块化的思想使得大型程序的设计和构建更简单，也使得人们能更容易地理解大型程序。
此外，函数程序设计语言使函数间交互的一般模式的识别和抽象变得更容易，因此人们可以在语言本身内描述和操作这些模式。函数本身可以作为参数传递给其他函数，也可以作为函数的结果值返回。使用高阶函数可以更容易地表述和理解常用的算法。
本书旨在向读者展示一系列广泛使用的算法，并用纯函数程序设计语言进行表达，从而帮助读者更好地阅读和理解它们的结构和操作。函数程序设计的其他优点也将在这一过程中展现出来。
我们用Scheme程序设计语言的一个纯函数版本来描述算法，附录B中描述了（afp primitives）库的实现。本书代码已经在《算法语言Scheme第7版修订报告》的Chibi-Scheme、
Larceny和Racket实现下做了详细测试，并可在作者的网站上下载，网址为http://unity.homelinux.net/afp/。
本书代码在GNU通用公共许可证（第3版或更高版本）下供读者自由使用（http://www.gnu.org/copyleft/gpl.html）。
致谢
感谢格林内尔学院给我写这本书提供了时间和资源；感谢我的同事Henry Walker、Samuel Rebelsky、Ben Gum、Janet Davis、Jerod Weinman、Peter-Michael Osera和Charlie Curtsinger的耐心和支持；感谢Karen McRitchie和Jeff Leep给予我的帮助；感谢莱斯大学给我提供了工作环境；感谢Springer-Verlag的编辑Wayne Wheeler和Ronan Nugent；感谢Matthias Felleisen和Shriram Krishnamurthi阅读了本书早期的手稿，并帮助我避免了许多错误。感谢大家的支持！
在这本书的各个草稿中纠正了几千个错误之后，我很不安地意识到，书中可能还存在许多错误。因此，我提前向读者表示感谢，感谢你们提醒我，让我可以在我的网站上更正这些错误。我会关注你发至reseda@grinnell.edu的电子邮件，并立即回复你。
计算机\算法
本书用纯函数程序设计语言Scheme的一种变体深入浅出地讲解各类常用的数据结构和算法。第1章介绍了本书使用的基于Scheme的变体语言，第2章和第3章分别介绍了函数程序设计中常用的各类编程模式和数据结构，第4～7章分别介绍了排序、组合构造、图算法和子列表搜索算法等，并对算法的思想和实现进行了详细分析和解释。全书每节都总结了本节涉及的过程并编排了有针对性的习题，以便读者更好地理解和掌握相关内容。
本书适用于学习函数程序设计和算法设计及相关课程的本科生和研究生，也可供程序员学习函数程序设计时阅读和参考。
作者简介
约翰·戴维·斯通（John David Stone） 是格林内尔学院计算机科学系的高级讲师，教授算法、计算机安全和计算语言。他的研究兴趣包括逻辑和编程基础。
译者简介
乔海燕 中山大学数据科学与计算机学院副教授，研究方向为类型论及其在程序验证中的应用。
曾烈康 中山大学数据科学与计算机学院研究生，研究方向为边缘计算、边缘智能、智能物联网、分布式系统。
数据结构与算法的设计是计算机程序设计的核心。由于多方面的原因，目前主流的程序设计范式仍然是命令式的，因此，数据结构和算法的描述与实现都是命令式的。但是，一般命令式程序的执行有副作用，一个命令式程序动辄由成千上万行代码组成，种种原因使得基于命令式程序的软件可读性和可维护性都难以令人满意，无法保证软件的可靠性、安全性和正确性。随着人们对于软件安全性和正确性的日益重视，一种改善思路是采用函数程序设计语言设计程序。函数程序设计语言从更高的数学抽象层面描述程序的计算逻辑，基于函数程序设计语言，构成程序的数据结构和算法逻辑能够更清晰地呈献给读者，程序的理解更容易，程序的正确性推理成为可能。因此，现在越来越多的程序员转向函数程序设计语言，即使是使用命令式语言编写程序，也会借鉴函数程序设计的思想。越来越多的语言开始支持函数程序设计。
本书是少有的仅使用函数程序设计语言描述和实现算法的教材。全书使用函数程序设计语言Scheme的一种变体，详尽地描述并实现了各类常用的数据结构和算法。本书第1章介绍了全书使用的基于Scheme的变体语言，包括该语言的函数、过程、过程调用、λ表达式、谓词和定义等。第2章介绍了函数程序设计中常用的各类编程模式，包括映射（map）、过程节选、过程的各种高阶组合模式。第3章介绍了数据结构的建模思想和常用的数据结构，包括和类型、积类型、列表、多元组、源、树、包、集合、表和缓冲区等。接下来的各章（第4～7章）依次介绍了排序算法（包括插入排序、快速排序和归并排序等）、平衡查找树（包括二叉搜索树和红黑树）、各种组合构造（包括各种子列表的选择、排位和去排位、排列和划分等）、图论经典算法（包括深度优先遍历和广度优先遍历、最小生成树、最短路径和网络流算法等）以及子列表搜索经典算法（包括KMP算法、Boyer-Moore算法和Rabin-Karp算法）。
本书作者约翰·戴维·斯通在格林内尔学院长期教授算法、计算机安全、人工智能和计算语言学，具有非常丰富的教学经验。全书结构逻辑性强，对算法的思想和实现的解释清晰详细，每节都总结了本节讲解的过程并编排了有针对性的习题，便于读者进一步理解和掌握相关内容。本书对于想进一步学习函数程序设计的本科生和研究生以及其他对函数程序设计感兴趣的程序员而言都是一本很好的教材。
本书在翻译过程中得到了刘锋编辑的大力支持，我们在此表示感谢！
限于译者水平，译文中难免出现疏漏和错误，欢迎大家批评指正！
译 者
2019年11月于中山大学东校区
出版者的话
译者序
前言
第1章 基本符号 1
1.1 简单值 1
1.2 标识符和表达式 3
1.3 函数和过程 4
1.4 算术函数 5
1.4.1 加法 5
1.4.2 减法 5
1.4.3 乘法 6
1.4.4 除法 6
1.4.5 幂运算 7
1.4.6 过程总结 7
1.5 过程调用 9
1.6 λ表达式 10
1.6.1 变元过程 11
1.6.2 构建列表 13
1.6.3 返回多个值 13
1.6.4 没有结果的计算 14
1.7 谓词 15
1.7.1 分类谓词 16
1.7.2 相等谓词 16
1.7.3 相等和类型 16
1.8 条件类型表达式 19
1.8.1 条件表达式 19
1.8.2 合取表达式与析取表达式 19
1.9 定义 21
1.9.1 过程定义 21
1.9.2 递归定义 22
1.10 局部绑定 23
1.10.1 局部过程 24
1.10.2 局部递归 24
1.10.3 收纳表达式 25
第2章 工具箱 27
2.1 列表映射 27
2.2 常量过程 28
2.3 过程节选 29
2.3.1 invoke过程 30
2.3.2 卡瑞化 31
2.4 耦合器 32
2.4.1 过程复合 32
2.4.2 并行应用 33
2.4.3 调度 34
2.5 适配器 35
2.5.1 选择 35
2.5.2 重排 36
2.5.3 预处理和后处理 36
2.6 递归管理器 38
2.6.1 recur过程 39
2.6.2 递归谓词 40
2.6.3 迭代 41
2.7 欧几里得算法 44
2.8 高阶布尔过程 47
2.8.1 布尔值和谓词上的操作 47
2.8.2 ^if过程 47
2.9 自然数和递归 49
2.9.1 数学归纳法 49
2.9.2 自然数上的递归 49
2.9.3 计数 53
2.9.4 有界推广 54
第3章 数据结构 56
3.1 建模 56
3.2 空值 57
3.3 和类型 57
3.3.1 枚举 57
3.3.2 可区分并集 58
3.3.3 递归类型方程 59
3.4 有序对 60
3.4.1 命名对 61
3.4.2 积类型 61
3.4.3 再议可区分并集 62
3.4.4 重新实现自然数 62
3.5 盒 64
3.6 列表 66
3.6.1 选择过程 67
3.6.2 同构列表 68
3.6.3 列表的递归过程 69
3.6.4 列表归纳原理 70
3.6.5 列表递归管理 71
3.6.6 展开 73
3.7 列表算法 77
3.7.1 元数扩展 77
3.7.2 筛选和划分 79
3.7.3 子列表 80
3.7.4 位置选择 81
3.7.5 列表元素上的谓词扩展到列表 82
3.7.6 转置、压缩和解压缩 83
3.7.7 聚合多个结果 84
3.8 源 89
3.9 多元组 98
3.9.1 建立模型 99
3.9.2 记录类型 99
3.10 树 101
3.10.1 树归纳原理 103
3.10.2 树递归管理 103
3.11 灌木 109
3.11.1 灌木归纳原理 110
3.11.2 灌木递归管理 110
3.12 包 113
3.12.1 基本包过程 114
3.12.2 包操作 115
3.12.3 包递归管理 116
3.13 等价关系 120
3.14 集合 123
3.14.1 集合递归管理 124
3.14.2 筛选和划分 125
3.14.3 其他集合运算 126
3.14.4 并集、交集和差集 127
3.15 表 132
3.16 缓冲区 138
第4章 排序 142
4.1 序关系 142
4.1.1 隐式定义的等价关系 142
4.1.2 测试一个列表是否有序 143
4.1.3 查找极值 143
4.1.4 复合序关系 145
4.1.5 字典序 145
4.2 排序算法 148
4.2.1 插入排序 149
4.2.2 选择排序 149
4.2.3 快速排序 150
4.2.4 归并排序 150
4.3 二叉搜索树 153
4.3.1 测试二叉搜索树不变量 154
4.3.2 从二叉搜索树中提取一个值 155
4.3.3 二叉搜索树排序 156
4.4 红黑树 158
4.4.1 实现红黑树 159
4.4.2 颜色翻转和旋转 160
4.4.3 插入 161
4.4.4 查找 163
4.4.5 删除 163
4.4.6 用红黑树实现表 168
4.5 堆 175
4.5.1 折叠和展开堆 178
4.5.2 堆排序 178
4.6 序统计量 181
第5章 组合构造 183
5.1 笛卡儿积 183
5.1.1 笛卡儿积排序 185
5.1.2 排位和去排位 186
5.2 列表选择 189
5.2.1 子列表 189
5.2.2 分组 193
5.2.3 子序列和选择 194
5.3 包选择 199
5.4 排列 201
5.5 划分 204
5.5.1 包划分 204
5.5.2 划分自然数 206
第6章 图 208
6.1 图的实现 208
6.1.1 图的构造 209
6.1.2 图与关系 211
6.1.3 图的性质 212
6.1.4 其他图访问方法 213
6.1.5 无向图 215
6.2 深度优先遍历 221
6.2.1 图的遍历 221
6.2.2 深度优先 222
6.2.3 拓扑排序 223
6.2.4 可到达结点 223
6.3 路径 225
6.4 广度优先遍历 227
6.5 生成树 229
6.6 最短路径 233
6.6.1 Bellman-Ford算法 233
6.6.2 Dijkstra算法 234
6.6.3 Floyd-Warshall算法 235
6.7 流网络 239
第7章 子列表搜索 244
7.1 简单低效的算法 244
7.2 Knuth-Morris-Pratt算法 246
7.3 Boyer-Moore算法 253
7.4 Rabin-Karp算法 255
附录A 推荐读物 260
附录B (afp primitives)库 261
附录C 如何使用AFP库 263
