函數程序設計算法 Algorithms for Functional Programming

出版者的話
譯者序
前言
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