Haskell程序设计基础

《Haskell程序设计基础》，乔海燕，周晓聪 著，出版社： 清华大学出版社。

清华大学出版社成立于1980年6月，是教育部主管、清华大学主办的综合性大学出版社。清华社现年出版图书、音像制品、电子出版物等近3000种，销售规模和综合实力以及在高等教育教材市场、科技图书市场、馆配图书市场占有率均名列前茅。

目录

内容简介

本书用Haskell 语言从函数式程序设计角度讲解计算机程序设计。本书前半部分介绍程序设计的基本内容， 包括数据、类型、函数、递归函数、模块、测试、多态和重载等；后半部分则突出了函数程序设计的特色内容， 包括高阶函数、代数类型、惰性计算和单子等。

全书内容编排由浅入深，语言表达清晰准确，每章都提供了难度适中的练习，各章内容都配备讲解视频， 十分便于自学。

本书是为程序设计初学者编写，可作为高等院校各专业学习程序设计的教材，也可供从事计算机软件工作 的技术人员学习函数式程序设计参考。

前言/序言

学习程序设计，必须选择一种高级程序设计语言。不同于其他介绍程序设计入门的一些书籍，本书选择了Haskell 函数式程序设计语言从函数式程序设计角度介绍程序设计。

高级程序设计语言大致可分为命令式和声明式两种。命令式语言如C、Java 和Python 等，这类语言的程序用语句序列描述如何一步步完成一个计算，其特点是有副作用。例如，对于任意正整数n，计算1~n的和1 + 2 + … + n，命令式语言的程序通常形如：

s = 0

for (int i = 1; i <= n; i++)

s = s + i

这里第一行设置变量s 的初值为0，接下来的循环语句（后两行）不断修改变量s 的值，最后s 的值便是计算结果。这种程序重点描述如何计算。

Haskell 函数式语言属于声明式语言，这种语言的程序用计算逻辑表达计算，不需要描述计算次序，其特点是无副作用。对于前面的求和问题，在Haskell 语言中可以定义数学函数sum：

sum 0 = 0

sum n = n + sum (n-1)

在这里，计算1~n之和的Haskell 函数式程序是表达式sum n，sum 是一个纯数学函数，n 是数学意义上的变量，没有副作用。函数式程序重点描述计算什么。

函数式程序设计语言是建立在计算模型演算上的通用高级程序设计语言。由于它具有更高的抽象层次，更接近于人类习惯的数学思维，因此，更便于初学者理解和掌握。

Haskell 函数式程序设计语言具有下列特点。

（1）程序简洁优美，语义清晰，容易理解。例如，对于有一定程序设计基础的程序员，用命令式语言实现快速排序并不容易。然而，下面几行简短的Haskell 代码用列表就表达了快速排序的计算逻辑：

qsort [] = []

qsort (x:xs) = qsort [y|y <- xs, y < x] ++ [x] ++

qsort [y|y <- xs, y >= x]

这里[] 表示空列表（空序列），(x:xs) 表示非空列表（非空序列），x 是第一个元素，xs 是其余元素构成的列表，[y|y <- xs, y < x] 表示xs 中小于x 的元素构成的列表，[y|y <- xs, y >= x] 表示xs 中大于或等于x 元素构成的列表，++ 表示将两个列表串接成一个列表的运算。

（2）纯函数无副作用，程序错误更少。命令式程序中的函数多为有副作用的“过程”。一个Haskell 纯函数的计算结果只与函数的输入有关，与计算次序无关，由此避免了命令式程序中由副作用引起的一类错误。

（3）静态强类型，确保类型安全。在Haskell 函数中，将一个输入类型为整数的函数应用于布尔类型是类型错误，这种错误在编译过程中可以检测出来，由此可以避免出现运行时错误。因此，类型正确的函数式程序不会出现运行时错误。

（4）多态和重载支持代码重用。Haskell 的参数多态和重载增强了程序的可重用性。例如，qsort 可用于任何类型的列表，只要这种类型支持小于、大于和等于运算即可。

（5）高阶函数支持更高抽象性，支持模块化。在Haskell 语言中，函数是“一等公民”，函数可以是其他函数的输入和输出，由此为表达更高层次的计算逻辑提供了支持，也为代码重用性和模块化提供了更大的方便。

（6）惰性计算为无穷数据结构提供支持。Haskell 是一种惰性语言，这表明它只有在需要计算时才进行计算，或者只做必要的计算。这种惰性计算允许表达无穷数据结构，由此也为模块化提供了一种新途径。

（7）支持和鼓励形式化验证。Haskell 函数没有副作用，因此，可以像对数学表达式那样对程序进行推理，也可以使用形式化工具验证其正确性，确保程序的正确性。

本书内容涵盖函数式程序设计入门的基本知识。第1章简要介绍程序设计的概念；第2章介绍Haskell 函数式程序设计的基本知识，包括数据、类型、函数、递归函数、模块和测试等基本知识；第3章进一步介绍列表程序设计，包括如何设计一个字符图形库；第4章介绍程序设计的多态和重载概念，以及Haskell 处理重载的类族机制；第5章介绍函数式程序设计的重要特性：高阶函数，包括常用的map、foldr 和filter 等；第6章介绍如何自定义类型以更准确地表达数据；第7章介绍如何设计交互程序，包括模拟计算和小游戏；第8章介绍Haskell 语言的惰性计算策略以及惰性计算对模块划分的支持，特别是生产者-消费者模式；第9章介绍函数式语言的高级特性函子与单子，包括一个单子语法分析器和一个简单计算器的实现。

函数式程序设计语言（也简称为函数程序设计语言）(①虽然不是主流程序设计语言，但是函数程序设计的概念如表达式、函数对象、map、filter 和reduce 等高阶函数已经渗透到各种主流程序设计语言如C++、Java 和Python 中。因此，从函数式程序设计语言入门学习程序设计，无论对初学者还是有基础的程序员，都将开启一扇新的程序设计科学的大门。

与其他函数式程序设计书籍相比，本书具有下列特点。

（1）适合初学程序设计的读者。

（2）内容简练，由浅入深，适合自学。

（3）本书是立体式教材，与中国大学慕课“Haskell 函数程序设计基础”配套。

本书能以现在的面貌出版，得益于许多老师和学生的支持。特别感谢裘宗燕教授、宋方敏教授和罗朝晖教授三位专家在百忙之中阅读本书初稿，并提出了许多中肯的意见！限于作者的水平，本书现在的面貌恐未能达到专家期望的水平，在此作者深表歉意！本书在编写过程中得到了清华大学出版社白立军老师和杨帆老师的大力协助，在此一并表示感谢！

本书可作为大中专院校非计算机专业程序设计入门教材，也可作为其他程序设计爱好者的自学教材。

限于作者的水平，书中可能有错误和疏漏，敬请读者不吝指正。

作者

2022 年春于中山大学东校园

( ① 本书将把“函数式程序设计”简称为“函数程序设计”，“函数式程序”简称为“函数程序”。