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

目　錄
第1章　Haskell簡(jiǎn)介　1
1．1　Haskell的由來(lái)　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?。甴s和．lhs文件、注釋與庫(kù)函數(shù)　7
1．5　第一個(gè)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　λ表達(dá)式　30
2．3．5　參數(shù)的綁定　34
2．4　Haskell中的表達(dá)式　35
2．4．1　條件表達(dá)式　35
2．4．2　情況分析表達(dá)式　36
2．4．3　守衛(wèi)表達(dá)式　37
2．4．4　模式匹配　37
2．4．5　運(yùn)算符與函數(shù)　38
2．4．6　運(yùn)算符與自定義運(yùn)算符　38
本章小結(jié)　41
第3章　基于布爾值的函數(shù)　42
3．1　關(guān)鍵字module與import簡(jiǎn)介　42
3．2　簡(jiǎn)易布爾值的函數(shù)　43
3．3　與非門和或非門　46
本章小結(jié)　47
第4章　庫(kù)函數(shù)及其應(yīng)用　48
4．1　預(yù)加載庫(kù)函數(shù)　48
4．1．1　常用函數(shù)　48
4．1．2　基于列表的函數(shù)　50
4．1．3　定義歷法公式　57
4．1．4　字符串處理的函數(shù)　58
4．2　字符與位函數(shù)庫(kù)簡(jiǎn)介　60
4．2．1　Data．Char　60
4．2．2　Data．Bits　60
本章小結(jié)　61
第5章　遞歸函數(shù)　62
5．1　遞歸函數(shù)的概念　62
5．2　簡(jiǎn)單遞歸函數(shù)　64
5．3　擴(kuò)展遞歸與尾遞歸　66
5．4　互調(diào)遞歸　68
5．5　麥卡錫的91函數(shù)　69
5．6　斐波那契數(shù)列　69
5．7　十進(jìn)制數(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　遞歸與不動(dòng)點(diǎn)　92
5．13　無(wú)基本條件遞歸和惰性求值　94
本章小結(jié)　96
第6章　列表內(nèi)包　97
6．1　列表生成器　97
6．2　素?cái)?shù)相關(guān)趣題　99
6．3　凱撒加密　101
6．3．1　加密　102
6．3．2　解密　102
6．4　排列與組合問(wèn)題　104
6．4．1　排列問(wèn)題　104
6．4．2　錯(cuò)位排列問(wèn)題　105
6．4．3　組合問(wèn)題　106
6．5　八皇后問(wèn)題　107
6．6　計(jì)算矩陣乘法　111
6．7　最短路徑算法與矩陣乘法　112
本章小結(jié)　116
第7章　高階函數(shù)與復(fù)合函數(shù)　117
7．1　簡(jiǎn)單高階函數(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　樹(shù)　150
8．6　卡特蘭數(shù)問(wèn)題　151
8．7　霍夫曼編碼　152
8．8　解24點(diǎn)　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中常見(jiàn)類型類　169
9．2．1　常用類型類　169
9．2．2　Functor　171
9．2．3　Applicative　173
9．2．4　Alternative　177
9．2．5　簡(jiǎn)易字符識(shí)別器　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　定長(zhǎng)列表　193
9．6　運(yùn)行時(shí)重載　197
9．7　Existential類型　198
本章小結(jié)　199
第10章　Monad初步　201
10．1　Monad簡(jiǎn)介　201
10．2　從Identity Monad開(kāi)始　204
10．3　Maybe Monad　206
10．4　Monad定律　209
10．5　列表Monad　210
10．6　Monad相關(guān)運(yù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ù)的簡(jiǎn)易實(shí)現(xiàn)　229
11．4　星際譯王詞典　233
11．4．1　二分法查找　234
11．4．2　散列表的使用　237
11．5　簡(jiǎn)易異常處理　239
11．6　Haskell中的時(shí)間　244
本章小結(jié)　245
第12章　記錄器Monad、讀取器Monad、狀態(tài)Monad　246
12．1　記錄器Monad　246
12．1．1　MonadWriter　248
12．1．2　記錄歸并排序過(guò)程　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實(shí)現(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　基于棧的計(jì)算器　258
12．4　隨機(jī)數(shù)的生成　270
本章小結(jié)　271
第13章　Monad轉(zhuǎn)換器　273
13．1　從IdentityT Monad轉(zhuǎn)換器開(kāi)始　273
13．2　Monad轉(zhuǎn)換器組合與復(fù)合Monad的區(qū)別　276
13．3　Monad轉(zhuǎn)換器的組合順序　278
13．4　lift與liftIO　281
13．5　簡(jiǎn)易Monad編譯器　282
13．6　語(yǔ)法分析器Monad組合子　286
13．6．1　簡(jiǎn)易語(yǔ)法分析器的實(shí)現(xiàn)　287
13．6．2　Parsec庫(kù)簡(jiǎn)介　291
13．6．3　上下文無(wú)關(guān)文法　296
13．6．4　基于語(yǔ)法分析器的計(jì)算器　300
本章小結(jié)　304
第14章　QuickCheck簡(jiǎn)介　305
14．1　測(cè)試函數(shù)屬性　305
14．2　測(cè)試數(shù)據(jù)生成器　308
本章小結(jié)　310
第15章　惰性求值簡(jiǎn)介　311
15．1　λ演算簡(jiǎn)介　311
15．2　⊥Bottom　313
15．3　表達(dá)式形態(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　確定性的并行計(jì)算　325
16．2　輕量級(jí)線程　333
16．2．1　調(diào)度的不確定性　333
16．2．2　基本線程通信　334
16．2．3　信道　337
16．2．4　簡(jiǎn)易聊天服務(wù)器　337
16．3　軟件事務(wù)內(nèi)存　341
16．3．1　軟件事務(wù)內(nèi)存簡(jiǎn)介　341
16．3．2　軟件事務(wù)內(nèi)存的使用　343
16．3．3　哲學(xué)家就餐問(wèn)題　347
16．3．4　圣誕老人問(wèn)題　350
16．4　異步并發(fā)庫(kù)簡(jiǎn)介　355
本章小結(jié)　357
參考文獻(xiàn)　358
后記　359