函數(shù)程序設(shè)計算法

出版者的話
譯者序
前言
第1章　基本符號 1
1.1　簡單值 1
1.2　標識符和表達式 3
1.3　函數(shù)和過程 4
1.4　算術(shù)函數(shù) 5
1.4.1　加法 5
1.4.2　減法 5
1.4.3　乘法 6
1.4.4　除法 6
1.4.5　冪運算 7
1.4.6　過程總結(jié) 7
1.5　過程調(diào)用 9
1.6　λ表達式 10
1.6.1　變元過程 11
1.6.2　構(gòu)建列表 13
1.6.3　返回多個值 13
1.6.4　沒有結(jié)果的計算 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　過程節(jié)選 29
2.3.1　invoke過程 30
2.3.2　卡瑞化 31
2.4　耦合器 32
2.4.1　過程復(fù)合 32
2.4.2　并行應(yīng)用 33
2.4.3　調(diào)度 34
2.5　適配器 35
2.5.1　選擇 35
2.5.2　重排 36
2.5.3　預(yù)處理和后處理 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　自然數(shù)和遞歸 49
2.9.1　數(shù)學(xué)歸納法 49
2.9.2　自然數(shù)上的遞歸 49
2.9.3　計數(shù) 53
2.9.4　有界推廣 54
第3章　數(shù)據(jù)結(jié)構(gòu) 56
3.1　建模 56
3.2　空值 57
3.3　和類型 57
3.3.1　枚舉 57
3.3.2　可區(qū)分并集 58
3.3.3　遞歸類型方程 59
3.4　有序?qū)?60
3.4.1　命名對 61
3.4.2　積類型 61
3.4.3　再議可區(qū)分并集 62
3.4.4　重新實現(xiàn)自然數(shù) 62
3.5　盒 64
3.6　列表 66
3.6.1　選擇過程 67
3.6.2　同構(gòu)列表 68
3.6.3　列表的遞歸過程 69
3.6.4　列表歸納原理 70
3.6.5　列表遞歸管理 71
3.6.6　展開 73
3.7　列表算法 77
3.7.1　元數(shù)擴展 77
3.7.2　篩選和劃分 79
3.7.3　子列表 80
3.7.4　位置選擇 81
3.7.5　列表元素上的謂詞擴展到列表 82
3.7.6　轉(zhuǎn)置、壓縮和解壓縮 83
3.7.7　聚合多個結(jié)果 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　等價關(guān)系 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　緩沖區(qū) 138
第4章　排序 142
4.1　序關(guān)系 142
4.1.1　隱式定義的等價關(guān)系 142
4.1.2　測試一個列表是否有序 143
4.1.3　查找極值 143
4.1.4　復(fù)合序關(guān)系 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　實現(xiàn)紅黑樹 159
4.4.2　顏色翻轉(zhuǎn)和旋轉(zhuǎn) 160
4.4.3　插入 161
4.4.4　查找 163
4.4.5　刪除 163
4.4.6　用紅黑樹實現(xiàn)表 168
4.5　堆 175
4.5.1　折疊和展開堆 178
4.5.2　堆排序 178
4.6　序統(tǒng)計量 181
第5章　組合構(gòu)造 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　劃分自然數(shù) 206
第6章　圖 208
6.1 圖的實現(xiàn) 208
6.1.1 圖的構(gòu)造 209
6.1.2 圖與關(guān)系 211
6.1.3 圖的性質(zhì) 212
6.1.4 其他圖訪問方法 213
6.1.5 無向圖 215
6.2 深度優(yōu)先遍歷 221
6.2.1 圖的遍歷 221
6.2.2 深度優(yōu)先 222
6.2.3 拓撲排序 223
6.2.4 可到達結(jié)點 223
6.3 路徑 225
6.4 廣度優(yōu)先遍歷 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 流網(wǎng)絡(luò) 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