Haskell函數(shù)式編程入門

目　錄
第1章　Haskell簡介　1
1．1　Haskell的由來　1
1．2　Haskell編譯器的安裝以及 編寫環(huán)境　3
1．3　GHCi的使用　4
1．3．1　GHCi中的命令　5
1．3．2　在GHCi中調(diào)用函數(shù)　5
1．4　．hs和．lhs文件、注釋與庫函數(shù)　7
1．5　第一個Haskell程序HelloWorld!　7
本章小結(jié)　8
第2章　類型系統(tǒng)和函數(shù)　9
2．1　Haskell的類型與數(shù)據(jù)　9
2．1．1　Haskell常用數(shù)據(jù)類型　9
2．1．2　函數(shù)類型　14
2．1．3　類型的別名　17
2．1．4　類型的重要性　18
2．2　Haskell中的類型類　19
2．2．1　相等類型類：Eq　20
2．2．2　有序類型類：Ord　20
2．2．3　枚舉類型類：Emum　21
2．2．4　有界類型類：Bounded　21
2．2．5　數(shù)字類型類：Num　22
2．2．6　可顯示類型類：Show　25
2．2．7　小結(jié)　25
2．3　Haskell中的函數(shù)　26
2．3．1　Haskell中的值　26
2．3．2　函數(shù)思想入門　27
2．3．3　函數(shù)的基本定義格式　28
2．3．4　λ表達式　30
2．3．5　參數(shù)的綁定　34
2．4　Haskell中的表達式　35
2．4．1　條件表達式　35
2．4．2　情況分析表達式　36
2．4．3　守衛(wèi)表達式　37
2．4．4　模式匹配　37
2．4．5　運算符與函數(shù)　38
2．4．6　運算符與自定義運算符　38
本章小結(jié)　41
第3章　基于布爾值的函數(shù)　42
3．1　關(guān)鍵字module與import簡介　42
3．2　簡易布爾值的函數(shù)　43
3．3　與非門和或非門　46
本章小結(jié)　47
第4章　庫函數(shù)及其應(yīng)用　48
4．1　預(yù)加載庫函數(shù)　48
4．1．1　常用函數(shù)　48
4．1．2　基于列表的函數(shù)　50
4．1．3　定義歷法公式　57
4．1．4　字符串處理的函數(shù)　58
4．2　字符與位函數(shù)庫簡介　60
4．2．1　Data．Char　60
4．2．2　Data．Bits　60
本章小結(jié)　61
第5章　遞歸函數(shù)　62
5．1　遞歸函數(shù)的概念　62
5．2　簡單遞歸函數(shù)　64
5．3　擴展遞歸與尾遞歸　66
5．4　互調(diào)遞歸　68
5．5　麥卡錫的91函數(shù)　69
5．6　斐波那契數(shù)列　69
5．7　十進制數(shù)字轉(zhuǎn)成羅馬數(shù)字　73
5．8　二分法查找　74
5．9　漢諾塔　75
5．10　排序算法　78
5．10．1　插入排序　78
5．10．2　冒泡排序　81
5．10．3　選擇排序　83
5．10．4　快速排序　84
5．10．5　歸并排序　86
小結(jié)　91
5．11　遞歸基本條件與程序終止　91
5．12　遞歸與不動點　92
5．13　無基本條件遞歸和惰性求值　94
本章小結(jié)　96
第6章　列表內(nèi)包　97
6．1　列表生成器　97
6．2　素數(shù)相關(guān)趣題　99
6．3　凱撒加密　101
6．3．1　加密　102
6．3．2　解密　102
6．4　排列與組合問題　104
6．4．1　排列問題　104
6．4．2　錯位排列問題　105
6．4．3　組合問題　106
6．5　八皇后問題　107
6．6　計算矩陣乘法　111
6．7　最短路徑算法與矩陣乘法　112
本章小結(jié)　116
第7章　高階函數(shù)與復(fù)合函數(shù)　117
7．1　簡單高階函數(shù)　117
7．2　折疊函數(shù)foldr與foldl　119
7．3　mapAccumL與mapAccumR函數(shù)　125
7．4　復(fù)合函數(shù)　126
本章小結(jié)　128
第8章　定義數(shù)據(jù)類型　129
8．1　數(shù)據(jù)類型的定義　129
8．1．1　枚舉類型　129
8．1．2　構(gòu)造類型　132
8．1．3　參數(shù)化類型　134
8．1．4　遞歸類型　138
8．1．5　雜合定義類型　140
8．2　類型的同構(gòu)　142
8．3　使用newtype定義類型　146
8．4　數(shù)學(xué)歸納法的有效性　148
8．5　樹　150
8．6　卡特蘭數(shù)問題　151
8．7　霍夫曼編碼　152
8．8　解24點　154
8．9　zipper　157
8．10　一般化的代數(shù)數(shù)據(jù)類型　159
8．11　類型的kind　162
8．11．1　類型的kind　162
8．11．2　空類型的聲明　164
本章小結(jié)　165
第9章　定義類型類　166
9．1　定義類型類　166
9．2　Haskell中常見類型類　169
9．2．1　常用類型類　169
9．2．2　Functor　171
9．2．3　Applicative　173
9．2．4　Alternative　177
9．2．5　簡易字符識別器　179
9．2．6　Read類型類　182
9．2．7　單位半群(Monoid)　182
9．2．8　Foldable與Monoid類型類　184
9．2．9　小結(jié)　186
9．3　類型類中的類型依賴　187
9．4　類型類中的關(guān)聯(lián)類型　192
9．5　定長列表　193
9．6　運行時重載　197
9．7　Existential類型　198
本章小結(jié)　199
第10章　Monad初步　201
10．1　Monad簡介　201
10．2　從Identity Monad開始　204
10．3　Maybe Monad　206
10．4　Monad定律　209
10．5　列表Monad　210
10．6　Monad相關(guān)運算符　210
10．7　MonadPlus　211
10．8　Functor、Applicative與Monad的關(guān)系　213
本章小結(jié)　215
第11章　系統(tǒng)編程及輸入/輸出　216
11．1　不純函數(shù)與副作用　216
11．2　IO Monad　218
11．3　輸入/輸出處理　222
11．3．1　Control．Monad中的函數(shù)　222
11．3．2　系統(tǒng)環(huán)境變量與命令行參數(shù)　224
11．3．3　數(shù)據(jù)的讀寫　225
11．3．4　格式化輸出printf函數(shù)　228
11．3．5　printf函數(shù)的簡易實現(xiàn)　229
11．4　星際譯王詞典　233
11．4．1　二分法查找　234
11．4．2　散列表的使用　237
11．5　簡易異常處理　239
11．6　Haskell中的時間　244
本章小結(jié)　245
第12章　記錄器Monad、讀取器Monad、狀態(tài)Monad　246
12．1　記錄器Monad　246
12．1．1　MonadWriter　248
12．1．2　記錄歸并排序過程　249
12．2　讀取器Monad　250
12．2．1　MonadReader　251
12．2．2　變量環(huán)境的引用　252
12．3　狀態(tài)Monad　253
12．3．1　狀態(tài)Monad標(biāo)簽器　254
12．3．2　用狀態(tài)Monad實現(xiàn)棧結(jié)構(gòu)　255
12．3．3　狀態(tài)Monad、FunApp單位半群和讀取器Monad的關(guān)系　257
12．3．4　MonadState　258
12．3．5　基于棧的計算器　258
12．4　隨機數(shù)的生成　270
本章小結(jié)　271
第13章　Monad轉(zhuǎn)換器　273
13．1　從IdentityT Monad轉(zhuǎn)換器開始　273
13．2　Monad轉(zhuǎn)換器組合與復(fù)合Monad的區(qū)別　276
13．3　Monad轉(zhuǎn)換器的組合順序　278
13．4　lift與liftIO　281
13．5　簡易Monad編譯器　282
13．6　語法分析器Monad組合子　286
13．6．1　簡易語法分析器的實現(xiàn)　287
13．6．2　Parsec庫簡介　291
13．6．3　上下文無關(guān)文法　296
13．6．4　基于語法分析器的計算器　300
本章小結(jié)　304
第14章　QuickCheck簡介　305
14．1　測試函數(shù)屬性　305
14．2　測試數(shù)據(jù)生成器　308
本章小結(jié)　310
第15章　惰性求值簡介　311
15．1　λ演算簡介　311
15．2　⊥Bottom　313
15．3　表達式形態(tài)和thunk　314
15．3．1　WHNF、HNF與NF　314
15．3．2　thunk與嚴(yán)格求值　315
15．4　求值策略　319
15．4．1　引值調(diào)用　319
15．4．2　按名調(diào)用　320
15．4．3　常序求值　320
15．5　惰性求值　321
15．6　嚴(yán)格模式匹配與惰性模式匹配　322
第16章　并行與并發(fā)編程　324
16．1　確定性的并行計算　325
16．2　輕量級線程　333
16．2．1　調(diào)度的不確定性　333
16．2．2　基本線程通信　334
16．2．3　信道　337
16．2．4　簡易聊天服務(wù)器　337
16．3　軟件事務(wù)內(nèi)存　341
16．3．1　軟件事務(wù)內(nèi)存簡介　341
16．3．2　軟件事務(wù)內(nèi)存的使用　343
16．3．3　哲學(xué)家就餐問題　347
16．3．4　圣誕老人問題　350
16．4　異步并發(fā)庫簡介　355
本章小結(jié)　357
參考文獻　358
后記　359