定义新类型(共40张PPT)

定义新类型本章介绍如何使用代数类型描述数据。Slides

borrowed

from

J.Hughes为什么定义新类型前面介绍了使用Haskell值表示数据的例子，如使用

[(Borrower,Book)]表示借阅卡片库，其中type

Borrower

=Stringtype

Book

=String但是，有些数据难以用我们已学的类型表示。例：使用什么类型表示一个星期：星期一，...,星期日(Monday,

Tuesday,

Wednesday

etc.).使用串?Monday++Tuesday?day

=“ahha”?使用数字?Monday

+

Tuesday?定义新类型我们可以定义只包含一个星期七天的类型：data

Day

=

Monday

|Tuesday

|Wednesday

|ThursdayFriday

|Saturday

|Sundayderiving

(Eq,

Show)定义==和

show新类型的值各不相同，它们不能相加，不

能连接。这种类型称为代数数据类型。新类型的值(大写字母开始)新类型上的函数可以通过模式匹配定义：weekDay::Day

->BoolweekDay

Monday

=

True

weekDay

Tuesday

=

True

weekDay

Wednesday

=

True

weekDay

Thursday

=

TrueweekDay

Friday

=TrueweekDay

Saturday

=

False

weekDay

Sunday

=

False新定义类型上的函数类型

Bool的定义布尔类型的定义data

Bool

=

True

|

False

deriving(Eq,

Show)True

&&

p=pFalse

&&

p=FalseNode

a(Tree

a)(Tree

a)

deriving

(Eq,

Show)depth::

Tree

a

->Intdepth

Nil=

0depth

(Node

n

tl

t2)=1+max(depth

t1)(depth

t2)类型List的定义data

List

a

=Nil|a:List

a

deriving(Eq,

Show)考虑整数列表集合[Int]的定义

(1)空列表Nils属于[Int];(2)如果

x::Int,xs::[Int],

那

么x:xs是[Int]的元素；二叉树定义data

Tree

a

=Nil乘积类型多元组类型可以用具有多个分量的代数类型代替，又

称为乘积类型。例如，data

People

=

Person

Name

Age其中Name

和

Age分别是String和

Int的别名：type

Name

=

Stringtype

Age

=Int类型People的定义可读作：构造People一个元素需要两个值：

一个是类型是Name的值st,

另一个是类型为Age

的值n,

由此形成People

的值Person

st

n.代数类型定义的

一

般形式：data

Typename

=Conl

tn.

tikCon2tz

...

tzk

类型构造符Conm

tml

...

tmkm代数数据类型的一般形式代数类型便于表示多种选择：例：

记录的表示data

Event

=

Call

Stringtype

History

=[(Etype

Time

=

Int表示多种选择E.g.Call/p>

”,拨叫号码Hangup,

etc.例：抽取拨叫号码明细表。仍然使用模式匹配：calls::

History

->[(String,

Time,

Time)]calls((Call

number,

start):(Hangup,

end):history)=(number,

start,

end):calls

historycalls

[(Call

number,

start)]=[]--

正在进行的通话calls抽取拨叫号码明细表设想有一个学算术程序：程序显示一个算术式，

并检查结果是否正确。What

is(1+2)*3?

8Sorry,

wrong

answer!表达式(1+2)*3是数据，且不同于9。如何表示这样的数据呢?”1+2”+

+”3"表示什么?”1+hello

world**"表示什么?算术表达式使用串??表达式建模我们可以使用代数类型为算术表达式(结构)建模一个表达式可以是：·一个数n·一个变量x·表达式相加

a+b·表达式相乘a*bdata

Expr=NumVarAddMul一个表达式可以是：data

Expr

=·一个数nNumInt·一个变量xVarString·表达式相加

a+bAddExpr

Expr·表达式相乘a*bMulExpr

Expr表达式建模我们可以使用代数类型为算术表达式(结构)建模递归代数类型在代数类型中的表示：Num

2Add(Num

2)(Num

2)Mul(Add(Num

1)(Num

2))(Num

3)Add(Num

1)(Mul(Num

2)(Num3))data

Expr

=

Num

Int

|

Var

StringAdd

Expr

Expr|Mul

Expr

Expr表达式：22+2(1+2)*31+2*3例子试定义一个计算表达式的值的函数：eval::Expr

->Int例：

eval(Add

(Num

1)(Mul(Num

2)(Num

3))7

不考虑带有变量的表达式。问题二二

如何定义等式的右边?二使用模式匹配：eval(Num

n)eval

(Add

a

b)eval

(Mul

a

b)计算表达式eval::Expr

->Inta

和

b

的类型是Expr.eval

(Num

n)eval

(Add

a

b)eval

(Mul

a

b)递归定义的类型上的函数

往往是递归的。1eval

a

+

eval

beval

a

*

eval

b计算表达式eval::Expr

->Int=二二一个表达式的微分是一个表达式：differentiate::Expr->String

->Exprdifferentiate(Num

n)x=Num

0differentiate(Var

y)x|x==y=Num

1|x/=y=Num

0

微分变量differentiate(Add

a

b)x

=Add

(differentiate

a

x)(differentiate

b

x)differentiate

(Mul

a

b)

x=Add(Mul

a(differentiate

b

x))(Mul

b(differentiate

a

x))符号微分differentiate

(Mul

(Num

2)(Var”x”)”x"→Add(Mul(Num

2)(differentiate(Var”x”)”x”)(Mul(Var”x”)(differentiate

(Num

2)”x”))→Add(Mul(Num

2)(Num

1))2*1+x*0(Mul(Var”x")(Num

0))例格式化表达式将表达式格式化为更易读的字符串：instance

Show

Expr

whereshow

=formatExprformatExpr(Num

n)

=

show

nformatExpr(Var

x)

=xformatExpr(Mula

b)

=

”(“++formatExpra

++”*”++formatExpr

b++")"show(Mul(Num

1)(Add

(Num

2)(Num

3)))

→”((1*2)+3)"b)=”("++formatExpra++”+"++formatExpr

b++”)"formatExpr(Adda1+(2+3)1+(2*3)1*(2+3)那些括号是必需的?括号问题那些表达式可能需要括起来?什么时候需要括起来?加法加法表达式在乘法内部1+(2+3)1+(2*3)1*(2+3)那些括号是必需的?NO!NO!YES!括号问题给

formatExpr一个额外参数用以说明其原输入所处的上下文。data

Context

=

Multiply

|AnyOtherformatExpr::Expr->Context

->

StringformatExpr(Add

a

b)

Multiply

=”(”++

formatExpr(Add

a

b)

AnyOther++”"formatExpr(Mula

b)

=formatExpr

a

Multiply

++”*"++

formatExprb

Multiply解决括号问题许多函数对于某些输入没有结果。例

表上的查找.type

Table

=[(String,Int)]lookup”y”[(”x“,1),(”y”,2)]lookup”z”[(”x”,1),(”y”,2)]data

MaybeInt

=

Found

Int

|Notfound

→Found

2

Notfound表示失败失败的通用类型我们无需对每种情况定义一个包含失败的类型，可以

定义一个通用的类型Maybe:类型参数.表示有结果表示没有结果例

Just

2,Just

3,Nothing

:

Maybe

IntJust"hello",Nothing

:

Maybe

Stringdata

Maybe

a

=

Just

aNothingderiving

(Eq,

Show)代数类型不仅可以表示多种选择，还可以改进程序

的效率。下面以查找为例说明。用代数类型实现查找一个查找表示关键字及其相关信

息的集合。例如，

号码本是姓名(关键

字

)

和

的集合。问题：给定一个查找表和关键字，找出和关键字相信息。John

Hughes1001Mary

Sheeran1013Rogardt

Heldal1057一个Lars

Pareto1158关的查找问题关键字和相关信息都可以具有任意的类型，故这两个类型作为参数：[(”x”,1),(”y”,2)]::Table

String

Inttype

Table

a

b

=[(a,b)]lookup::Orda=>a->Table

a

b->

Maybe

blookup

key

[]

=Nothinglookup

key

((k,v):t)|key==k

=

Just

vI

otherwise

=lookup

key

t使用列表的查找表lookup"y"...→

Just

2顺序查找需要检查列表的每个元素，效率很低。假定查找表按照关键字

Aaboen

A有序，则可以先检查表中间的记录，如果它不

Hughes?是查找的纪录，则下一步或者到前半部分查找

Nilsson

Hans或者到后半部分查找。Ostvall

Eva快速查找需要快速将表分解：·

处于中间记录前的一个查找子表·

中间纪录；·后半部分查找表。Aabo

en

AOs

tva

ll

Evadata

Table

a

b

=Join(Table

a

b)

a

b(Table

a

b)查找表的表示Nilsson

Hans上述代数类型定义合理吗?data

Table

a

b

=Join(Table

a

b)

a

b(Table

a

b)问题问题递归代数类型定义没有“基”data

Table

a

b

=

Join(Table

a

b)

a

b(Table

a

b)Empty加上基：空表查找方法：·

如果表空，则查找失败；·

比较给定关键字与中间记录关键字；·

如果相等，则查找成功，返回相应信息；·

如果给定关键字小于中间关键字，则继续到前半部分查找表查找；·

如果给定关键字大于中间关键字，则继续到后半部分查找表查找。有序表的查找定义查找函数lookup::Ord

a=>a->Table

a

b->Maybe

bdata

Table

a

b

=Join(Table

a

b)

a

b(Table

a

b)Empty查找函数lookup::Ord

a=>a->Table

a

b->Maybe

blookup

key

Empty

=Nothinglookup

key

(Join

left

k

v

right)

递归函数!|key

=k

=Just

v|key<k=lookup

key

left|key>k=lookup

key

right查找函数查找表可以通过不断插入记录完成：insert::

Ord

a=>a->b->Table

a

b->Table

a

b插入必须保持查找表的有序性。方法：比较待插入关键字与中间关键字，如果相等则替换相应信息，否则根据比较结果插入前半部分或

者后半部分。构造查找表insert

key

val

Empty

=

Join

Empty

key

val