- 浏览: 160960 次
- 性别:
- 来自: 保山腾冲
文章分类
最新评论
-
TNTDoctor:
谢谢,标记一下,有空来看看
(转)Haskell与范畴论 -
t173625478:
文章一般般,不够透彻,以至于误解了很多函数式特性的由来和作用。 ...
(转)函数式编程另类指南 -
liyiwen007:
学习了!
很受益!
用AGG实现高质量图形输出(二) -
hqs7636:
感谢!!!!!!!
《learn to tango with D》译文 -
rocex:
多谢,刚好用到。
《learn to tango with D》译文
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中快速计算斐波那奇数列
2010-11-14 22:17 1278haskell中快速计算斐波那奇数列 看到一个在Has ... -
用haskell求水仙花数
2010-11-14 21:53 1302用haskell求水仙花数 最近对has ... -
来自网络的有关实验室语言与工程性语言的精彩论述
2010-08-24 09:44 1267来自网络的有关实验室语言与工程性语言的精彩论述 原文出自gr ... -
(转)Haskell与范畴论
2010-08-06 21:10 1749Haskell与范畴论 http://www.yi-prog ... -
(转)对 haskell 与 monad 的理解
2010-08-06 21:07 1385对 haskell 与 monad 的理解 h ... -
(转)函数式编程另类指南
2010-08-06 21:02 1166函数式编程另类指南 原文链接:Functional ... -
(转)Haskell教程
2010-08-06 20:44 983Haskell教程 http://rufi.ycool.co ...
相关推荐
Haskell简明教程 关于functional programming
**Haskell教程(中文版)** Haskell是一种纯函数式编程语言,以其强大的类型系统、惰性求值和高阶函数特性而闻名。这本由Hal Daumé III编著并由乔海燕翻译的《Yet Another Haskell Tutorial》中文版,为初学者提供了...
### Haskell语言基础 Haskell是一门纯函数式编程语言,它以数学为理论基础,具有高度的抽象性和强大的表达力。它采用惰性求值策略,这意味着表达式只在真正需要时才进行计算。Haskell没有变量的概念,所有的值都是...
《Haskell语言教程》是一本深受开发者欢迎的在线书籍,主要目标是帮助初学者深入理解Haskell这门纯函数式编程语言。Haskell以其强大的理论基础、严格的类型系统和静态类型而著称,它鼓励程序员编写简洁、清晰且易于...
Haskell是一种纯函数式编程语言,它以其独特的...总的来说,Haskell教程会逐步引导初学者进入这个富有挑战性和乐趣的编程世界,通过学习纯函数、惰性求值、类型系统、Monads等概念,他们将能够编写出高效、优雅的代码。
**Haskell 中文教程概述** Haskell 是一种纯函数式编程语言,以其强大的类型系统、惰性求值和静态类型而闻名。它鼓励编写简洁、可读性强且易于维护的代码。本教程将深入探讨 Haskell 的核心概念和语法,帮助初学者...
这份Haskell教程的版权归属于Hal Daume III,原作者在2002年至2006年间创作了这份材料,并且给予了在GNU自由文档许可证(GNU Free Documentation License)的条款下分发的权利。该许可证允许人们将作品纳入如...
Haskell是一种标准化的通用纯函数式编程语言,它的设计基于数学原理,特别是λ演算。作为一门纯粹的函数式编程语言,Haskell强调函数是一等公民("函数是第一类对象"),其中主要的控制结构是函数。Haskell语言的...
**Haskell 编程入门五星教程** Haskell 是一种纯函数式编程语言,以其严谨的数学基础、静态类型系统和惰性求值策略而闻名。它鼓励程序员采用声明式编程风格,强调数据流和计算的表达,而不是指令的执行顺序。本教程...
TutorialsPoint Haskell 教程.epub
总之,《Haskell Cookbook》是一本全面且深入的Haskell教程,涵盖了从入门到进阶的各个层面。通过阅读和实践书中的例子,读者不仅能掌握Haskell的基本语法和特性,还能提升在函数式编程领域的思维能力和问题解决技巧...
《Real World Haskell》是一本广泛认可的Haskell编程语言教程,旨在将这门函数式编程语言的理论与实践相结合,让读者能够在实际项目中运用Haskell。这本书的PDF版本是根据2015年3月1日的在线文档转制而成,确保了...