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

落日映苍穹つ 2022-04-22 06:58 237阅读 0赞

# Haskell简明教程 #

来自水木清华[http://www.smth.edu.cn/bbscon.php?board=FuncProgram&id=107][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时可能  
的。

[http_www.smth.edu.cn_bbscon.php_board_FuncProgram_id_107]: http://www.smth.edu.cn/bbscon.php?board=FuncProgram&id=107