来自水木清华的Haskell简明教程

Haskell简明教程

来自水木清华http://www.smth.edu.cn/bbscon.php?board=FuncProgram&id=107

Damir Medak
Gerhard Navratil 

Institute for Geoinformation
Technical University Vienna 

February 2003 

译者：taowen 

北京理工大学
07120202班 

2003年6月12日 


------------------------------------------------------------------------------
--

关于functional programming有很多的书。这些书是优秀的，但是通常都打算教给学生作
者已经知道的一切东西。 

因而，一开始的时候读者可能会被搞晕来：要么是因为给出信息的数量太大，要么就是由
于缺少应用理论性论述的具体而且有用的例子。通常，读者很快就会对如何在编程中使用
抽象的概念感到好奇，但是并不知道从哪里入手。 

我想要在这儿把functional语言的基础告诉给初学者。想法是让读者能够作实际的coding
，从而对某些后台的理论背景产生好奇。假定你已经比较熟悉初级的数学了。 

然而我们必须承认，我们忽律了两个方面，但是他们可能对读者来说至关重要： 

我们不关心效率！我们想要详细说明功能和创建模型。我们不着眼于软件的速度和功能，
而是模型是否易于理解。 

我们没有定义用于界面。我们不关心同用户，其他程序或者是文件的交互。我们使用语言
仅仅是为了建模，并且使用命令行来作测试。 

1. 对读者的前提要求 
在电脑前来读这个教程是又帮助的，因为后面的所有例子能够得到立即的尝试。因而安装
Hugs(98)以及一个适当的编辑器（例如UltraEdit）是有益处的。 

1.1 如何安装Hugs？ 
如果读者不能用它进行试验，阅读任何编程语言都是令人烦躁的。对于Hskell，解决办法
是被称为Hugs的东西（Haskell User’s Gofer System）。最新的版本可以从Internet上
找到（www.Haskell.org）。 

 DOS版本 Windows版本 
命令行 dir \HUGS.EXE %F dir \WINHUGS.EXE %F 
工作目录 %P  %P  
Windows程序？ 未选中 选中 

表格1：在UltraEdit中把Hugs作为工具添加的参数 

在此刻（2003年二月），最新版时2002年11月的那个。有运行于Microsoft Windows，通用
Unix，Linux，MacOS X和MacOS 9的版本。当谈论到用户界面的时候，我们总是讲Windows
版本下的。阅读一下其他操作系统的文档。Windows版的安装文件时一个Windows安装包（
msi），双击就可以开始安装。为了避免错误和获得附加的信息，我推荐你读读帮助文件。
 

下载最新版的Hugs的文件（此时是“hugs98-Nov2002.msi”）到你的硬盘上。 

运行安装程序 

检查你是否已经安装了一个编辑器。如果你没有一个好用的，现在就获得一个。 

如果使用的是UltraEdit，在Hugs中把编辑选项（Options/Set ...）设置为：UEdit32 %s
%d/1。如果你使用不同的编辑器，把“UEdit32”替换为你选择的编辑器的名字，以及把那
些参数替换为用那个编辑器打开文件并跳转到指定行的参数。 

表格1提供了把Hugs作为工具添加到UltraEdit中必须的命令。命令行中的dir必须被Hugs安
装于目录给替换。 

1. 2 在这个教程中我们要学习一些什么？ 
这个教程是学习functional programming的艰辛之途，因为学习任何有用的东西都没有捷
径。（如果你更喜欢其他正规的办法，找到任何一本书，读一或者两章，然后你会回来的
。） 

简单的练习将似的你对Hugs有好感（我欢迎你提供注释和建议！）。我们会从类似定义个
一个函数或者数据型别这样的简单任务开始，然后进步到像面向对象编程和模块化这些更
精巧的方法上。 

2 基本型别，“到底如何让Hskell给我工作起来？” 
在Hugs中测试一下函数－保存他们在一个文件中，载入进Hugs，然后测试他们。 

2. 1 在命令行上打印“Hello, World” 
这没什么大不了的，任何语言都可以做到；Hskell有一个putstr操作来把一个字符串写到
屏幕上。打开Hugs在命令行（那个带有问号的行）上写上以下的内容： 

putstr "Hello"

结果是这样： 

Hello
(2 reductions, 7 cells)
?

第一行是命令的结果。第二行提供了关于命令的求织过程的一些信息。解释起把函数替换
为更简单的函数，直到每部分是一个能够直接实现的简单步骤（类似于其他语言的解释器
比如最原始的Basic）。这些替换被称为reduction。cell是表示用于reduction和打印结果
用的内存数目的值。 

打开编辑器（在命令行中输入“:e”）而且在编辑窗口中输入同样的命令（使用编辑命令
“new file”和“save file as”）。我们把它写作函数，也就是说我们提供一个名字（
在这例中是f）并且用字符“=”把它和函数定义分割开来。保存文件并给它扩展名“.hs”
。 

f = putstr "Hello"

在HUGS中载入文件并且运行函数。在Hugs中运行一个函数很简单。你只需要在命令行输入
函数名（这里：f）以及参数（此例中没有）。结果是： 

? f
Hello
(3 reductions, 15 cells)
?

和上面的程序的区别是reduction的数目是3（而不是2），使用的cell的数目是15（而不是
7）。reduction的数目增加了一次是因为解释器必须用putstr "Hello"替换f。这是一个额
外的reduction，它也需要一些内存。 

2. 2 在Haskell中写函数 
在functional语言中，所有东西（设置包括程序）是一个函数。因而，写一个程序实际上
是在写一个函数。你可以在一个文件中写许多函数，也就是说，你可以在一个文件中有多
个程序。每个函数可能要使用其他函数参与计算得出结果。和其他编程语言中一样，有许
多预定义的函数。包含这些函数的文件可以在“hugs98\lib”中。 

写一个函数包含两个部分。首先我们必须为参数和结果定义型别。一个函数可以没有参数
。这样的函数被称为常量函数。一个这种函数的例子是pi函数，它返回圆周率的值而且不
需要任何参数来完成这个工作。其他函数可能有一个或者多个参数。然而，每个函数有一
个结果，例如： 

increment :: Int -> Int

我们新函数的名字是increment。“::”把函数名字和型别定义分开。如果有多于一个的型
别，型别名被->分割开。列表中最后的一个型别是结果的型别。 

写一个函数的第二部分是具体的实现，例如： 

increment x = x + 1

函数increment需要一个型别为Int的参数（一个整数），并且返回一个整数。为了测试它
的功能，我们在Hugs提示行中输入“increment 2”（输入的时候不要带引号），结果入下
： 

3 :: Int

如果Hugs输出3而没有型别，进入“Options/Set..”并且选中“show type after evalua
tion”。如果没有选中这个项目，解释器仅仅输出结果而不指定型别。 

让我们再来看另外一个例子。像其他编程语言一样,Haskell为布尔值预定一了一个数据型
别。对布尔值进行的一个很重要的操作是逻辑与。虽然Haskell已经有了这个函数，我们还
是要在实现一遍。一个解决方案可能像这样： 

and1 :: Bool -> Bool -> Bool
and1 a b = if a == b then a
                     else False

这儿我们使用了一个分支（if-then-else）来把计算方法和结果分割开。如果参数是相等
的（要么都是 True 要么都是 False） 我们返回其中一个参数的值。如果参数不相同，我
们返回False。另外一个办法可能是使用模式匹配。逻辑“与”在结果是真的是时候有一个
特定的情形。在所有的其他情况下，结果都是False。我们知道特殊情况下的参数是如何的
。我们可以把这些参数写在单独的一行中，并加上结果。对于其他的所有情况，我们写第
二行： 

and2 :: Bool -> Bool -> Bool
and2 True True = True
and2 x    y    = False

在我们的例子中，我们么有使用参数来进行计算第二行的结果。知道参数的结果不是必要
，因为我们有一个固定的结果。在Haskell中，我们写“_”来代替给这些参数提供的名字
。好处是对于读者，他能够知道参数的数目，又知道结果是和这些参数的值无关的。第二
航可能写成这样： 

and2 _ _ = False

2. 3 计算二次方程的根（学习where和if then else） 
写程序的第一步是规划问题。我们必须确定解决方案的特征。 

首先，记住你正在写的函数实际上一个程序 -- 在编程中使用草稿，笔记，书和已经写好
的例子。它不是打字的活动 -- 他是工作的艺术。 

一个二次方程是这样的 （）。方程有两个根（或者说是一个，如果根一样的话）。数学的
解决办法是这样的： 

 
计算根的函数有三个输入和两个输出。如果我们对于值使用Float型别，Haskell的定义是
这样： 

roots :: (Float, Float, Float) -> (Float, Float)

函数的名字是roots。“::”把函数名和型别定义分割开来。字符“->”把不同的型别定义
分开。最后定义的型别是函数结果（输出）的型别，而其他的是参数（输入）的型别。因
而型别定义（Float, Float, Float）是我们函数的参数。它代表的是三个浮点值。函数的
结果是（Float, Float），一对浮点值。 

下一步是定义函数roots： 

roots (a,b,c) = (x1, x2) where
  x1 = e + sqrt d/(2*a)
  x2 = e - sqrt d/(2*a)
  d = b*b-4*a*c
  e = -b/(2*a)

函数的结果是pair(x1, x2)。x1和x2的值都是局部定义的（在where语句之后）。局部定义
计算部分的结果。总的来说，如果对于结果的计算需要多余一次，创建局部定义有益于部
分求值（partial calculation)。例如，局部定义d和e的值对于解决办法的两个部分（x1
和x2）都是必要的。解决办法本身可以直接写在tuple中。若能而，把他们定义于局部定义
中改善了代码的可读性，因为解决办法的匀称是显而易见的。 

使用的公式是著名的计算二次方程根的公式。 

这个函数可以工作，但是它没有考虑到对负数求平方根。我们可以用两个多项式triple p
1和p2来作测试： 

p1, p2 :: (Float, Float, Float）
p1 = (1.0, 2.0, 1.0)
p2 = (1.0, 1.0, 1.0)

对于p1，结果是 

? roots p1 (-1.0,-1.0) :: (Float, Float)
(04 reductions, 159 cells)

然而，对于p2结果是 

? roots p2
( Program error: {primSqurtFloat (-3.0)}
(61 reductions, 183 cells)

记号Program error：指出在运行时有一个错误。在文本之前的括号之所以在那儿是因为H
askell在错误发生之前就开始打印结果了。那个括号是作为结果的pair的文本的开头。在
error记号之后的文字指明了是什么错误，这里是函数primSqurtFloat不能处理负的参数-
3，因而没有实数解。函数primSqrtFloat实sqrt为型别float准备的内部实现。 

我们必须修改代码以支持处理不存在实数解这样的异常情况。 

roots (a,b,c) = if d < 0 then error "sorry" else (x1, x2)
  where x1 = e + sqrt d / (2 * a)
        x2 = e - sqrt d / (2 * a)
        d = b * b - 4 * a * c
        e = - b / (2 * a)

函数现在测试局部定义d的值，并当d为负的时候输出一个用户定义的错误，否则函数如前
一样计算方程的根。

对于这段代码有几处要解释的： 

if-then-else结构工作起来就是这么一个过程“如果条件被满足了（为真），然后执行第
一个操作（在then之后），其余的所有情况执行第二个操作（在else之后）。 

where是前面一行的一部分，因为它被缩进了，所以其后的四行必须作相同的缩进，因为它
们在同一个级别上。 

在x那一行，当d<0.0时怎么可能计算sqrt d？答案是：如果d小于零的话，它永远不会被计
算，因为functional程序只对对结果必要的表达式求值： 

程序需要d，计算d，然后它小于0.0，程序给出错误信息并结束 

如果d不小于0.0，它计算x1，然后需要e参与计算，计算e，计算x2，然后结束

函数应该被测试行为是否正确。如果解释器没有给出出错信息，那么我们的函数满足了所
有的语法规则（例如，所有的括号都已经配对）。如果在加载或者运行函数的时候有错误
，而且它包含了字type，函数的型别那儿肯定有什么问题：没有匹配函数原型，等等。最
后要说的是，语法正确的函数不一定语意正确：它可能给出错误的结果或者干脆什么结果
都没有。我们应该用一些（简单的）例子来测试新写的函数。

2.4 一些预定义的型别
表2提供了在Haskell中最重要的预定义型别的概览

Bool True, False 
Int -100, 0, 1, 2,... 
Integer -33333333333, 3, 4843056380457832945789457,... 
Float/Double -3.22425, 0.0, 3.0,... 
Char ‘a’ , ‘z’, ‘A’, ‘Z , ‘;’, ... 
String “Medak”, “Navratil”, ... 

表2：预定义型别

2.5 小结
函数有原型:声明了参数和结果型别的说明

缩进问题

顶级的声明从第一列开始，而且它们的结果是下一个从第一列开始的声明

一个声明可以被打散于任何地方，并从下一行继续，只要缩进比前一行更深就行


如果关键字where后跟多于一个的定义，它们必须有相同层级的缩进

在书写的时候，尽可能的清楚（给函数取描述性的名字）。例如，一个名字为matrixMult
的函数比mM易懂多了。

注释始终都是有益的——所有写在“--”后的都是注释。

用我们手工就可以轻易检查的例子来测试函数。

练习：把程序扩展到支持复数（复数是实数的一个pair）。

3 List，“如此简单的东西怎么能那么有用？”
在前面的练习中，我们遇到了数据型别pair(x1, x2)和triple(a, b, c)（或者更一般的说
，tuple）。pair只能有两个元素，triple只能有三个元素。我们还可以有四个，五个以及
更多元素的tuple，但元素的个数是固定的。然而，tuple中的元素可以是不同的型别。例
如，pair的第一个元素可以是名字（字符串）而第二个是年龄（数字）。

什么是list？list提供了处理同一型别，任意数目的元素的办法。一个list可以一个元素
也没有：空的list记为[]。它能包含任意型别，但所有元素的型别必须相同。换句话说：
list是同种型别元素（数字，字符串，布尔值）的一维集合。list的例子有：

[] ... 空的list 
[1, 2] ... 元素型别为整数的list 
[True, False] ... 元素型别为布尔值的list 
[(1, 2), (2, 3)] ... 整数tuple的list 
[[1, 2], [2, 3, 4]] ... 整数list的list 

字符串也是list：

"Name" = ['N' , 'a' , 'm', 'e']
对list元素的操作提供对第一个元素（list的头），以及所有其他元素（list的尾）。因
而，如果我们需要访问某个元素，我们必须递归地读list，例如下面地函数，提供了对li
st中第n个元素访问的办法：

nthListEl 1 1 = head 1
nthListEl 1 n = nthListE1 (tail 1) (n-1)

3.1 递归：functional编程的基本方法，“谁偷了我的循环和计数器”
在数学中标准的阶乘函数，用自己来定义自己：

 
阶乘是数学递推中的一个十分简单的例子——Zero-case和Induction Step（Successor C
ase）为：

p(0)，

p(n) => p(n+1)

我们可以很容易把这样的语法翻译到Haskell中来

fact 0 = 1 -- zero step
fact n = n * fact (n-1) -- induction step

程序是如何工作的？让我们看一个例子，6的阶乘：因为n==6不是零，应用induction ste
p：6*fact 5。因为n==5，不为零，应用induction step：6 * (5 * fact 4)，以此类推直
到n==0。此时应用zero-step，并终止递归。

fact 6 ==> 6 * fact 5
       ==> 6 * (5 * fact 4)
       ==> 6 * (5 * (4 * fact 3))
       ==> 6 * (5 * (4 * (3 * fact 2)))
       ==> 6 * (5 * (4 * (3 * (2 * fact 1))))
       ==> 6 * (5 * (4 * (3 * (2 * (1 * fact 0)))))
       ==> 6 * (5 * (4 * (3 * (2 * (1 * 1)))))
       ==> 6 * (5 * (4 * (3 * (2 * 1))))
       ==> 6 * (5 * (4 * (3 * 2)))
       ==> 6 * (5 * (4 * 6))
       ==> 6 * (5 * 24)
       ==> 6 * 120
       ==> 720

这个推理是基于一个很重要的事实：包括零的完全集合自然数被分为两种情况：

一个自然数要么是零（zero case）

要么是另一个自然数的successor（induction step）

简单地过一下数学是想让掌握在Haskell中施加list上地类似过程更加容易一些。对于lis
t，两种情况为：

一个空的list

一个包含一个元素和其余部分（可能是空的list）的非空list

要了解完整地定义，我们必须知道一个把元素和list“粘”到一起地一个重要函数——(:
)发音为construct的"cons"。它有一下原型：

(:) :: a -> [a] -> [a]

用起来像这样：

1 : 2 : 3 : [] = [1,2,3]    

现在组成list的递归定义的两种情况是：

[] 一个空的list
(x: xs) 一个至少有一个元素的list

List = [] | (a : List)

这意味着一个list要么是空的，要么包含一个元素并后接一个list（它又可能是空的，或
者……）。型别变量a告诉我们，list的元素可以为任何型别。list的结构不依赖于储存于
list中的数据。唯一的限制是list中的所有元素必须型别相同。我们可以有整数的list，
布尔值的list，或者浮点数的list，但我们不能创造出包含5个整数和2个布尔值的list。
有了这个定义，就可以用list来写函数了。例如，一个计算list中所有元素之和的函数：


sumList :: [Int] -> Int
sumList [] = 0
sumList (x:xs) = x + sumList xs

我们递归地把第一个元素和剩余地list分开，直到变成一个空地list。我们知道对于空的
list的结果（为零）。然后我们可以在分离的过程中逆序地把元素加起来。这意味着list
中最后的一个元素是我们第一个与0相加的数，以此类推。在处理完了list中所有元素之后
。我们有了作为list结果的list元素之和。我们也可以使用list constructor来重写读li
st中的第n个元素的函数：

nthListEl' (l:ls) 1 = l
nthListEl' (l:ls) n = nthListEl' ls (n-1)

3.2 用于list的基本函数
head 返回list的第一个元素 
tail 移除list的第一个元素 
length 返回list的长度 
reverse 反转list 
++(concat) 连接两个list：[1, 2]++[3, 4]=[1, 2, 3, 4] 
map 对list中的所有元素应用一个函数 
filter 返回满足条件的所有list元素 
foldr 把list的元素和一个指定函数与起始值合并起来 
zip 把两个list的对应元素（位于相同位置的元素）通过配对的形式合并起来 
zipWith 把两个list的对应元素（位于相同位置的元素）通过应用指定函数的形式合并起
来 

表3：有用的list函数

有几个用于list的重要元素。表3列出了最重要的list函数的一部分，并简要地说明了他们
是干什么用的。

其中的某些函数（例如map）特别有趣，因为它们有一个参数是函数——我们称这些函数是
higher order函数。在接下来的部分，我们将使用这些函数。

3.2.1 把你的名字编码成ASCII码以及译回来，（你知道map是干什么的吗？）
假定我们有一个字符串并需要字符串中每个字符的ASCII吗。Haskell中字符串是一个字符
list。因而很明显是用list函数来解决问题。函数ord应该作用于每个字符上，它能计算出
ASCII码的值。因为字符串是一个字符list，把一个字符串编码为一个ASCII码的list需要
把ord作用于字符串中的每个字符。这就是map的工作。map的型别定义是：

map :: (a -> b) -> [a] -> [b]

map函数带两个参数，一个函数一个list，并返回一个list。输入的list的元素为任意型别
a而结果list的元素为任意型别b，函数有一个型别为a的参数并返回型别为b的值。在我们
的例子当中，型别a是字符，型别b是整数。map的实现是：

map f [] = []
map f (x:xs) = f x : map f xs

它递归地把f作用于list中的所有元素，并用list constructor “:”创建一个新的list。


现在把字符串编码为ASCII码的list可以这么写：

code :: String -> [Int]
code x = map ord x

在重新把定义文件加载到Hugs之后，我们可以测试这个新写的函数：

code "Hugs"

结果是：

[72,117,103,115]

3.2.2 计算多边形的面积
让我们假定需要计算一个多边形的面积。多边形是一个有x和y坐标的点的list。计算面积
的Gaussian公式是：

 
我们现在需要用list函数来计算面积。我们从定义多边形开始，在此例中，它是点的list
，每个点是坐标的pair。用作测试的多边形可能是这样（如我们可以一眼看出的，它的面
积为10000）：

p = [(100.0,100.0),(100.0,200.0),(200.0,200.0),(200.0,100.0)]
:: [(Float,Float)]

函数p返回一个我们可以用来测试我们的函数的简单多边形（这个多边形的面积为10000）
。

我们要思考的第一步是用一种能够使用list函数的形式重新构建我们的list。很清楚，最
后一步将是计算部分面积的和。函数foldl把list的元素和指定函数合并起来并指定一个起
始值。我们要相加元素，因而必须使用“+”，因为“+”被定义为位于参数(x+y)的中间，
我们必须把它写作“(+)”，表达式“(+)xy“和“x+y”是一样的。我们函数的起始值是零
，因而函数是这样的：

sum_parts :: [Float] -> Float
sum_parts parts = (foldl (+) 0 parts) / 2

现在我们必须找出一个计算部分面积(xi-xi+1)(yi+yi+1的办法。让四个list有一下内容：


list 内容 
1 x1, x2, x3, x4 
2 x2, x3, x4, x1 
3 y1, y2, y3, y4 
4 y2, y3, y4, y1 

这将使得能够使用zipWith来计算部分和。函数zipWith定义如下（我把名字改为zipWith'
来避免和已定义的函数发生冲突）：

zipWith' :: (a -> a -> a) -> [a] -> [a] -> [a]
zipWith' _ [] _ = []
zipWith' _ _ [] = []
zipWith' f (a:as) (b:bs) = (f a b) : zipWith' f as bs

第一行定义了函数的型别。函数带两个list和一个函数（用于合并list成员）的参数。下
面两行在当其中一个list为空之时结束递归，然后最后一行表现了函数是如何工作的。它
提出两个list的第一个元素，并把函数作用于其上。结果成为结果list的一个元素。

我们其余公式的第一个部分用(xi-xi+1)告诉我们把第一个点的x坐标减去第二点的x坐标。
如果使用表4中的list，我们把第一个list的元素减去第二个list的元素。因而这行：

zipWith (-) list1 list2

对list中的所有元素作剑法。因此，完整的公式是这样的：

zipWith (*) (zipWith (-) list1 list2) (zipWith (+) list3 list4)

剩下的唯一一个问题不是list的创建。list 1和3都十分简单。它们是点的xy坐标。我们可
以使用map并应用fst和snd两个函数于list中的每个元素。fst输出一个pair，返回第一个
值。snd也输入一个pair但留下第二值。如果我们假定给我们的坐标是以(x,y)的顺序，我
们利用这样的办法得到这些list：

list1 poly = map fst poly
list3 poly = map snd poly

其中poly包含了多边形。因为如果我们调换x和y，公式也能工作，所以多边形坐标是以(x
,y)还是(y,x)的形式给出的并不重要。

另外两个list要麻烦一些。两个list都被循环移位了，我们必须取出第一个元素并安插到
list的尾部，这个可以由它完成：

moveback poly = tail poly ++ [head poly]

函数head和tail把list分为第一个元素（头）和剩余的自身也是list的list（尾）两个部
分，在表达式的外面加上方括号表示由表达式作为元素创建一个list。函数“++”（或者
concat指的是连接）。通过第二个list的元素放在第一个list的最后一个元素之后，把两
个list进行融合。

把所有这些部分综合起来就是最终的解决方案，其中我们还添加了应对于3个点（因为没有
面积）情况的出错代码：

area :: [(Float,Float)] -> Float
area [] = error "not a polygon"
area [x] = error "points do not have an area"
area [x,y] = error "lines do not have an area"
area ps = abs ((foldl (+) 0.0 parts) / 2) where
  parts = zipWith (*) (zipWith (-) l1 l2) (zipWith (+) l3 l4)
  l1 = map fst ps
  l2 = tail l1 ++ [head l1]
  l3 = map snd ps
  l4 = tail l3 ++ [head l3]

3.3 其他有用的list函数
正如在3.2节中所见，函数也可以成为其他函数的参数。对于这个的一个例子是我们在3.2
.1节中用到的map。

map :: (a -> b) -> [a] -> [b]
map f []     = []
map f (x:xs) = f x : map f xs

对于函数定义，我们不需要确切说明使用的是什么型别。然而，在运行时，知道型别是很
关键的。参数的型别在运行时获知（然后我们工作于一个指定型别的数据集）。然而结果
的型别必须不能带由歧义。在此例中，我们必须通过添加“:: Type”来指定结果的型别。


下一个很关键的list函数是filter函数。我们改了一下名字（避免和在prelude定义了的函
数发生冲突），并实现了它：

filter2 :: (a -> Bool) -> [a] -> [a]
filter2 f []     = []
filter2 f (x:xs) = if f x then x : filter2 f xs
                          else filter2 f xs

filter函数带两个参数。第一个参数是一个函数（过滤器），第二个是一个任意型别a的l
ist。过滤器输入一个list的元素并返回布尔值。如果值为真，元素留在list中，否则从结
果list中移除。

3.4 计算一序列二次方程的根
我们从二次方程（像在2.3节中那样，以实数的triple的形式保存）的list入手。任务被分
成两部分。我们必须确保所有的方程有实根，因为如果有虚根的话，函数会产生错误。因
此我们需要一个函数返回真假来判断解是实是虚：

real :: (Float, Float, Float) -> Bool
real (a,b,c) = (b*b - 4*a*c) >= 0

现在我们可以使用这个函数过虑出有实数解的方程：

p1 = (1.0,2.0,1.0) :: (Float, Float, Float)
p2 = (1.0,1.0,1.0) :: (Float, Float, Float)
ps = [p1,p2]
newPs = filter real ps
rootsOfPs = map roots newPs

ps函数返回有两个二次方程的list，第一个方程（p1）有实数解，而p2只有复数解。newP
s函数使用real来过虑ps的元素中有实数解的部分。然后结果是一个方程解的list。

练习： 使用计算复根的函数（上一个练习的题目），并把它运用于二次方程的list上去。


3.5 多样的函数定义
总是能够用不同的办法完成同一个函数。区别之处通常在定义使用的抽象和用到的函数上
。也总是能够用不同的风格处理特定的情况。下面的例子，定义了几个求list长度的函数
。虽然它们看上去很不一样，但它们都产生相同的结果。在所有这些中，抽象是一致的（
都有一个类型为[a]的参数和类型为Int的结果）

l1 [] = 0
l1 (x:xs) = 1 + l1 xs

l2 xs = if xs == [] then 0 else 1 + l2 (tail xs)

l3 xs | xs == [] = 0
      | otherwise = 1 + l3 (tail xs)

l4 = sum . map (const 1)

l5 xs = foldl inc 0 xs
  where inc x _ = x+1

l6 = foldl' (\n _ -> n + 1) 0

求list长度的特殊情况是list为空的时候，在此例中，长度为0。函数l1到l3从这点事实入
手，使用递归来计算长度。然而，它们使用了不同的方法来探测空的list：

l1使用了模式匹配

l2使用if-then-else分支

l3使用Guard记号（参见6.2）

函数l4到l6使用其他函数来执行计算。他们工作原理如下：

l4首先用1替换list中的所有元素，然后对list的成员求和

l5定义一个local函数来步增一个局部的计数器，并使用foldl函数遍历list

l6使用和l5相同的方法，但使用lambda表达式定义函数

3.6 小结
我们在此节中学到了关于list的一些东西。最重要的地方是：

list提供了一个表示个数任意的相同类型元素的极好途径

在prelude.hs 中有许多用于list的有用函数

higher-order函数map把一个函数作用于list的所有成员。

数学递推是递归的基本理论背景

递归用数学的办法代替了imperative程序中的循环结构

list类似于自然数，施加其上的递归也是类似的

map filter 和foldl/foldr是作用于list的最重要的函数而且在许多程序中都有用

在Haskell中通常有很多办法来定义同一个函数

4 表达数据
到现在为止，我们在函数中只使用了基本类型，通常需要数据结构来保存在函数中需要用
到的数据。

4.1 型别别名
让我继续那个roots的例子。roots的输入是一个triple(Float, Float, Float)而且输出是
一个pair(x1, x2)。roots的型别原型是：

roots:: (Float, Float, Float) -> (Float, Float)

如果我们在程序中有好多函数，这样的类型信息在理解这个函数到底是干什么的时候不会
很有帮助。如果是这样可能就好多了：

roots:: Poly2 -> Roots2

这就是为什么Haskell支持型别别名的原因。型别别名是对已经存在的类型或者以tuple或
list作接合的用户定义的名称

type Poly2 = (Float, Float, Float)
type Roots2 = (Float, Float)

意思是我们可以用Poly2这个名字来引用任何Float的triple而用Roots2这个名字引用floa
t的tuple。两个名字都比原来的tuple告诉了更多的信息（第一个告诉我们它包含一个二次
多项式，第二个包含了这样的多项式的根的意思）。

小结：型别别名只是已存在的数据型别的快捷方式。它会使得程序是干什么的，以及函数
有怎样的输入输出更加清楚。

4.2 用户自定义数据类型
在list([])或者tuple(pair, triple..)中结合预定义的类型通常已经足够强大了，能够解
决我们需要处理的很多问题。然而，我们优势需要自己的定义来表达：

更方便形式的Tuple: Poly=(Float, Float, Float) 
枚举类型：一周中的每天是Mon或者Tue或者Wed或者Thu或者Fri或者Sat或者Sun 
递归类型：Num(N0)要么是0，要么是一个Num的Successor 
用户自定义数据类型在基于类风格编程中扮演一个很重要的角色，并值得学习它们是如何
工作的。

data Polynom = Poly Float Float Float

解释：

data是开始一个数据类型定义的关键字 
Polynom是数据类型的名字（类型信息） 
Poly是构造函数（尝试 :t Poly） 
Float是Poly第一，二，三个参数的类型 
这意味着我们可以重写函数roots2（避免和roots名称冲突）。 

roots2 :: Polynom -> (Float, Float)
roots2 (Poly a b c) = ...
pOne, pTwo :: Polynom
pOne = Poly 1.0 2.0 1.0
pTwo = Poly 2.0 4.0 (-5.0)

在pTwo定义中数-5.0外面的括号是必须的，因为负数的记号和减法的函数名一样。没有括
号，Haskell将会误解了'-'并给出以下错误：

ERROR D:\Texte\Latex\code.hs:116 - Type error in explicitly typed binding
*** Term : pTwo
*** Type : Float -> Polynom
*** Does not match : Polynom

最重要的是类型名（Polynom）和类型构造函数（Poly）之间的区别。类型名总是出现于关
于类型信息的行中（包含'::'），而类型构造函数在关于程序的行中（包含'='）。类型构
造函数是唯一的以大写字母开关的函数，并且是唯一能够出现在表达式左边的函数

可以给类型和构造函数取相同名字,但是这样的作法是极度不赞成的!

重点:最后，另一个关于语法设计上的问题：为了避免打印函数结果带来的问题，对新定义
的数据类型增加了一下两个词：deriving show。这把自动创建了一个类show的instance作
为新的数据类型

下面的代码给了一个递归数据类型的例子。在命令行中输入：

:t Start, :t Next, :t Next (Bus), :i Bus, testbus, testint
data Bus = Start | Next (Bus) deriving Show
myBusA, myBusB, myBusC :: Bus
myBusA = Start
myBusB = Next (Next (Next (Start)))
myBusC = Next myBusB
plus :: Bus -> Bus -> Bus
plus a Start = a
plus a (Next b) = Next (plus a b)
testBus :: Bus
testBus = plus myBusC myBusB
howFar :: Bus -> Int
howFar Start = 0
howFar (Next r) = 1 + howFar r
testInt :: Int
testInt = (+) (howFar myBusC) (howFar myBusB)

参数化数据类型
数据类型能够通过类型参数编程参数化的，在使用中必须用类型进行实例化。一个关于这
种类型的简单例子是：

data List a = L a (List a) | Empty

这个数据类型递归地定义了一个list，起点是一个空地list。任何其它地list都有一个元
素作为其头部以及一个list作为它地尾巴。list地元素是任意地，但必须具有相同类型。
几个关于这种数据类型地例子：

l1,l2,l3 :: List Integer
l1 = Empty
l2 = L 1 l1
l3 = L 5 l2
li1 = L 1.5 Empty :: List Double

多态
多态意味着单个的函数可以赋予不同类型的参数。在其他编程语言中的典型的例子是像加
减这样的数学操作符。通常对于整数和浮点数，一下的表达式都是有效的。在C++记法中，
我们会称函数为“重载的”。

a + b
a - b

5.1 Ad hoc多态
如果两个操作具有相同的名字，我们称之为ad hoc多态。当两者是完全不同的操作时，因
为不同的属性都用相同的名字而让人有些糊涂（例如'+'用来连接字符串而不具有交换律a
+b不等于b+a）。这不是想要的。程序员应当小心不要引入来自这点上的错误（编的程序不
同，读者对于'+'的预期不一样）

5.2 subset多态
一个常见类型的多态时基于数据类型的子集关系。我们从一个最一般的类型（比如说numb
er）postulate，构建子类型（整数，浮点数等等）。然后我们说家法作用域所有number型
别的对象，所以也作用于其子类型。

在haskell中，子类型不能直接定义。然而，要使用了的数据类型的必须有instance时可能
的。