(精品)2.Basictypes.ppt

《(精品)2.Basictypes.ppt》由会员分享，可在线阅读，更多相关《(精品)2.Basictypes.ppt（56页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、如何编辑Haskell程序？如何运行解释器？如何在解释器下运行一个Haskell程序？类型和函数一个程序（函数）形如f:A-B 或者 f:A-B-C,A,B,C 表示函数的输入数据集合和输出数据集合例如,Int 表示整数集合double:Int-Int mymax:Int-Int-Int问题：如何表示输入数据和输出数据？Haskell提供了哪些表示数据的类型？如何定义函数，或者定义函数的语法如何？第二章 基本类型与定义本章介绍 1.基本类型2.基本函数定义类型一个类型是一些值的集合，这些值均支持相同的运算。例如，布尔类型Bool包含两个逻辑值:True 和 False；支持&(与)，|(或)，

2、not(非)等运算。类型在Haskell中,每个合理的表达式都有它所属的类型，写作 e:t 类型t可以在编译时由系统的类型推导程序（type inference）计算出。表达式e具有类型t类型推导规则一个基本的类型推导规则是：f:A-B e:A f e:Bdouble 4:Int例如,double:Int-Int,所以 类型安全（Type Safety）但是 是错误的，称之为类型错误（type error）.double True所有的类型错误均可以在编译时发现，这使得函数程序是类型安全的：well-typed programs never go wrong(no errors at run

3、time)!.类型避免了一类错误的发生。基本类型Haskell 提供了一些基本类型，用户也可定义自己的类型。布尔类型布尔类型:BoolBool具有两个值:True和False.它们表示一个测试或者条件是否成立的两个可能的结果。布尔运算（operators）包括:&(and),|(or),not,=(equal)例如,True|False=True not True=False 可以查看 Prelude.hs中这些函数的定义。类型:Bool运算&和|称为中缀运算，其类型为:(&):Bool-Bool-Bool (|):Bool-Bool-Bool运算|是“可兼或”。我们可以定义“不可兼或”:ex

4、Or:Bool-Bool-Bool exOr x y=(x|y)¬(x&y)另一种定义 exOr的方式:exOr True x=not x exOr False x=x注意(&)中的括号不可少类型:Integers 1,2,3,:Int此类型包括介于 231 和 231 1间的整数。其中的运算包括:3+4 =7 3*7 =21 23 =8 关系运算:,=,=,Int-Int我们可以用两种方式使用+：(+)3 2 =53+3=5一个二元函数也可以使用(backquote)转变为中缀运算:7 div 2 3 7 mod 2 1Infix version of div and mod重载（Ov

5、erloading）我们使用同一个符号(=)比较整数的相等，布尔值的相等，这也表明(=)具有下列类型:Int-Int-Bool Bool-Bool-Bool这种现象称为重载（重载（overloading）:使用同一个符号或者名表示不同类型上的（相似）运算.更多的例子:(+),(-),(*)等.使用条件的定义如何定义求两个整数中较大的数，max?max:Int-Int-Int max x y|x=y =x|otherwise =y 如果条件为True,则max x y 等于 x如果条件为 False，那么 max x y 等于 y使用条件（guards）一般地，使用条件定义的函数具有下列格式:n

6、ame x1 x2 xn|g1 =e1|g2 =e2|otherwise =e 函数名 形式参数条件结果条件(2)条件必须是布尔类型的表达式，即它们的值为True 或者 False.给定一组参数，Haskell 自上而下计算条件的值，然后将第一个条件之值为True对应的结果作为函数在相应输入下的结果。所以，条件的次序很重要。定义中的条件往往覆盖所有的情况。习题习题：定义函数 maxThree，它返回三个整数中的最大值.An example using guards maxThree:Int-Int-Int-Int maxThree x y z|x=y&x=z =x|y=z =y|otherwi

7、se =zOr using a predefined function:maxThree x y z=max(max x y)zExercise:compute maxThree 6(4+3)5.条件表达式Haskell 提供下列条件表达式:if condition then m else n 其语义是,如果条件 condition(of type Bool)的值为 True,则表达式的值为 m,否则为 n,其中m和n必须具有相同的类型.例如,max x y=if x=y then x else yExercise.Define min:Int-Int-Int 使用定义做计算函数调用的计算过程

8、 用函数定义的右式代替函数；使用实在参数代替形式参数 double:Int-Int double x=2*x double 3 2*3 6计算顺序一个表达式的计算顺序可能有多种，但是，其计算结果不变.double(2+3)double 5102*(2+3)The evaluation order does not matter.递归（Recursion）问题问题:定义函数 fac:Int-Intfac n=1*2*n假如我们已知 fac(n-1)，如何计算fac n?fac n=1*2*(n-1)*n=fac(n-1)*n能否用fac(n-1)计算fac n?阶乘表nfac n01112236

9、424.已知 fac 0=1.所以 fac 1=1*1.所以 fac 2=1*2.所以 fac 3=2*3.Factorial的递归定义fac:Int-Intfac 0=1fac n|n 0=fac(n-1)*n递归基递归情况计算 Factorialsfac:Int-Intfac 0=1fac n|n 0=fac(n-1)*nfac 4?4=0False?4 0Truefac(4-1)*4fac 3*4fac 2*3*4fac 1*2*3*4fac 0*1*2*3*41*1*2*3*424原始递归原始递归定义规则：利用f(n-1)定义 f n（n 0）.直接定义f 0.如何确定一个函数是否存在

10、递归定义：可否将 f n 的计算转换为类似的 f(n-1)的计算，但是参数更简单；能否直接定义最简单的情况 f 0；QuizDefine a function power so thatpower x n=x*x*xn times(Of course,power x n=xn,but you should define power without using).QuizDefine a function power so thatpower x n=x*x*xn timespower x 0=1power x n|n 0=power x(n-1)*x Dont forget the base

11、case!Since this equals(x*x*x)*xn-1 times 一般递归（General Recursion）Examplex(2*n)=(x*x)nx(2*n+1)=(x*x)n*x如何利用f x之值计算f n 之值,其中 x小于n？一般递归的幂函数 power:Int-Int-Intpower x 0=1power x n|n mod 2=0=power(x*x)(n div 2)|n mod 2=1=power(x*x)(n div 2)*x注意不要漏掉递归基两种递归的情况这个定义有何特点呢？Comparing the VersionsFirst Versionpowe

12、r 3 5power 3 4*3power 3 3*3*3power 3 2*3*3*3power 3 1*3*3*3*3power 3 0*3*3*3*3*31*3*3*3*3*3243Second Versionpower 3 5power 9 2*3power 81 1*3power 81 0*81*31*81*32436 function calls,5 multiplications.4 function calls,4 multiplications.使用递归应注意的问题 使用递归可以将一个问题转换为类似的之问题，递归是程序设计语言中一种有力的解决问题方法；一般的问题比简单的问题更

13、容易解决，因为递归方法可以解决更复杂的问题；使用递归时应该注意保证“程序终止”（termination），即定义一个问题规模，在递归基的情况问题规模为0，其他情况下大于0，而且在定义中，每次递归调用的规模均严格减小。字符类型:CharHaskell 提高了字符类型Char.字符类型的值是单引号扩起来的单个字符，如 a,3 等.一些特殊字符：t(tab),n(newline),(backslash),(single quote),”(double quote)串类型:Strings 一个串是用双引号括起来的一些字符，如 “Hello World!”:String 串上的运算:“Hello“+“w

14、orld!”“Hello World!”show(max 5(8+4)“12”一段文本的类型实数类型 1.4,14.732,3.14159,-33.5:Float算术运算:+,-,*,/,*(exponential)关系运算:,=,=,=,/=列表类型 1,2,3,5:Int 运算:1,3+2,4,3 1,3,2,4,3 head 1,3,5 1 last 1,3,5 5注意:String=Char包括在一对方括号之间的一些同类型值或表达式整数列表类型Lists一般地，对于任意类型t,t 是类型为t的值构成的列表类型。例如,False,True,False,:Bool H,e,l,l,o,!:

15、Char(or String)“Hello”,“world”:Char (or String)空列表列表的列表多元组(True,False):(Bool,Bool)(“Bob,23,M):(String,Int,Char)一般地,对于任意类型 t1,tn,(t1,tn)是一个类型，其元素包括所有形如(a1,an)的值，其中 ai 具有类型ti.运算符运算符名使用下列字符构成的串：!#$%&*+.?|:-不过，冒号:不可作为首字符。例如:(/):Bool-Bool-Bool x/y=if x then y else x Associativity and Binding Powers To ch

16、ange associativity or binding power:infixr 7(/)(right associative)or infix 7(/)(non-associative)Binding PowerLeft associativeNon-associativeRight associative9!,!.8*,7*,/,div6+,-5:,+4/=,命令类型 writeFile:FilePath-String-IO()writeFile“myfile”“Hello”:IO()readFile“myfile”:IO String将串“Hello!”写入文件 myfile.命令类

17、型，没有返回结果返回一个串的命令类型由文件 myfile 中读入一个串，其返回结果是一个串函数类型double是类型为Int-Int的函数。一般地,t1-t2 是将类型t1之值映射到类型t2的值的函数的类型。double:Int-Intdouble x=x+x f:A-B e:AF e:B Function types运算“-”是右结合的，即类型 t1-t2-t3 等于 t1-(t2-t3)但是，(t1-t2)-t3 不可写成 t1-t2-t3Curried functions add:(Int,Int)-Int add(x,y)=x+y add:Int-Int-Int add x y=x+y

18、 Note:add 2:Int-IntUncurried versionCurried version add 2 是一个函数函数的复合 quadruple :Int-Int quadruple =double.double quadruple 3 double(double 3)double 6 12函数的复合是函数上的运算Is max correct?程序设计是一个非常容易犯错误的过程；第一次设计的程序也很少是正确的。软件开发很大一部分费用是找错和改错，即软件测试：给软件不同的输入，然后检查输出是否正确。软件测试是确保软件符合设计要求的主要方法。选择测试数据测试数据尽可能包括各种可能的情形

19、，特别是那些可能出现错误的情形，特殊情形和边界情形等。函数 max 的测试数据至少应该包含 xy,以及正负参数组合的情形。测试数据应该覆盖每一种情况，使每种情况都能运行至少一次。”Testing can never demonstrate the absence of errors in software,only their presence”Edsger W.Dijkstra测试也是找错的最有效方法 测试永远不能证明软件中不存在错误，只能证明软件中存在错误。软件规格说明（Specifications）如何说明 max 是正确的?一个规格说明（specification）陈述max应该满足的

20、性质。Property:x=max x yProperty:y Int-Boolprop_Max x y=x=max x y&y quickCheck prop_MaxOK,passed 100 testsQuickCheck 随机生成100组输入并检查测试的性质是否成立。如果不成立，则返回一个反例。Testing with QuickCheck(2)假如我们定义下列程序?max x y|x y=yMain quickCheck prop_MaxFalsifiable,after 0 tests10See http:/www.cs.chalmers.se/rjmh/QuickCheck/for

21、 QuickCheck.ExercisesDefine a function that decide if an integer is even:isEven:Int-Bool Define a function that decide if an integer is even:isOdd:Int-BoolDefine a function threeDifferent:Int-Int-Int-BoolSo that the result threeDifferent m n p is True iff all three numbers m,n,p are different.Write

22、definitions of the functions smallerRoot,largerRoot:Float-Float -Float-FloatWhich return the smaller and larger real roots of the quadratic(二次方程）.What are the types of the following values:a,c,2 (a,c,2)(False,0),(True,1)(True,False,1,0)a,d,d,a,4What are the types of the following functions?swap(x,y)

23、=(y,x)swap2 x y=(y,x)twice f x=f(f x)pair x y=(x,y)list x y=x,yCheck your answers with Hugs.Define all the functions of the following types:Bool-BoolBool-Bool-Bool(Bool,Bool)-BoolBool-(Bool,Bool)Write a function which returns the greatest common divisor of two integers,which has the following type:mygcd:Int-Int-IntFor example,mygcd 2 4=2,mygcd 3 5=1