本书通过Haskell语言介绍函数式程序设计的基本思想和方法，讲解如何将数学思维应用于程序设计问题，以实现更高效的计算。本书涵盖Haskell的诸多特性，但并不是这门语言的参考指南，而是旨在利用丰富的实例和练习揭示函数式程序设计的本质。本书不要求读者具备程序设计基础，所涉及的数学知识也并不高深，既适合初学者阅读，也适合有经验的程序员参考。

理查德·伯德(Richard Bird)牛漳大学计算机实验室的荣誉退休教授，牛津大学林肯学院的研究员。他的著述颇丰，包括《Algebra of Programming》(Prentice Hall，1996)和《Pearls Of Functional ALgorithm Design》(Cambridge University Press，2010）。

出版者的话

译者序

前言

第1章　何谓函数式程序设计1

1.1　函数和类型1

1.2　函数复合2

1.3　例子：高频词2

1.4　例子：数字转换为词5

1.5　Haskell平台8

1.6　习题9

1.7　答案11

1.8　注记13

第2章　表达式、类型和值15

2.1　GHCi会话15

2.2　名称和运算符17

2.3　求值18

2.4　类型和类族20

2.5　打印值22

2.6　模块24

2.7　Haskell版面24

2.8　习题25

2.9　答案29

2.10　注记32

第3章　数33

3.1　类族Num33

3.2　其他数值类族33

3.3　取底函数的计算35

3.4　自然数37

3.5　习题39

3.6　答案40

3.7　注记41

第4章　列表42

4.1　列表记法42

4.2　枚举43

4.3　列表概括43

4.4　一些基本运算45

4.5　串联46

4.6　函数cancat、map和filter46

4.7　函数zip和zipWith49

4.8　高频词的完整解50

4.9　习题52

4.10　答案55

4.11　注记58

第5章　一个简单的数独求解器59

5.1　问题说明59

5.2　合法程序的构造63

5.3　修剪选择矩阵64

5.4　格子的扩展67

5.5　习题70

5.6　答案71

5.7　注记72

第6章　证明73

6.1　自然数上的归纳法73

6.2　列表归纳法74

6.3　函数foldr78

6.4　函数foldl81

6.5　函数scanl83

6.6　最大连续段和问题84

6.7　习题87

6.8　答案90

6.9　注记96第7章　效率97　7.1　惰性求值97

7.2　空间的控制100

7.3　运行时间的控制103

7.4　时间分析104

7.5　累积参数106

7.6　元组109

7.7　排序112

7.8　习题115

7.9　答案117

7.10　注记120

第8章　精美打印121

8.1　问题背景121

8.2　文档122

8.3　一种直接实现125

8.4　例子126

8.5　最佳格式128

8.6　项表示129

8.7　习题133

8.8　答案135

8.9　注记139

第9章　无穷列表140

9.1　复习140

9.2　循环列表141

9.3　作为极限的无穷列表143

9.4　石头剪刀布147

9.5　基于流的交互151

9.6　双向链表152

9.7　习题154

9.8　答案156

9.9　注记158

第10章　命令式函数式程序设计159

10.1　IO单子159

10.2　更多的单子162

10.3　状态单子165

10.4　ST单子167

10.5　可变数组169

10.6　不变数组173

10.7　习题175

10.8　答案178

10.9　注记183

第11章　句法分析184

11.1　单子句法分析器184

11.2　基本分析器186

11.3　选择与重复187

11.4　语法与表达式190

11.5　显示表达式192

11.6　习题194

11.7　答案196

11.8　注记198

第12章　一个简单的等式计算器199

12.1　基本思想199

12.2　表达式203

12.3　定律206

12.4　计算208

12.5　重写210

12.6　匹配211

12.7　代换213

12.8　测试计算器214

12.9　习题221

12.10　答案222

12.11　注记224

索引225