Haskell函数式编程基础（原书第3版）

《Haskell函数式编程基础（原书第3版）》是一本非常优秀的Haskell函数式程序设计的入门书，依次介绍函数式程序设计的基本概念、编译器和解释器、函数的各种定义方式、简单程序的构造、多态和高阶函数、数组和列表的结构化数据、列表上的原始递归和推理、输入输出I/O的控制处理、类型检测方法、代数数据类型、抽象数据类型、惰性计算等内容。《Haskell函数式编程基础（原书第3版）》包含大量的实例和习题，注重程序测试、程序证明和问题求解，易读易学。《Haskell函数式编程基础（原书第3版）》循序渐进，从基本的函数式程序设计直至高级专题，让读者对Haskell的学习不断深入。

第1章 函数式程序设计简介
1.1 计算机与建模
1.2 什么是函数
1.3 图形与函数
1.4 类型
1.5 函数式程序设计语言Haskell
1.6 表达式与计算
1.7 定义
1.8 函数定义
1.9 类型与函数式程序设计
1.10 计算与求值
1.11 函数式程序设计的精髓
1.12 领域专用语言
1.13 图形的两种模型.
1.14 测试、性质和证明

第2章 认识Haskell与GHCi
2.1 第一个Haskell程序
2.2 在工作中使用Haskell
2.3 使用GHCi
2.4 标准库Prelude和Haskell函数库
2.5 模块
2.6 例子：Pictures
2.7 错误与错误信息

第3章 基本类型与定义
3.1 布尔类型Bool
3.2 整数类型：Integer和Int
3.3 重载
3.4 守卫
3.5 字符和串
3.6 浮点数Float
3.7 语法
第4章 设计与书写程序
4.1 如何开始一个Haskell程序的设计
4.2 逐步求解问题：局部定义
4.3 自定义类型：枚举类型
4.4 递归
4.5 实践中的原始递归
4.6 扩展练习：图形.
4.7 递归的一般形式
4.8 程序测试.
第5章 数据类型、多元组与列表
5.1 多元组和列表简介
5.2 元组类型
5.3 代数类型简介
5.4 本书对列表的介绍方法
5.5 Haskell的列表
5.6 列表概括
5.7 图书馆数据库

第6章 列表程序设计.
6.1 通用函数：多态
6.2 Haskell引导库Prelude中的列表函数
6.3 认识Haskell函数库
6.4 Picture例子的实现
6.5 扩展练习：图形的另一种实现
6.6 扩展练习：有位置的图形
6.7 扩展练习：超市账单
6.8 扩展练习：纸牌和纸牌游戏

第7章 定义列表上的函数
7.1 再谈模式匹配
7.2 列表与列表模式
7.3 列表上的原始递归
7.4 寻找原始递归定义
7.5 列表上的一般递归
7.6 例子：文本处理

第8章 游戏：Haskell的I/O
8.1 石头-剪刀-布的策略
8.2 为什么I/O是一个问题
8.3 输入/输出
8.4 do语法
8.5 迭代与递归
8.6 石头-剪刀-布：玩游戏

第9章 程序推理
9.1 理解定义
9.2 测试与证明
9.3 定义性、终止性和有限性
9.4 一些逻辑知识
9.5 归纳法
9.6 归纳证明的进一步例子
9.7 推广证明目标

第10章 推广：计算模型
10.1 列表上的计算模式
10.2 高阶函数：函数作为参数
10.3 折叠与原始递归
10.4 推广：拆分列表
10.5 再谈实例

第11章 高阶函数
11.1 运算：函数的复合和应用
11.2 函数的表达式：λ抽象
11.3 部分应用
11.4 卡瑞式函数
11.5 定义高阶函数
11.6 验证与通用函数

第12章 高级程序开发
12.1 再谈Picture
12.2 函数作为数据：策略组合子
12.3 函数作为数据：正则表达式匹配
12.4 函数作为数据的实例
12.5 例子：建立索引
12.6 实践中的程序开发
12.7 理解程序

第13章 重载，类族和类型检测
13.1 为什么使用重载？
13.2 引进类族
13.3 签名和实例
13.4 Haskell的预定义类族
13.5 类型检测和类型推导概述
13.6 单态类型检测
13.7 多态类型检测
13.8 类型检测与类族

第14章 代数类型
14.1 代数类型回顾
14.2 递归代数类型
14.3 多态代数类型
14.4 程序错误的表示
14.5 使用代数类型设计系统
14.6 代数类型与类族
14.7 代数类型的推理

第15章 实例研究：Hu.man编码
15.1 Haskell的模块
15.2 模块设计
15.3 编码与译码
15.4 实现一
15.5 构造Hu.man树
15.6 设计
15.7 实现二

第16章 抽象数据类型
16.1 类型表示
16.2 Haskell抽象数据类型机制
16.3 队列
16.4 设计
16.5 仿真
16.6 实现仿真
16.7 查找树
16.8 集合
16.9 关系和图
16.1 0评注

第17章 惰性计算
17.1 惰性计算
17.2 计算规则与惰性计算
17.3 再谈列表概括
17.4 数据导向编程
17.5 实例：分析表达式
17.6 无穷列表
17.7 为什么使用无穷列表
17.8 实例：仿真
17.9 再谈证明

第18章 单子程序设计
18.1 输入/输出程序
18.2 深入I/O
18.3 计算器
18.4 再谈do记法
18.5 单子：为函数式程序设计定制的语言
18.6 例子：树上的单子式计算

第19章 领域专用语言
19.1 程序语言无处不在
19.2 为什么在Haskell中嵌入DSL？
19.3 浅嵌入和深嵌入
19.4 处理正则表达式的DSL
19.5 单子式DSL
19.6 表示计算的DSL：QuickCheck中的数据生成
19.7 深入DSL

第20章 时间与空间行为
20.1 函数的复杂度
20.2 计算的复杂度
20.3 集合的实现.
20.4 空间行为
20.5 再谈折叠
20.6 避免重复计算：记忆

第21章 结论
21.1 函数式程序设计的威力
21.2 深入Haskell
21.3 网络上的Haskell
21.4 其他函数式程序设计语言

附录A 函数式，命令式和OO程序设计
A.1 值与状态
A.2 函数与变量
A.3 程序验证
A.4 记录和元组
A.5 列表和指针
A.6 高阶函数
A.7 多态
A.8 定义类型与类族
A.9 列表概括
A.10 惰性计算
A.11 状态，无穷列表和单子
A.12 结论
附录B 术语解释
附录C Haskell运算符
附录D Haskell实践
D.1 实现
D.2 下载Craft3e代码
D.3 使用GHCi
D.4 Haskell编辑器
附录E GHCi错误
E.1 语法错误
E.2 类型错误
E.3 程序错误
E.4 模块错误
E.5 系统信息
附录F 项目建设
F.1 游戏与智力测验
F.2 Web图形
F.3 逻辑
F.4 投票系统
F.5 有穷自动机
F.6 领域专用语言
参考文献
索引

《Haskell函数式编程基础（原书第3版）》：
第1章 函数式程序设计简介
本章首先概括介绍什么是函数式程序设计或者函数程序设计，以及函数式程序设计与其他方式程序设计的不同，同时介绍函数式程序设计语言Haskell。本章的目的有三个：
介绍函数式程序设计的主要思想，并解释函数和类型的概念。然后介绍如何求表达式的值以及如何书写求值的过程。一旦读者理解如何使用函数后，再介绍如何自定义一个函数。为了理解函数的功能，本章将介绍如何测试函数，以及如何使用数学证明来说明一个函数具有某种特定的性质。
以图形为例来解释以上的概念。这样做不仅是因为它可以展示Haskell在实践中的应用特点，而且也因为它是领域专用语言（DSL）的一个例子，而Haskell便是特别适用于领域专用语言的程序设计语言。
最后，对照其他程序设计方式，如面向对象的程序设计，本章将介绍函数式程序设计中更具表现力且与众不同的思想。读者由此可以看出，为什么在财经、Web2.0和多核高效程序设计等领域的许多程序开发人员选择了函数式程序语言。我们还将解释，为什么无论你在什么领域工作，函数式程序语言的思想都能让你成为一个更好的程序员。
本章将指明有关内容在后续哪些章节中有详细解释和例子说明。尽管本书是为Haskell函数式程序设计编写的教材，但是如第21章所讨论的一样，本书讨论的许多内容具有普遍意义，同样适用于其他函数程序语言。
1.1计算机与建模
过去的60年来，计算机已经由庞大、昂贵、稀少、低速及不可靠的机器过渡为小型、廉价、普及、快速和相对可靠的机器。第一代计算机是“孤立”（stand-alone）的机器，而现代计算机都连接到全球互联网络上。现代计算机不仅已经嵌入汽车和洗衣机等家用电器里，而且还成为诸如智能手机和其他个人设备的核心。如果你对计算机的重要性有所怀疑，那么设想一下如果所有的计算机都停止工作将产生的影响：那便是一夜之间整个世界将陷入一片混乱。
尽管如此，现在这个时期计算的基本目的即处理符号信息并没有多大的变化。这些信息可以是简单的情况，如超市的购物清单，或者更复杂的情况，如关于欧洲的气象系统。给定这些信息，信息处理的任务可能是计算超市购物的总支出，或者是对英格兰南部做出24小时的气象预报。
这些任务如何得以完成呢？我们需要描述信息是如何处理的。对这个过程的描述称为一个程序（program），它是用一种程序设计语言（programminglanguage）编写的。这种程序设计语言是一种计算机指令的人工形式化语言。换言之，这种语言用于编写控制计算机硬件（hardware）运行的软件（software）。
一方面，虽然计算机的体积已经由大如房屋变为小如手掌，但是其由集成电路构成的处理单元和内存组成结构以及基本工作原理基本没有变化。另一方面，计算机的编程方式却已经发生了巨大的变化。最初的程序是用直接控制计算机硬件的指令编写的，而现代程序设计语言致力于程序员思考和解决问题的“高”层次，而不是机器解决问题的“低”层次（机器层）。
程序设计语言由一个实现（implementation）来完成它在计算机上的工作，这个实现本身也是一个程序，其任务是运行由高阶语言编写的程序。本书的目的是讲授如何编写函数式程序，而非实现的细节，有关实现参见（PeytonJones1987；PeytonJones和Lester1992）。
……