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

出版者的話
譯者序
前言
第1章　基本符號(hào) 1
1.1　簡(jiǎn)單值 1
1.2　標(biāo)識(shí)符和表達(dá)式 3
1.3　函數(shù)和過(guò)程 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　冪運(yùn)算 7
1.4.6　過(guò)程總結(jié) 7
1.5　過(guò)程調(diào)用 9
1.6　λ表達(dá)式 10
1.6.1　變?cè)^(guò)程 11
1.6.2　構(gòu)建列表 13
1.6.3　返回多個(gè)值 13
1.6.4　沒有結(jié)果的計(jì)算 14
1.7　謂詞 15
1.7.1　分類謂詞 16
1.7.2　相等謂詞 16
1.7.3　相等和類型 16
1.8　條件類型表達(dá)式 19
1.8.1　條件表達(dá)式 19
1.8.2　合取表達(dá)式與析取表達(dá)式 19
1.9　定義 21
1.9.1　過(guò)程定義 21
1.9.2　遞歸定義 22
1.10　局部綁定 23
1.10.1　局部過(guò)程 24
1.10.2　局部遞歸 24
1.10.3　收納表達(dá)式 25
第2章　工具箱 27
2.1　列表映射 27
2.2　常量過(guò)程 28
2.3　過(guò)程節(jié)選 29
2.3.1　invoke過(guò)程 30
2.3.2　卡瑞化 31
2.4　耦合器 32
2.4.1　過(guò)程復(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過(guò)程 39
2.6.2　遞歸謂詞 40
2.6.3　迭代 41
2.7　歐幾里得算法 44
2.8　高階布爾過(guò)程 47
2.8.1　布爾值和謂詞上的操作 47
2.8.2　^if過(guò)程 47
2.9　自然數(shù)和遞歸 49
2.9.1　數(shù)學(xué)歸納法 49
2.9.2　自然數(shù)上的遞歸 49
2.9.3　計(jì)數(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　命名對(duì) 61
3.4.2　積類型 61
3.4.3　再議可區(qū)分并集 62
3.4.4　重新實(shí)現(xiàn)自然數(shù) 62
3.5　盒 64
3.6　列表 66
3.6.1　選擇過(guò)程 67
3.6.2　同構(gòu)列表 68
3.6.3　列表的遞歸過(guò)程 69
3.6.4　列表歸納原理 70
3.6.5　列表遞歸管理 71
3.6.6　展開 73
3.7　列表算法 77
3.7.1　元數(shù)擴(kuò)展 77
3.7.2　篩選和劃分 79
3.7.3　子列表 80
3.7.4　位置選擇 81
3.7.5　列表元素上的謂詞擴(kuò)展到列表 82
3.7.6　轉(zhuǎn)置、壓縮和解壓縮 83
3.7.7　聚合多個(gè)結(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　基本包過(guò)程 114
3.12.2　包操作 115
3.12.3　包遞歸管理 116
3.13　等價(jià)關(guān)系 120
3.14　集合 123
3.14.1　集合遞歸管理 124
3.14.2　篩選和劃分 125
3.14.3　其他集合運(yùn)算 126
3.14.4　并集、交集和差集 127
3.15　表 132
3.16　緩沖區(qū) 138
第4章　排序 142
4.1　序關(guān)系 142
4.1.1　隱式定義的等價(jià)關(guān)系 142
4.1.2　測(cè)試一個(gè)列表是否有序 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　測(cè)試二叉搜索樹不變量 154
4.3.2　從二叉搜索樹中提取一個(gè)值 155
4.3.3　二叉搜索樹排序 156
4.4　紅黑樹 158
4.4.1　實(shí)現(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　用紅黑樹實(shí)現(xiàn)表 168
4.5　堆 175
4.5.1　折疊和展開堆 178
4.5.2　堆排序 178
4.6　序統(tǒng)計(jì)量 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 圖的實(shí)現(xiàn) 208
6.1.1 圖的構(gòu)造 209
6.1.2 圖與關(guān)系 211
6.1.3 圖的性質(zhì) 212
6.1.4 其他圖訪問(wèn)方法 213
6.1.5 無(wú)向圖 215
6.2 深度優(yōu)先遍歷 221
6.2.1 圖的遍歷 221
6.2.2 深度優(yōu)先 222
6.2.3 拓?fù)渑判?223
6.2.4 可到達(dá)結(jié)點(diǎn) 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 簡(jiǎn)單低效的算法 244
7.2 Knuth-Morris-Pratt算法 246
7.3 Boyer-Moore算法 253
7.4 Rabin-Karp算法 255
附錄A　推薦讀物 260
附錄B　(afp primitives)庫(kù) 261
附錄C　如何使用AFP庫(kù) 263