定義新類型(共40張PPT)

定義新類型本章介紹如何使用代數(shù)類型描述數(shù)據(jù)。Slides

borrowed

from

J.Hughes為什么定義新類型前面介紹了使用Haskell值表示數(shù)據(jù)的例子，如使用

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

Borrower

=Stringtype

Book

=String但是，有些數(shù)據(jù)難以用我們已學(xué)的類型表示。例：使用什么類型表示一個(gè)星期：星期一，...,星期日(Monday,

Tuesday,

Wednesday

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

=“ahha”?使用數(shù)字?Monday

+

Tuesday?定義新類型我們可以定義只包含一個(gè)星期七天的類型：data

Day

=

Monday

|Tuesday

|Wednesday

|ThursdayFriday

|Saturday

|Sundayderiving

(Eq,

Show)定義==和

show新類型的值各不相同，它們不能相加，不

能連接。這種類型稱為代數(shù)數(shù)據(jù)類型。新類型的值(大寫字母開始)新類型上的函數(shù)可以通過模式匹配定義：weekDay::Day

->BoolweekDay

Monday

=

True

weekDay

Tuesday

=

True

weekDay

Wednesday

=

True

weekDay

Thursday

=

TrueweekDay

Friday

=TrueweekDay

Saturday

=

False

weekDay

Sunday

=

False新定義類型上的函數(shù)類型

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)考慮整數(shù)列表集合[Int]的定義

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

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

那

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

Tree

a

=Nil乘積類型多元組類型可以用具有多個(gè)分量的代數(shù)類型代替，又

稱為乘積類型。例如，data

People

=

Person

Name

Age其中Name

和

Age分別是String和

Int的別名：type

Name

=

Stringtype

Age

=Int類型People的定義可讀作：構(gòu)造People一個(gè)元素需要兩個(gè)值：

一個(gè)是類型是Name的值st,

另一個(gè)是類型為Age

的值n,

由此形成People

的值Person

st

n.代數(shù)類型定義的

一

般形式：data

Typename

=Conl

tn.

tikCon2tz

...

tzk

類型構(gòu)造符Conm

tml

...

tmkm代數(shù)數(shù)據(jù)類型的一般形式代數(shù)類型便于表示多種選擇：例：

記錄的表示data

Event

=

Call

Stringtype

History

=[(Etype

Time

=

Int表示多種選擇E.g.Call/p>

”,撥叫號(hào)碼Hangup,

etc.例：抽取撥叫號(hào)碼明細(xì)表。仍然使用模式匹配：calls::

History

->[(String,

Time,

Time)]calls((Call

number,

start):(Hangup,

end):history)=(number,

start,

end):calls

historycalls

[(Call

number,

start)]=[]--

正在進(jìn)行的通話calls抽取撥叫號(hào)碼明細(xì)表設(shè)想有一個(gè)學(xué)算術(shù)程序：程序顯示一個(gè)算術(shù)式，

并檢查結(jié)果是否正確。What

is(1+2)*3?

8Sorry,

wrong

answer!表達(dá)式(1+2)*3是數(shù)據(jù)，且不同于9。如何表示這樣的數(shù)據(jù)呢?”1+2”+

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

world**"表示什么?算術(shù)表達(dá)式使用串??表達(dá)式建模我們可以使用代數(shù)類型為算術(shù)表達(dá)式(結(jié)構(gòu))建模一個(gè)表達(dá)式可以是：·一個(gè)數(shù)n·一個(gè)變量x·表達(dá)式相加

a+b·表達(dá)式相乘a*bdata

Expr=NumVarAddMul一個(gè)表達(dá)式可以是：data

Expr

=·一個(gè)數(shù)nNumInt·一個(gè)變量xVarString·表達(dá)式相加

a+bAddExpr

Expr·表達(dá)式相乘a*bMulExpr

Expr表達(dá)式建模我們可以使用代數(shù)類型為算術(shù)表達(dá)式(結(jié)構(gòu))建模遞歸代數(shù)類型在代數(shù)類型中的表示：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表達(dá)式：22+2(1+2)*31+2*3例子試定義一個(gè)計(jì)算表達(dá)式的值的函數(shù)：eval::Expr

->Int例：

eval(Add

(Num

1)(Mul(Num

2)(Num

3))7

不考慮帶有變量的表達(dá)式。問題二二

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

n)eval

(Add

a

b)eval

(Mul

a

b)計(jì)算表達(dá)式eval::Expr

->Inta

和

b

的類型是Expr.eval

(Num

n)eval

(Add

a

b)eval

(Mul

a

b)遞歸定義的類型上的函數(shù)

往往是遞歸的。1eval

a

+

eval

beval

a

*

eval

b計(jì)算表達(dá)式eval::Expr

->Int=二二一個(gè)表達(dá)式的微分是一個(gè)表達(dá)式：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))符號(hào)微分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))例格式化表達(dá)式將表達(dá)式格式化為更易讀的字符串：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)那些括號(hào)是必需的?括號(hào)問題那些表達(dá)式可能需要括起來?什么時(shí)候需要括起來?加法加法表達(dá)式在乘法內(nèi)部1+(2+3)1+(2*3)1*(2+3)那些括號(hào)是必需的?NO!NO!YES!括號(hào)問題給

formatExpr一個(gè)額外參數(shù)用以說明其原輸入所處的上下文。data

Context

=

Multiply

|AnyOtherformatExpr::Expr->Context

->

StringformatExpr(Add

a

b)

Multiply

=”(”++

formatExpr(Add

a

b)

AnyOther++”"formatExpr(Mula

b)

=formatExpr

a

Multiply

++”*"++

formatExprb

Multiply解決括號(hào)問題許多函數(shù)對(duì)于某些輸入沒有結(jié)果。例

表上的查找.type

Table

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

MaybeInt

=

Found

Int

|Notfound

→Found

2

Notfound表示失敗失敗的通用類型我們無需對(duì)每種情況定義一個(gè)包含失敗的類型，可以

定義一個(gè)通用的類型Maybe:類型參數(shù).表示有結(jié)果表示沒有結(jié)果例

Just

2,Just

3,Nothing

:

Maybe

IntJust"hello",Nothing

:

Maybe

Stringdata

Maybe

a

=

Just

aNothingderiving

(Eq,

Show)代數(shù)類型不僅可以表示多種選擇，還可以改進(jìn)程序

的效率。下面以查找為例說明。用代數(shù)類型實(shí)現(xiàn)查找一個(gè)查找表示關(guān)鍵字及其相關(guān)信

息的集合。例如，

號(hào)碼本是姓名(關(guān)鍵

字

)

和

的集合。問題：給定一個(gè)查找表和關(guān)鍵字，找出和關(guān)鍵字相信息。John

Hughes1001Mary

Sheeran1013Rogardt

Heldal1057一個(gè)Lars

Pareto1158關(guān)的查找問題關(guān)鍵字和相關(guān)信息都可以具有任意的類型，故這兩個(gè)類型作為參數(shù)：[(”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順序查找需要檢查列表的每個(gè)元素，效率很低。假定查找表按照關(guān)鍵字

Aaboen

A有序，則可以先檢查表中間的記錄，如果它不

Hughes?是查找的紀(jì)錄，則下一步或者到前半部分查找

Nilsson

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

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

處于中間記錄前的一個(gè)查找子表·

中間紀(jì)錄；·后半部分查找表。Aabo

en

AOs

tva

ll

Evadata

Table

a

b

=Join(Table

a

b)

a

b(Table

a

b)查找表的表示Nilsson

Hans上述代數(shù)類型定義合理嗎?data

Table

a

b

=Join(Table

a

b)

a

b(Table

a

b)問題問題遞歸代數(shù)類型定義沒有“基”data

Table

a

b

=

Join(Table

a

b)

a

b(Table

a

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

如果表空，則查找失??；·

比較給定關(guān)鍵字與中間記錄關(guān)鍵字；·

如果相等，則查找成功，返回相應(yīng)信息；·

如果給定關(guān)鍵字小于中間關(guān)鍵字，則繼續(xù)到前半部分查找表查找；·

如果給定關(guān)鍵字大于中間關(guān)鍵字，則繼續(xù)到后半部分查找表查找。有序表的查找定義查找函數(shù)lookup::Ord

a=>a->Table

a

b->Maybe

bdata

Table

a

b

=Join(Table

a

b)

a

b(Table

a

b)Empty查找函數(shù)lookup::Ord

a=>a->Table

a

b->Maybe

blookup

key

Empty

=Nothinglookup

key

(Join

left

k

v

right)

遞歸函數(shù)!|key

=k

=Just

v|key<k=lookup

key

left|key>k=lookup

key

right查找函數(shù)查找表可以通過不斷插入記錄完成：insert::

Ord

a=>a->b->Table

a

b->Table

a

b插入必須保持查找表的有序性。方法：比較待插入關(guān)鍵字與中間關(guān)鍵字，如果相等則替換相應(yīng)信息，否則根據(jù)比較結(jié)果插入前半部分或

者后半部分。構(gòu)造查找表insert

key

val

Empty

=

Join

Empty

key

val