Haskell中的函數(shù)及類型系統(tǒng)

1、Haskell中的類型與類型系統(tǒng)編程語言分類編程語言Domain SpecificLanguage(特定領(lǐng)域語言)General Purposeprogramminglanguage(通用編程語言)SQL, HTML命令式語言命令式語言C/C+, Java,Python, C#混合范式型語言混合范式型語言Scala, OCaml, F#函數(shù)型語言函數(shù)型語言Haskell, Coq,Agda, Lisp,Clojure, ML什么是Haskell？一個(gè)強(qiáng)類型的、純的、惰性的函數(shù)式編程語言一個(gè)強(qiáng)類型的、純的、惰性的函數(shù)式編程語言第一個(gè)編譯器的版本于第一個(gè)編譯器的版本于1990年年4月發(fā)布月發(fā)布每年

2、有相當(dāng)多的博士在改進(jìn)它，進(jìn)化速度非?？烀磕暧邢喈?dāng)多的博士在改進(jìn)它，進(jìn)化速度非?？靤ee 什么是Haskell？每個(gè)值都有嚴(yán)格的類型，不能任意轉(zhuǎn)型，也沒有隱式轉(zhuǎn)型。對(duì)于純函數(shù)只要輸入確定結(jié)果必然確定，與計(jì)算機(jī)當(dāng)前的狀態(tài)無關(guān)。Haskell可以嚴(yán)格求值，7.10前需要我們手動(dòng)控制，但7.12中會(huì)有-XStrict擴(kuò)展演示用SMT Solver解百雞問題公雞每只5元，母雞每只3元，小雞3只1元，用100元錢買100只雞，求公雞、母雞、小雞各有多少只。函數(shù)反應(yīng)式編程模擬小球下落函數(shù)/運(yùn)算符（位置、結(jié)合性、優(yōu)先級(jí)）值Haskell中的主要概念Kind（多態(tài)kin

3、d、實(shí)體kind、data kind）類型(多態(tài)類型、類型類限定類型、實(shí)體類型)類型類Haskell中的值1, True函數(shù)函數(shù)not : Bool - Boolid : a - ashow : Show a = a - String運(yùn)算符只是有優(yōu)先級(jí)的函數(shù)，它們可以相互轉(zhuǎn)化運(yùn)算符只是有優(yōu)先級(jí)的函數(shù)，它們可以相互轉(zhuǎn)化(+) 1 2與與1 + 2相同相同mod 19 7與與19 mod 7相同相同Haskell中的類型基本類型：基本類型：Int, Integer, Char, type String = Char基于基本類型的函數(shù)基于基本類型的函數(shù)ord : Char - Intchr : In

4、t - Char多態(tài)類型：多態(tài)類型：a, Maybe a, (a,b)多態(tài)類型函數(shù)：多態(tài)類型函數(shù)：id : a - a,const : a - b - alength : a - Intsize : Tree a - Intfst : (a,b) - a所以的值都有精確的類型，所以的值都有精確的類型， 1 : Char, True : Bool代數(shù)類型枚舉類型枚舉類型data Bool = False | Truederiving (Eq, Show, Ord, Enum, Bounded, Read)參數(shù)化類型參數(shù)化類型類似于類似于Java中的泛型中的泛型data Maybe a = Not

5、hing | Just aderiving (Eq, Show, Ord, Read)- 解決了解決了Tony Hoare的十億美元的的十億美元的null問題問題!遞歸類型遞歸類型data Nat = Zero | Succ Natderiving (Eq, Show, Ord, Read)構(gòu)造類型構(gòu)造類型data Pair a b = Pair a b- 類型構(gòu)造器與數(shù)據(jù)構(gòu)造器名字一樣類型構(gòu)造器與數(shù)據(jù)構(gòu)造器名字一樣data Person = Person name : String, age: Intdata List a = Nil | Cons a (List a)- data a =

6、| a : aderiving (Eq, Show, Ord, Read)基于這些類型的函數(shù)每個(gè)模式實(shí)際上是匹配的構(gòu)造器與參數(shù)。每個(gè)模式實(shí)際上是匹配的構(gòu)造器與參數(shù)。not : Bool - Boolnot False = Truenot True = FalsefromJust : Maybe a - afromJust (Just x) = xfromJust Nothing = error “cannot get value from nothing”error的類型是什么？的類型是什么？基于這些類型的函數(shù)每個(gè)模式實(shí)際上是匹配的構(gòu)造器與參數(shù)。每個(gè)模式實(shí)際上是匹配的構(gòu)造器與參數(shù)。not :

7、Bool - Boolnot False = Truenot True = FalsefromJust : Maybe a - afromJust (Just x) = xfromJust Nothing = error “cannot get value from nothing”error的類型是什么？的類型是什么？error : String - a基于這些類型的函數(shù)add : Nat - Nat - Natadd Zero n = nadd (Succ n) m = add n (Succ m)foo : Person - Stringfoo (Person n s) = n + if

8、 s 18then “ is an adult”else “ is a child”sum : Int - Intsum = 0sum (x:xs) = x + sum xs類型類相當(dāng)于多種類型的公共屬性相當(dāng)于多種類型的公共屬性(=) : Eq a = a - a - Bool類型類間的有依賴關(guān)系類型類間的有依賴關(guān)系class Eq a = Ord a(=),(),(=),( a - a - Boolshow : Show a = a - String函數(shù)的重載函數(shù)的重載(+) : Num a = a - a - aInt, Integer, Double, Float都可相加都可相加Show

9、, Eq, Ord, Enum, Read, Bounded定義類型類class Eq a where(=) : a - a - Bool(/=) : a - a - Bool(=) x y = not (x /= y)(/=) x y = not (x = y)-# MINIMAL (=) | (/=) #-class Show a whereshow : a - Stringdata Person = Person Name Intinstance Eq Person where(Person n1 i1) = (Person n2 i2) = n1 = n2 & i1 = i2i

10、nstance Show Person whereshow (Person name age) = name + show ageFunctor函子類型類中的fmap函數(shù)data List a = Nil | Cons a (List a)class ListT e = null;List list = null;data Tree a = Leaf | Node a (Tree a) (Tree a)list : List Intlist = Cons 10 (Cons 11 (Cons 6 (Cons 1 Nil)tree : Tree Inttree = Node 10 (Node 11

11、 Leaf Leaf) (Node 6 (Node 1 Leaf Leaf)Leaf)Functor函子類型類中的fmap函數(shù)class Functor f wherefmap : (a - b) - f a - f binstance Functor List wherefmap f Nil = Nilfmap f (Cons a l) = Cons (f a) (fmap f l)instance Functor Tree wherefmap f Leaf = Leaffmap f (Node v l r) = Node (f v) (fmap f l) (fmapf r)可以使用可以使用

12、DeriveFunctor編譯器擴(kuò)展自動(dòng)生成編譯器擴(kuò)展自動(dòng)生成數(shù)學(xué)對(duì)于Functor的指導(dǎo)意義F(g) F(f) = F(g f)fmap g . fmap f = fmap (g.f)fmap g (fmap f v) = fmap (g.f) v-# RULE “fmap”forall g f v fmap g (fmap f v) = fmap (g.f) v #-fmap (+10) (fmap (*2) 1.10) = fmap (+10).(*2) 1.10int arrfor(int i = 0 ; i arr.length; i+)arri = arri * 2;for(int

13、 i = 0 ; i arr.length; i+)arri = arri + 10;類型類與Java的接口的不同1、接口在、接口在Haskell相當(dāng)于是一個(gè)字典，函數(shù)調(diào)用會(huì)根據(jù)不同的類型相當(dāng)于是一個(gè)字典，函數(shù)調(diào)用會(huì)根據(jù)不同的類型來傳遞。多幾個(gè)類型類限定相當(dāng)于是多傳入了幾個(gè)字典。來傳遞。多幾個(gè)類型類限定相當(dāng)于是多傳入了幾個(gè)字典。Java中要中要把接口合并起來有些啰嗦。把接口合并起來有些啰嗦。2、由于、由于Haskell的類型是代數(shù)數(shù)據(jù)類型，即全部可以用單位元、類的類型是代數(shù)數(shù)據(jù)類型，即全部可以用單位元、類型加法、類型乘法、類型復(fù)合來定義，所以類型類實(shí)例可以自動(dòng)實(shí)現(xiàn)型加法、類型乘法、類型復(fù)合來定

14、義，所以類型類實(shí)例可以自動(dòng)實(shí)現(xiàn)能力極強(qiáng)，而且方法特別多能力極強(qiáng)，而且方法特別多通用編程、摒棄模板化編程、元編程。通用編程、摒棄模板化編程、元編程。3、還有很多其他不同。、還有很多其他不同。演示：處理演示：處理JSON數(shù)據(jù)的數(shù)據(jù)的aeson庫、漂亮打印的庫、漂亮打印的generic-pretty庫，類型的序列化。庫，類型的序列化。interface Show String show (T a);interface Eq boolean eq(T a);interface ShowEq extends Eq, Showclass Person implements Eq, ShowString n

15、ame ; int age;Person(String name, int age) = name; this.age = age;public boolean eq(Person a) return .equals() & this.age = a.age;public String show() return + “ ” + this.age;foo : (Show a, Eq a) = a - a - (Bool, String)類型系統(tǒng)與Java的不同1、Java中沒有中沒有“高階泛型高階泛型” 高階高階Kin

16、dclass MkT m ; new Mk()new Mk()2、沒有、沒有“多態(tài)泛型多態(tài)泛型” Kind多態(tài)多態(tài)類型的Kind類型的類型為類型的類型為kind，類型把值分類，類型把值分類，class給類型賦予了屬性，給類型賦予了屬性，kind把類把類型分類。型分類。*代表一個(gè)實(shí)體的代表一個(gè)實(shí)體的kind如：如：3 : Int , Int : *Just 3 : Maybe Int,Maybe : * - *, Maybe Int : *- 只有只有kind為為*的類型下面才有值的類型下面才有值- 沒有一個(gè)值的類型是沒有一個(gè)值的類型是Maybe，只有，只有Maybe Int或或Maybe Ch

17、ar等等Either : * - * - * - 同理也沒有一個(gè)值的類型是同理也沒有一個(gè)值的類型是Either(,) : * - * - *- 元組類型的構(gòu)造器元組類型的構(gòu)造器- RNodea ( (RoseTree a):kind * - *data BinTree a = BLeaf a| BNode a (Pair (BinTree a)- (a,a)data Pair a = MkPair a a:kind Pair* - *高階Kinddata RoseTree a = RLeaf a| RNode a RoseTree a高階Kinddata Tree k a = Leaf a|

18、Node a (k (Tree k a)type RoseTree a = Tree atype BinTree a = Tree Pair atype AnnTree a = Tree AnnPair adata Pair a = MkPair a adata AnnPair a = AnnPair String a a:kind Tree(* - *) - * - *Kind多態(tài)Typeableclass Typeable a where- a : *typeOf : a - Stringinstance Typeable Int where - Int : *typeOf _ = “Int”Maybe : * - *instance Typeable Maybe where - ?solution:class Typeable2 t wheretypeOf2 : t a - Stringclass Typeable3 t wheretypeOf3 : t a b - String- 顯然這個(gè)方案不好！顯然這個(gè)方案不好！Kind多態(tài)Typeableclas