第 1 章：引言（Introduction）
原文：Graham Hutton, Programming in Haskell, Second Edition, Chapter 1。维护者已确认本书可翻译并发布用于学习研究。
本章为本书其余内容奠定背景。我们先回顾函数的概念，然后介绍函数式编程的思想，概述 Haskell 的主要特性和历史背景，最后用三个小例子展示 Haskell 的味道。
1.1 函数（Functions）
在 Haskell 中，函数是一种映射：它接收一个或多个参数，并产生一个结果。函数通过方程定义，方程给出函数名、每个参数的名字，以及一个主体，用来说明如何根据参数计算结果。
例如，函数 double 接收一个数 x，并产生结果 x + x。它可以用下面的方程定义：
double x = x + x
当函数被应用到实际参数时，结果通过把这些参数代入函数主体中的参数名来得到。这个过程可能会立刻产生一个不能继续简化的结果，例如一个数字。但更常见的是，结果会包含其他函数应用，而这些应用也必须以同样方式继续处理，直到产生最终结果。
例如，函数 double 应用于数字 3 时，结果可以按下面方式计算。每一步后的注释说明了该步应用了哪个函数：
double 3
= { applying double }
3 + 3
= { applying + }
6
类似地，嵌套应用 double (double 2) 中，函数 double 被应用了两次。可以这样计算：
double (double 2)
= { applying the inner double }
double (2 + 2)
= { applying + }
double 4
= { applying double }
4 + 4
= { applying + }
8
也可以从外层的 double 开始计算同一个表达式：
double (double 2)
= { applying the outer double }
double 2 + double 2
= { applying the first double }
(2 + 2) + double 2
= { applying the first + }
4 + double 2
= { applying double }
4 + (2 + 2)
= { applying the second + }
4 + 4
= { applying + }
8
不过，这种方法比原来的版本多了两步，因为第一步复制了表达式 double 2，导致它被简化了两次。
一般来说，在一次计算中，函数应用的顺序不会影响最终结果的值，但可能影响所需步骤数量，也可能影响计算过程是否终止。第 15 章讨论表达式如何求值时，会更详细地研究这些问题。
1.2 函数式编程（Functional programming）
什么是函数式编程？不同人有不同看法，要给出精确定义并不容易。不过，一般而言，函数式编程可以看作一种编程风格，其中最基本的计算方式是把函数应用到参数。相应地，函数式编程语言就是支持并鼓励这种风格的语言。
为了说明这些想法，考虑一个任务：计算从 1 到某个较大数字 n 之间所有整数的和。在许多当前编程语言中，这通常会通过两个整型变量完成，这些变量的值可以通过赋值操作符 = 随时间变化。其中一个变量用于累计总和，另一个变量从 1 计数到 n。例如，在 Java 中，可以用下面程序计算所需总和：
int total = 0;
for (int count = 1; count <= n; count++)
total = total + count;
也就是说，先把整型变量 total 初始化为零，然后进入一个循环，让整型变量 count 从 1 变化到 n，每轮循环都把当前计数器的值加到总和中。
在这个程序中，基本计算方式是改变存储值。执行程序会产生一串赋值。例如，当 n = 5 时，会得到下面的序列，其中赋给变量 total 的最终值就是所需总和：
total = 0;
count = 1;
total = 1;
count = 2;
total = 3;
count = 3;
total = 6;
count = 4;
total = 10;
count = 5;
total = 15;
一般来说，像 Java 这样以改变存储值作为基本计算方式的编程语言称为命令式语言，因为这类语言中的程序由命令式指令构成，这些指令精确指定计算应该如何进行。
现在考虑用 Haskell 计算从 1 到 n 的数字之和。通常会使用两个库函数完成：一个叫作 [..]，用于产生从 1 到 n 的数字列表；另一个叫作 sum，用于产生这个列表的总和：
sum [1..n]
在这个程序中，基本计算方式是把函数应用到参数。执行程序会产生一串应用。例如，当 n = 5 时，会得到下面的序列，其中序列中的最终值就是所需总和：
sum [1..5]
= { applying [..] }
sum [1,2,3,4,5]
= { applying sum }
1 + 2 + 3 + 4 + 5
= { applying + }
15
大多数命令式语言都以某种形式支持函数编程，因此 Haskell 程序 sum [1..n] 可以翻译到这些语言中。不过，许多命令式语言并不鼓励函数式风格。例如，许多这类语言不鼓励或禁止把函数存入列表等数据结构，不鼓励或禁止构造中间结构，例如上面例子中的数字列表，不鼓励或禁止函数接收函数作为参数或产生函数作为结果，也不鼓励或禁止函数根据自身来定义。相比之下，Haskell 对函数的使用方式没有这些限制，并提供了一系列特性，让使用函数编程既简单又强大。
1.3 Haskell 的特性（Features of Haskell）
下面列出 Haskell 的主要特性，并标注本书中进一步介绍这些特性的章节。
简洁的程序（第 2 章和第 4 章）
由于函数式风格具有高层性质，Haskell 程序通常比其他语言编写的程序简洁得多，上一节中的例子已经展示了这一点。此外，Haskell 的语法也以编写简洁程序为目标而设计：关键字很少，并允许使用缩进表示程序结构。虽然很难做客观比较，但 Haskell 程序通常比其他语言编写的程序短二到十倍。
强大的类型系统（第 3 章和第 8 章）
多数现代编程语言都包含某种类型系统，用于检测不兼容错误，例如错误地尝试把数字和字符相加。Haskell 的类型系统通常只需要程序员提供很少类型信息，却能在程序执行前自动检测大量不兼容错误，这依赖一种称为类型推断的精巧过程。Haskell 的类型系统也比大多数语言更强大，支持非常一般的多态和重载形式，并提供很多与类型有关的专门特性。
列表推导式（第 5 章）
在计算中，组织和操作数据最常见的方式之一是使用值列表。为此，Haskell 把列表作为语言中的基本概念，并提供一种简单而强大的推导式记法，可以通过从一个或多个已有列表中选择并过滤元素来构造新列表。使用这种推导式记法，可以清晰、简洁地定义许多常见列表函数，而不需要显式递归。
递归函数（第 6 章）
大多数程序都包含某种循环形式。在 Haskell 中，实现循环的基本机制是递归函数，也就是根据自身定义的函数。对于有其他编程风格经验的人来说，习惯递归可能需要一些时间。但我们会看到，许多计算都可以用递归函数自然且简单地定义，尤其是结合模式匹配和守卫，把不同情况分离到不同方程中时。
高阶函数（第 7 章）
Haskell 是一种高阶函数式语言，这意味着函数可以自由地接收函数作为参数，也可以产生函数作为结果。使用高阶函数，可以把常见编程模式，例如组合两个函数，定义为语言内部的函数。更一般地说，高阶函数可以用于在 Haskell 内部定义领域特定语言，例如用于列表处理、交互式编程和解析。
带效果的函数（第 10 章和第 12 章）
Haskell 中的函数是纯函数：它们把所有输入作为参数接收，并把所有输出作为结果产生。不过，许多程序需要某种形式的副作用，而这似乎与纯性相冲突，例如程序运行时从键盘读取输入，或向屏幕写入输出。Haskell 提供了一套统一框架，用于在不破坏函数纯性的前提下进行带效果编程。这套框架基于单子和 applicative 的使用。
泛型函数（第 12 章和第 14 章）
多数语言都允许定义在一系列简单类型上泛化的函数，例如不同形式的数字。不过，Haskell 类型系统还支持在更丰富结构上泛化的函数。例如，语言提供了一系列库函数，可以用于任何具有 functor、applicative、monad、foldable 或 traversable 结构的类型，并且还允许定义新的结构以及作用于这些结构的泛型函数。
惰性求值（第 15 章）
Haskell 程序使用一种称为惰性求值的技术执行，其基础思想是：只有在真正需要结果时，才执行计算。惰性求值不仅能避免不必要的计算，还能保证程序在可能终止时终止，鼓励使用中间数据结构进行模块化编程，甚至允许使用无限结构编程。
等式推理（第 16 章和第 17 章）
由于 Haskell 程序是纯函数，可以使用简单的等式推理技术执行程序、变换程序、证明程序性质，甚至直接从预期行为的规约推导程序。当与归纳法结合，用于推理通过递归定义的函数时，等式推理尤其强大。
1.4 历史背景（Historical background）
Haskell 的许多特性并不是全新的，而是最早由其他语言引入。为了帮助理解 Haskell 的背景，下面简要概括与这门语言相关的一些关键历史发展：
- 20 世纪 30 年代，Alonzo Church 提出了 lambda 演算，这是一种简单而强大的函数数学理论。
- 20 世纪 50 年代，John McCarthy 开发了 Lisp，即“LISt Processor”，通常被认为是第一种函数式编程语言。Lisp 受到 lambda 演算的一些影响，但仍然保留变量赋值作为语言的核心概念。
- 20 世纪 60 年代，Peter Landin 开发了 ISWIM，即“If you See What I Mean”，这是第一种纯函数式编程语言，强烈基于 lambda 演算，并且没有变量赋值。
- 20 世纪 70 年代，John Backus 开发了 FP，即“Functional Programming”，这是一种特别强调高阶函数和程序推理思想的函数式编程语言。
- 同样在 20 世纪 70 年代，Robin Milner 等人开发了 ML，即“Meta-Language”，这是第一批现代函数式编程语言之一，引入了多态类型和类型推断思想。
- 20 世纪 70 年代和 80 年代，David Turner 开发了一系列惰性函数式编程语言，最终形成商业化语言 Miranda，意思是“令人赞叹的”。
- 1987 年，一个由编程语言研究者组成的国际委员会启动了 Haskell 的开发。Haskell 以逻辑学家 Haskell Curry 命名，是一种标准惰性函数式编程语言。
- 20 世纪 90 年代，Philip Wadler 等人发展了类型类概念以支持重载，并发展了使用单子处理效果的方式。这两者是 Haskell 的主要创新特性。
- 2003 年，Haskell 委员会发布了 Haskell Report，定义了这门语言期待已久的稳定版本。
- 2010 年，Haskell Report 的修订更新版发布。此后，随着新的基础理论发展和新的实践经验出现，这门语言仍在持续演化。
值得注意的是，上面提到的三位人物 McCarthy、Backus 和 Milner 都曾获得 ACM 图灵奖。该奖项通常被认为是计算领域的诺贝尔奖。
1.5 Haskell 初体验（A taste of Haskell）
本章最后用三个小例子展示 Haskell 编程的味道。这些例子涉及处理不同类型的值列表，并展示语言的不同特性。
数字求和（Summing numbers）
回顾本章前面使用的函数 sum，它会产生一个数字列表的总和。在 Haskell 中，sum 可以用两个方程定义：
sum [] = 0
sum (n:ns) = n + sum ns
第一个方程说明空列表的和是零；第二个方程说明，任何由第一个数字 n 和剩余数字列表 ns 组成的非空列表，其和可以通过把 n 与 ns 的和相加得到。例如，sum [1,2,3] 的结果可以这样计算：
sum [1,2,3]
= { applying sum }
1 + sum [2,3]
= { applying sum }
1 + (2 + sum [3])
= { applying sum }
1 + (2 + (3 + sum []))
= { applying sum }
1 + (2 + (3 + 0))
= { applying + }
6
注意，虽然函数 sum 根据自身定义，因此是递归的，但它不会永远循环。特别是，sum 的每次应用都会把参数列表长度减一，直到列表最终变为空，此时递归停止并执行加法。把空列表的和定义为零是合适的，因为零是加法的单位元。也就是说，对于任何数字 x，都有 0 + x = x 且 x + 0 = x。
在 Haskell 中，每个函数都有一个类型，用于指定其参数和结果的性质，并且这个类型会根据函数定义自动推断出来。例如，上面定义的函数 sum 具有下面的类型：
Num a => [a] -> a
这个类型说明，对于任意数字类型 a，sum 是一个把这类数字的列表映射为单个这类数字的函数。Haskell 支持许多不同数字类型，包括整数，例如 123，以及浮点数，例如 3.14159。因此，sum 既可以应用到整数列表，就像上面的计算那样，也可以应用到浮点数列表。
类型提供了关于函数性质的有用信息。但更重要的是，类型的使用允许程序中的许多错误在程序执行前被自动检测出来。特别是，对于程序中每一次函数应用，系统都会检查实际参数类型是否与函数本身的类型兼容。例如，尝试把函数 sum 应用到字符列表会被报告为错误，因为字符不是数字类型。
值排序（Sorting values）
现在考虑一个关于列表的更复杂函数，它展示了 Haskell 的其他几个方面。假设定义函数 qsort 如下：
qsort [] = []
qsort (x:xs) = qsort smaller ++ [x] ++ qsort larger
where
smaller = [a | a <- xs, a <= x]
larger = [b | b <- xs, b > x]
在这个定义中，++ 是连接两个列表的操作符。例如，[1,2,3] ++ [4,5] = [1,2,3,4,5]。而 where 是引入局部定义的关键字。这里定义了列表 smaller，它包含列表 xs 中所有小于或等于 x 的元素 a；同时定义了列表 larger，它包含 xs 中所有大于 x 的元素 b。例如，如果 x = 3 且 xs = [5,1,4,2]，那么 smaller = [1,2]，larger = [5,4]。
qsort 究竟做什么？首先注意，它对单元素列表没有影响，也就是说，对于任意 x，qsort [x] = [x]。这个性质可以用简单计算验证：
qsort [x]
= { applying qsort }
qsort [] ++ [x] ++ qsort []
= { applying qsort }
[] ++ [x] ++ []
= { applying ++ }
[x]
接着，把 qsort 应用到一个示例列表，并利用上面的性质简化计算：
qsort [3,5,1,4,2]
= { applying qsort }
qsort [1,2] ++ [3] ++ qsort [5,4]
= { applying qsort }
(qsort [] ++ [1] ++ qsort [2]) ++ [3]
++ (qsort [4] ++ [5] ++ qsort [])
= { applying qsort, above property }
([] ++ [1] ++ [2]) ++ [3] ++ ([4] ++ [5] ++ [])
= { applying ++ }
[1,2] ++ [3] ++ [4,5]
= { applying ++ }
[1,2,3,4,5]
总结来说，qsort 把示例列表排序成了数值顺序。更一般地说，这个函数会产生任意数字列表的有序版本。qsort 的第一个方程说明空列表已经有序；第二个方程说明，任何非空列表都可以通过把第一个数字插入两个排序后列表之间来排序，这两个列表分别来自剩余数字中小于或等于该数字的元素，以及大于该数字的元素。这种排序方法称为快速排序，是已知最好的排序方法之一。
上面的快速排序实现是 Haskell 能力的绝佳例子：它既清晰又简洁。此外，函数 qsort 也比最初看起来更一般，它不仅适用于数字，还适用于任何有序值类型。更准确地说，类型：
qsort :: Ord a => [a] -> [a]
说明对于任意有序值类型 a，qsort 是一个在这类值列表之间进行映射的函数。Haskell 支持许多不同有序值类型，包括数字、单个字符，例如 'a'，以及字符串，例如 "abcde"。因此，函数 qsort 也可以用于排序字符列表或字符串列表。
动作排序执行（Sequencing actions）
第三个也是最后一个例子进一步强调 Haskell 能达到的精确性和一般性。考虑一个名为 seqn 的函数，它接收一个输入输出动作列表，例如读取或写入单个字符的动作，按顺序执行这些动作，并返回结果值列表。在 Haskell 中，这个函数可以这样定义：
seqn [] = return []
seqn (act:acts) = do x <- act
xs <- seqn acts
return (x:xs)
这两个方程说明：如果动作列表为空，就返回空结果列表；否则，先执行列表中的第一个动作，再执行剩余动作，最后返回产生的结果列表。例如，表达式 seqn [getChar,getChar,getChar] 会使用读取单个字符的动作 getChar 从键盘读取三个字符，并返回包含这三个字符的列表。
函数 seqn 有趣的地方在于它的类型。根据上面的定义，可以推断出一个可能类型：
seqn :: [IO a] -> IO [a]
这个类型说明，seqn 把一个产生某种类型 a 结果的 IO 动作列表，映射为一个产生这类结果列表的单个 IO 动作。这个类型清晰而简洁地捕获了 seqn 的高层行为。更重要的是，这个类型还明确说明函数 seqn 涉及执行输入输出动作这种副作用。用类型保持纯函数和带副作用函数之间的清晰区分，是 Haskell 的核心方面，并在编程和推理方面带来重要好处。
事实上，函数 seqn 比最初看起来更加一般。特别是，它的定义方式并不专属于输入输出动作，也同样适用于其他形式的效果。例如，它也可以用于顺序执行可能改变存储值的动作、可能失败的动作、写入日志文件的动作等等。Haskell 通过下面这个更一般的类型捕获这种灵活性：
seqn :: Monad m => [m a] -> m [a]
也就是说，对于任何单子类型 m，而 IO 只是其中一个例子，seqn 都会把一个类型为 m a 的动作列表映射为一个返回 a 类型值列表的单个动作。能够定义像 seqn 这样可用于不同效果的泛型函数，是 Haskell 的一个关键特性。
1.6 章注（Chapter remarks）
Haskell Report 可以从 haskell.org 免费获得。关于函数式语言整体发展以及 Haskell 本身发展的更详细历史，可参见参考文献 [1] 和 [2]。
1.7 练习（Exercises）
- 给出另一种计算
double (double 2)结果的可能过程。 - 证明对于任意数字
x，都有sum [x] = x。 - 定义一个函数
product，用于产生一个数字列表的乘积，并用你的定义证明product [2,3,4] = 24。 - 应该如何修改函数
qsort的定义，使它产生一个反向排序后的列表？ - 如果在
qsort的原始定义中把<=替换为<，会产生什么效果？提示：考虑例子qsort [2,2,3,1,1]。
练习 1-3 的解答见附录 A。