计算机科学丛书 函数程序设计算法
作者：(美)约翰 戴维 斯通(John David Stone） 著 乔海燕，曾烈康 译
出版时间：2020年版
内容简介
本书介绍了各种广泛使用的算法，用纯函数式编程语言表达它们，使读者更清楚地理解它们的结构和操作。在第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
