`

来自水木清华的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时可能
的。 

分享到:
评论

相关推荐

    Haskell简明教程

    Haskell简明教程 关于functional programming

    Haskell教程(中文版)

    **Haskell教程(中文版)** Haskell是一种纯函数式编程语言,以其强大的类型系统、惰性求值和高阶函数特性而闻名。这本由Hal Daumé III编著并由乔海燕翻译的《Yet Another Haskell Tutorial》中文版,为初学者提供了...

    haskell简明课件

    ### Haskell语言基础 Haskell是一门纯函数式编程语言,它以数学为理论基础,具有高度的抽象性和强大的表达力。它采用惰性求值策略,这意味着表达式只在真正需要时才进行计算。Haskell没有变量的概念,所有的值都是...

    haskell语言教程(learn you a haskell)

    《Haskell语言教程》是一本深受开发者欢迎的在线书籍,主要目标是帮助初学者深入理解Haskell这门纯函数式编程语言。Haskell以其强大的理论基础、严格的类型系统和静态类型而著称,它鼓励程序员编写简洁、清晰且易于...

    haskell教程

    Haskell是一种纯函数式编程语言,它以其独特的...总的来说,Haskell教程会逐步引导初学者进入这个富有挑战性和乐趣的编程世界,通过学习纯函数、惰性求值、类型系统、Monads等概念,他们将能够编写出高效、优雅的代码。

    haskell中文教程

    **Haskell 中文教程概述** Haskell 是一种纯函数式编程语言,以其强大的类型系统、惰性求值和静态类型而闻名。它鼓励编写简洁、可读性强且易于维护的代码。本教程将深入探讨 Haskell 的核心概念和语法,帮助初学者...

    Haskell教程

    这份Haskell教程的版权归属于Hal Daume III,原作者在2002年至2006年间创作了这份材料,并且给予了在GNU自由文档许可证(GNU Free Documentation License)的条款下分发的权利。该许可证允许人们将作品纳入如...

    无涯教程(LearnFk)-Haskell教程离线版.pdf

    Haskell是一种标准化的通用纯函数式编程语言,它的设计基于数学原理,特别是λ演算。作为一门纯粹的函数式编程语言,Haskell强调函数是一等公民("函数是第一类对象"),其中主要的控制结构是函数。Haskell语言的...

    Haskell 编程入门五星教程

    **Haskell 编程入门五星教程** Haskell 是一种纯函数式编程语言,以其严谨的数学基础、静态类型系统和惰性求值策略而闻名。它鼓励程序员采用声明式编程风格,强调数据流和计算的表达,而不是指令的执行顺序。本教程...

    TutorialsPoint Haskell 教程.epub

    TutorialsPoint Haskell 教程.epub

    Haskell Cookbook.zip

    总之,《Haskell Cookbook》是一本全面且深入的Haskell教程,涵盖了从入门到进阶的各个层面。通过阅读和实践书中的例子,读者不仅能掌握Haskell的基本语法和特性,还能提升在函数式编程领域的思维能力和问题解决技巧...

    Real World Haskell PDF

    《Real World Haskell》是一本广泛认可的Haskell编程语言教程,旨在将这门函数式编程语言的理论与实践相结合,让读者能够在实际项目中运用Haskell。这本书的PDF版本是根据2015年3月1日的在线文档转制而成,确保了...

Global site tag (gtag.js) - Google Analytics