introduction.tex

\chapter{导~言}
在这一章节中，我们为本书的后续部分展开打好了基础。我们从回顾函数的概念开始，然后介绍函数式编程的概念，总结Haskell的主要特点和它的历史，最后通过两个小例子“品尝”一下Haskell的味道。

\section{函数}
在Haskell中，一个\textit{函数}是一个映射，它接受一个或多个参数，并产生唯一一个结果。我们可以通过一个等式来定义函数，等式中包含函数名、参数名以及详细描述如何依据参数计算出最终结果的函数体。

例如，一个函数$double$，接受一个数字$x$作为参数，产生的结果为$x + x$，它可通过如下等式定义：\\
\hspace*{1cm} $double~x = x + x$

当一个函数被应用于实际参数时，其结果可通过将实际参数替换函数体中的参数名的方式获得。这个过程可能会立即产生一个不能被进一步简化的结果，比如一个数字。而更为常见的情况是，这个结果是一个含有其他函数程序的表达式， 我们必须以同样的方式处理这个表达式才能得到最终的结果。 

例如，程序$double~3$将函数$double$应用于数字3的结果可通过如下计算过程得出，每一步计算通过花括号里简短注释解释：

\noindent\hspace*{1cm} $double~3$ \\ 
\hspace*{1cm} = \{applying $double$\} \\
\hspace*{1cm} $3 + 3$\\
\hspace*{1cm} = \{applying +\}\\
\hspace*{1cm} $6$

同样，两次应用$double$的内嵌程序$double~(double~2)$的结果可以通过如下计算过程得出：

\noindent\hspace*{1cm} $double~(double~2)$\\
\hspace*{1cm} = \{applying the inner $double$\}\\
\hspace*{1cm} $double~(2~+~2)$\\
\hspace*{1cm} = \{applying~+~\}\\
\hspace*{1cm} $double~4$\\
\hspace*{1cm} = \{applying $double$ \}\\
\hspace*{1cm} $4+4$\\
\hspace*{1cm} = \{applying~+\}\\
\hspace*{1cm} $8$

另外，同样的结果也可以通过先从外层的函数$double$开始计算获得：

\noindent\hspace*{1cm} double~(double~2)\\
\hspace*{1cm} = \{applying the outer $double$\}\\
\hspace*{1cm} $double~2~+~double~2$\\
\hspace*{1cm} = \{applying the first $double$\}\\
\hspace*{1cm} $(2~+~2)~+~double~2$\\
\hspace*{1cm} = \{applying~the~first~+~\}\\
\hspace*{1cm} $4~+~double~2$\\
\hspace*{1cm} = \{applying $double$\}\\
\hspace*{1cm} $4~+~(2~+~2)$\\
\hspace*{1cm} = \{applying~the~second~+\}\\
\hspace*{1cm} $4 + 4$\\
\hspace*{1cm} = \{applying~+~\}\\
\hspace*{1cm} $8$

但是，这个计算过程比我们原来的版本多出两步，因为表达式$double~
2$在第一步中被复制了一份并因此被化简了两次。一般来说，函数在计算过程中应用的顺序不会影响最终的结果值，但它可能会影响到所需步骤的数量，并可能影响计算过程是否终止的判断。本书第12章针对这些问题作了更为详细的探究。

\section{函数式编程}

什么是函数式编程？见仁见智，很难给出一个确切的定义。但总的来说，函数式编程可以被看作一种\textit{编程风格}，这种风格的基本计算方式是将函数应用于实际参数。相应的，一门函数式编程语言就是\textit{支持}和\textit{鼓励}使用函数式风格的计算机编程语言。

为了说明这些概念，让我们考虑一个计算从1到$n$的整数和的任务吧。在当前大多数编程语言中，这个任务通常可以通过使用两个可随时改变的存储值变量实现，一个变量从1变到$n$，另外一个变量用来累加总数。

例如，如果我们使用赋值符号:=来改变一个变量的值，使用关键字\textbf{repeat}和\textbf{until}来反复执行一个指令序列，直到某个条件被满足，然后下面的指令序列会计算出所需的总和：

\noindent\hspace*{1cm} $count := 0$\\
\hspace*{1cm} $total := 0$\\
\hspace*{1cm} \textbf{repeat}\\
\hspace*{1cm} \quad $count := count + 1$\\
\hspace*{1cm} \quad $total := total + count$\\
\hspace*{1cm} \textbf{until}\\
\hspace*{1cm} \quad $count = n$

也就是说，我们首先将counter和total这两个变量初始化为零，然后反复递增counter，并把这个值与变量total相加，直到counter达到$n$，此时计算过程停止。

在上述程序中，计算的基本方法是改变存储的值，在某种意义上说，程序执行就是一系列的赋值操作。例如，$n
= 5$时我们得到如下序列，其中最后赋给变量$total$的值就是所需的总和：

\noindent\hspace*{1cm} $count := 0$\\ 
\hspace*{1cm} $total := 0$\\
\hspace*{1cm} $count := 1$\\
\hspace*{1cm} $total := 1$\\
\hspace*{1cm} $count := 2$\\
\hspace*{1cm} $total := 3$\\
\hspace*{1cm} $count := 3$\\
\hspace*{1cm} $total := 6$\\
\hspace*{1cm} $count := 4$\\
\hspace*{1cm} $total := 10$\\
\hspace*{1cm} $count := 5$\\
\hspace*{1cm} $total := 15$\\

通常，这种以改变存储值为基本计算方式的编程语言被称为\textit{命令式语言}，因为用这类语言编写的程序由一系列命令式指令构成，这些指令精确描述了计算过程应该如何进行。

现在让我们考虑使用Haskell来计算从1到$n$的整数和。这通常可使用两个库函数实现，一个是$[~..~]$，用于产生从1到$n$之间的数字列表;另外一个是$sum$，用于针对这个列表求和。 

\noindent\hspace*{1cm} $sum [~1..n~]$\\

在这个程序中，计算的基本方法是将函数应用于参数。在这个意义上，程序的执行过程实际上是一系列的函数应用。比如当$n
= 5$时，我们得到如下序列，最终结果就是我们所需要的总和：

\noindent\hspace*{1cm} $sum [~1..5~]$\\
\hspace*{1cm} = \{ applying $[~..~]$ \}\\
\hspace*{1cm} $sum [1,~2,~3,~4,~5]$\\
\hspace*{1cm} = \{ applying $sum$ \}\\
\hspace*{1cm} $1+2+3+4+5$\\
\hspace*{1cm} = \{ applying + \}\\
\hspace*{1cm} $15$

大多数命令式语言都支持一些使用函数编程的形式，所以Haskell程序$sum
[~1..n~]$可以被转化成这些语言。但是，大多数命令式语言不鼓励使用函数式风格编程。比如，大多数语言不鼓励或禁止函数被存储在类似列表的数据结构中，禁止构建类似上面例子中数字列表那样的中间结构;
禁止接受函数作为参数或将函数作为返回值，禁止根据自己定义自己 。相反，Haskell在如何使用函数上没有这些限制，并且提供了一系列功能特点，使得使用函数进行编程既简单又强大。

\section{Haskell的特点}
作为参考，Haskell的主要功能特点都列在了下面，并伴随有提供进一步细节的章节号。

\begin{itemize}
\item 简明的程序 (第二章和第四章)

由于函数式风格抽象层次高的本质，使用Haskell编写的程序往往比用其他语言更加\textit{简明}，正如上一节例子中说明的那样。此外，Haskell的语法设计充分考虑了简明的特点，尤其是拥有较少的关键字，并允许使用缩进来表明程序结构。虽然很难作出客观的比较，但Haskell编写的程序往往比用当前其他语言编写的程序短小2-10倍。

\item 强大的类型系统（第三章和第十章）

大多数现代编程语言都包含某种形式的\textit{类型系统}来检测不兼容错误，如试图将一个数字和一个字符相加。Haskell有一个类型系统，它仅从程序员那里获取很少量的类型信息，但却可以在程序执行之前使用一种被称为类型推断的过程自动检查出大量不兼容的错误。Haskell的类型系统也比大多数现代编程语言更为强大，它允许函数是“多态的”和“重载的”。

\item List Comprehensions（第五章）

在计算中一种最常见的构造和操作数据的方法就是使用列表。为此，Haskell提供列表作为语言的一种基本概念，并连同一个简单但功能强大的\textit{comprehension}记法，使用这些符号可以从已有列表中选择或过滤元素来构建新的列表。comprehension记法的使用使得列表上许多公共函数以一种清晰、简明的方式定义出来，而不需要显式的递归。

\item 递归函数（第六章）

大多数实用程序都包含一些形式的重复或循环。在Haskell中，实现循环的基本机制是使用根据自己定义自己的\textit{递归函数}。许多计算都能用递归函数给出一个简单和自然的定义，特别是使用“模式匹配”和“守卫”将不同情况分成不同等式时。

\item 高阶函数（第七章）

Haskell是一门\textit{高阶}函数式编程语言，这意味着在函数定义中你可以自由将函数作为参数和结果返回值。使用高阶函数接受常见的编程模式，例如组合两个函数或定义作为语言自身的函数。
更常见的是在Haskell中高阶函数可以用于定义“领域专用语言”，比如列表处理、解析以及交互式编程。

\item Monadic作用（第八章和第九章）

Haskell中的函数都是纯函数，它们接受所有输入作为参数，将所有输出作为结果返回。但是，许多程序需要某种形式的\textit{副作用}，这似乎与纯洁性有冲突，比如程序运行时从键盘读取输入或输出结果到屏幕。Haskell提供了一个不损害函数纯洁性的基于\textit{monad}数学概念的处理副作用的统一框架。

\item 惰性求值（第十二章）

Haskell程序的执行使用了一种叫\textit{惰性求值}的技术，这种技术的基本思想是直到其结果是实际需要的时候，计算才应该被执行。除了避免不必要的计算，惰性求值保证程序适时结束，鼓励以使用中间数据结构的模块式风格进行编程，甚至允许使用拥有无穷元素个数的数据结构，比如一个无穷的数字列表。

\item 程序推导

因为在Haskell中程序是纯函数，所以简单的\textit{等式推导}可用于执行程序，变换程序，证明程序属性，甚至能够从他们的行为规范中直接提取出程序。在结合使用归纳方法对递归函数进行推导时，等式推导尤为强大。
\end{itemize}

\section{历史背景}
Haskell的许多特点并非首创，都是由其他语言首次引入的。为了帮助大家了解Haskell的背景，下面简要总结一下有关Haskell语言的一些主要的历史性的发展： 

\begin{itemize}
\item 20世纪30年代，Alonzo Church发明了lambda演算，一种简单但功能强大的数学函数理论。
\item 20世纪50年代，John McCarthy发明了Lisp(列表处理器)，Lisp被公认为是世上第一种函数式编程语言。Lisp许多方面受到了lambda演算的影响，但同时仍然接受变量赋值作为语言的一个核心特征。
\item 20世纪60年代，Peter Landin发明了ISWIN(“If you See What I Mean”)，第一种纯函数式编程语言，它主要基于lambda演算，并且没有变量赋值。
\item 20世纪70年代，John Backus发明了FP("Fuctional
Programming")，一种特别强调高阶函数和程序推导思想的语言。
\item 同样也是在20世纪70年代，Robin Milner和其他人一起开发了ML(元语言），第一种现代函数式编程语言，引入了多态类型和类型推断思想。
\item 20世纪70年代和80年代，David Turner 开发出许多惰性的函数式编程语言，最终造就了可获得商业支持的Miranda（意为"令人敬佩的"）语言的出现。
\item 1987年，一个国际研究委员会发起开发Haskell语言（以逻辑学家Haskell Curry命名），一个标准的惰性函数式编程语言。
\item 2003年，该委员会公布了Haskell的报告，报告中定义了一个期待已久的Haskell的稳定版本，该版本是该语言设计者们十五年工作的成果。
\end{itemize}

值得注意的是，上面提到的三个研究人员 - McCarthy, Backus和Milner各自获得了等同于计算机领域诺贝尔奖的的ACM图灵奖。

\section{品尝Haskell}
我们在结束本章之前通过两个小例子来品尝一下Haskell编程。首先我们回顾一下本章前面使用的函数$sum$，$sum$用于计算列表中一组数字的和。在Haskell中，这个函数可通过如下两个等式定义：

\noindent\hspace*{1cm} $sum [~] = 0$\\
\hspace*{1cm} $sum (x : xs) = x + sum~xs$

第一个等式定义一个空列表的总和是零，同时第二个等式定义一个非空列表的总和是由列表中的第一个数字和后续数字组成的列表$xs$的总和相加在一起获得的。例如，$sum~[1,~2,~3]$的总和计算过程如下：

\noindent\hspace*{1cm} $sum~[1,~2,~3]$\\
\hspace*{1cm} = \{ applying $sum$ \}\\
\hspace*{1cm} $1 + sum~[2,~3]$\\
\hspace*{1cm} = \{ applying $sum$ \}\\
\hspace*{1cm} $1 + (2 + sum~[3])$\\
\hspace*{1cm} = \{ applying $sum$ \}\\
\hspace*{1cm} $1 + (2 + (3 + sum [~]))$\\
\hspace*{1cm} = \{ applying $sum$ \}\\
\hspace*{1cm} $1 + (2 + (3 + 0))$\\
\hspace*{1cm} = \{ applying + \}\\
\hspace*{1cm} $6$

注意，即使函数$sum$使用自身定义自己而形成了递归，它也不会永远循环下去。尤其是每个$sum$都将列表参数的长度减一，直到列表最终变为空表，递归过程也随之终止。将零作为空表的总和再合适不过，因为加法里零不改变加法结果，也就是说对于任何数字$x$，$0
+ x = x$ 且$x + 0 = x$。

在Haskell中，每个函数都有一个描述参数和返回值的\textit{类型}，这个类型会自动从函数的定义中推断出来。例如，函数$sum$有以下类型：

\noindent\hspace*{1cm} $Num ~a \Rightarrow [~a~] \rightarrow a$

这个类型指出对于任何数字类型$a$，$sum$是一个将一组这样的数字列表映射到一个单一数字的函数。Haskell支持许多不同类型的数字，其中包括整数，如123，“浮点数”，如3.14159。因此，$sum$可以应用于一个整数列表，正如在上面的计算过程那样，也可以应用于一个浮点数列表。

类型提供了有关函数本质的有用的信息，但更为重要的是，类型的使用使得许多错误可以在程序被执行之前被自动检查出来。尤其是，对于一个程序中的每个函数都会检查其实际参数类型与函数本身的类型是否兼容。例如，试图将函数$sum$应用于一个字符列表将报错，因为字符不是数字类型。

现在让我们考虑一个关于列表的更为有趣的函数吧，这个函数说明了Haskell其他一些方面的特性。假设我们定义了一个名为$qsort$的函数，它由以下两个等式构成：

\hspace*{1cm} $qsort [~] = [~]$\\
\hspace*{1cm} $qsort (x : xs) = qsort~smaller~++~[x]~++~qsort~larger$\\
\hspace*{3cm}                  where\\
\hspace*{4cm}                     smaller = $[a~|~a \leftarrow xs,~a ≤ x ]$\\
\hspace*{4cm}                     larger = $[b~|~b \leftarrow xs,~b > x ]$

在这个定义里，+是一个连接两个列表的操作符。例如$[1,~2,~3]~++~[4,~5] =
[1,~2,~3,~4,~5]$。
相应的，\textbf{where}是一个关键字，用于引入局部定义。在这个例子中，\textit{smaller}列表由$xs$列表中所有小于等于$x$的元素组成，同时larger列表由$xs$列表中所有大于$x$的元素组成。例如，如果$x
= 3$且$xs = [ 5,~1,~4,~2]$，那么$smaller = [1,~2]$，$larger = [5,~4]$。

$qsort$究竟做了什么？首先我们要明确它对仅有一个元素的列表不起作用，在这种意义上，对于任何$x$，$qsort~[x] = [x]$:

\noindent\hspace*{1cm} $qsort~[~x~]$\\
\hspace*{1cm} = \{applying $qsort$\}\\
\hspace*{1cm} $qsort~[~] ++ [x] ++ qsort~[~]$\\
\hspace*{1cm} = \{applying $qsort$\}\\
\hspace*{1cm} $[~]~++~[x]~++~[~]$\\
\hspace*{1cm} = \{applying ++ \}\\
\hspace*{1cm} $[x]$

相应的，现在我们将\textit{qsort}应用到一个样例列表，使用上面的定义化简计算过程：

\noindent\hspace*{1cm} $qsort~[3,~5,~1,~4,~2]$\\
\hspace*{1cm} = \{applying $qsort$\}\\
\hspace*{1cm} $qsort~[1,~2] ++ [3] ++ qsort~[5,~4]$\\
\hspace*{1cm} = \{applying $qsort$\}\\
\hspace*{1cm} $(qsort~[~]~++~[1]~++~qsort~[2])~++~[3]$\\
\hspace*{1cm} $++~(qsort~[4]~++~[5]~++~qsort~[~])$\\
\hspace*{1cm} = \{applying $qsort$ , above property\}\\
\hspace*{1cm} $([~]~++~[1]~++~[2])~++~[3]~++~([4]~++~[5]~++~[~])$\\
\hspace*{1cm} = \{applying ++\}\\
\hspace*{1cm} $[1,~2]~++~[3]~++~[4,~5]$\\
\hspace*{1cm} = \{applying ++\}\\
\hspace*{1cm} $[1,~2,~3,~4,~5]$

总之，$qsort$将示例列表按照数字顺序进行了排序。更一般地说，这个函数产生了一个任意数字列表的排序版本。$qsort$的第一个等式表明空列表是已经被排序了的，而第二个等式则表明任何非空列表都可以通过将第一个数字插入两个列表之间的方式排序，这两个列表是通过将剩余号码与该数字比较获得的，比这个数字小的号码集构成一个列表，比这个数字大的号码集构成另外一个列表。这种排序方法被称为快速排序，并且是已知的排序方法中最好的方法之一。

上面的$quicksort$的实现是一个很好的体现Haskell功能强大、清晰又简明的例子。此外，函数$qsort$也比预期更加通用，即不仅仅适合排序数字，同样适用于任何具备有序值的类型。更确切的说，类型

\noindent\hspace*{1cm} $qsort::Ord~a \Rightarrow [a ] \rightarrow [a ]$

表明对于任何具备有序值的类型，$qsort$是一个提供在这种值列表间映射的函数。Haskell支持多种有序值类型，包括数字、单个字符比如'a'以及字符串比如"abcde"。因此，$qsort$这个函数也可以用于对一个字符列表或一个字符串列表进行排序。

\section{本章备注}
Haskell报告可以从Haskel主页www.haskell.org免费下载，同时这份报告也已经出版(25)。另外Hudak的调查报告(11)更详尽的记录了关于函数式编程语言发展的历史。 

\section{习题}
\begin{enumerate}
\item Give another possible calculation for the result of $double~(double~2)$.
\item Show that $sum~[ x ] = x$ for any number $x$ .
\item Define a function $product$ that produces the product of a list of
numbers, and show using your definition that $product~[2, 3, 4] = 24$.
\item How should the definition of the function $qsort$ be modified so that it produces a reverse sorted version of a list?
\item What would be the effect of replacing ≤ by < in the definition of
$qsort$ ?\\ Hint: consider the example $qsort~[2, 2, 3, 1, 1]$.
\end{enumerate}