描述
开 本: 16开纸 张: 胶版纸包 装: 平装-胶订是否套装: 否国际标准书号ISBN: 9787111653257
内容简介
本书介绍了各种广泛使用的算法，用纯函数式编程语言表达它们，使读者更清楚地理解它们的结构和操作。在第1章中，介绍了构成使用的格式变体的特殊符号。第2章介绍了函数式编程中许多更简单、更通用的模式。第3～7章介绍和解释数据结构、排序、组合结构、图表和子列表搜索。在整本书中，作者用Scheme编程语言的纯函数版本介绍了算法。本书配有练习题，适用于编程技术方面的本科和研究生课程。
目 录
出版者的话
译者序
前言
第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
译者序
前言
第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
前 言
算法的研究源于人类寻求问题答案的渴望。我们更喜欢找到问题的真相，而且是使用客观的方法得出的答案。这种偏好的原因是很实际的。如果能够了解世界的本真面目，我们的行动就更有可能取得令人满意的结果，因此我们不断探求真理。如果人们能够独立地验证问题的答案，那么就更容易为实现共同目标达成共识与合作，因此在探求真理时，我们使用他人可验证的方法。
有时我们会发现许多问题都有相似的结构，而且都是同一类问题的实例。在这种情况下，可能存在一种能够解决这类问题的共同方法。这种方法就是算法：一种有效的、逐步求解的计算方法。依照这种方法，人们可以获得一般的、形式化的问题的任何实例的答案。
在计算机出现之前，执行一个需要大量步骤或大量数据的算法，需要非凡的耐心、细心和执着。即便如此，所得的结果往往也是有缺陷的。例如，从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阅读了本书早期的手稿，并帮助我避免了许多错误。感谢大家的支持！
在这本书的各个草稿中纠正了几千个错误之后，我很不安地意识到，书中可能还存在许多错误。因此，我提前向读者表示感谢，感谢你们提醒我，让我可以在我的网站上更正这些错误。我会关注你发至[email protected]的电子邮件，并立即回复你。
有时我们会发现许多问题都有相似的结构，而且都是同一类问题的实例。在这种情况下，可能存在一种能够解决这类问题的共同方法。这种方法就是算法：一种有效的、逐步求解的计算方法。依照这种方法，人们可以获得一般的、形式化的问题的任何实例的答案。
在计算机出现之前，执行一个需要大量步骤或大量数据的算法，需要非凡的耐心、细心和执着。即便如此，所得的结果往往也是有缺陷的。例如，从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阅读了本书早期的手稿，并帮助我避免了许多错误。感谢大家的支持！
在这本书的各个草稿中纠正了几千个错误之后，我很不安地意识到，书中可能还存在许多错误。因此，我提前向读者表示感谢，感谢你们提醒我，让我可以在我的网站上更正这些错误。我会关注你发至[email protected]的电子邮件，并立即回复你。
评论
还没有评论。