Algebraic Data Types 入門

在前面的章節(jié)中，我們談了一些 Haskell 內(nèi)建的型別和 Typeclass。而在本章中，我們將學(xué)習(xí)構(gòu)造型別和 Typeclass 的方法。

我們已經(jīng)見識過許多型別，如 Bool、Int、Char、Maybe 等等，不過在 Haskell 中該如何構(gòu)造自己的型別呢？好問題，一種方法是使用 data 關(guān)鍵字。首先我們來看看 Bool 在標(biāo)準(zhǔn)函式庫中的定義：

data Bool = False | True

data 表示我們要定義一個新的型別。= 的左端標(biāo)明型別的名稱即 Bool，= 的右端就是值構(gòu)造子 (Value Constructor)，它們明確了該型別可能的值。| 讀作"或"，所以可以這樣閱讀該聲明：Bool 型別的值可以是 True 或 False。型別名和值構(gòu)造子的首字母必大寫。

相似，我們可以假想 Int 型別的聲明：

data Int = -2147483648 | -2147483647 | ... | -1 | 0 | 1 | 2 | ... | 2147483647

http://wiki.jikexueyuan.com/project/haskell-guide/images/caveman.png" alt="" />

頭尾兩個值構(gòu)造子分別表示了 Int 型別的最小值和最大值，注意到真正的型別宣告不是長這個樣子的，這樣寫只是為了便于理解。我們用省略號表示中間省略的一大段數(shù)字。

我們想想 Haskell 中圖形的表示方法。表示圓可以用一個 Tuple，如 (43.1,55.0,10.4)，前兩項表示圓心的位置，末項表示半徑。聽著不錯，不過三維向量或其它什么東西也可能是這種形式！更好的方法就是自己構(gòu)造一個表示圖形的型別。假定圖形可以是圓 (Circle) 或長方形 (Rectangle)：

data Shape = Circle Float Float Float | Rectangle Float Float Float Float

這是啥，想想？Circle 的值構(gòu)造子有三個項，都是 Float?？梢娢覀冊诙x值構(gòu)造子時，可以在后面跟幾個型別表示它包含值的型別。在這里，前兩項表示圓心的坐標(biāo)，尾項表示半徑。Rectangle 的值構(gòu)造子取四個 Float 項，前兩項表示其左上角的坐標(biāo)，后兩項表示右下角的坐標(biāo)。

談到「項」 (field)，其實(shí)應(yīng)為「參數(shù)」 (parameters)。值構(gòu)造子的本質(zhì)是個函數(shù)，可以返回一個型別的值。我們看下這兩個值構(gòu)造子的型別聲明：

ghci> :t Circle
Circle :: Float -> Float -> Float -> Shape
ghci> :t Rectangle
Rectangle :: Float -> Float -> Float -> Float -> Shape

Cool，這么說值構(gòu)造子就跟普通函數(shù)并無二致啰，誰想得到？我們寫個函數(shù)計算圖形面積：

surface :: Shape -> Float
surface (Circle _ _ r) = pi * r ^ 2
surface (Rectangle x1 y1 x2 y2) = (abs $ x2 - x1) * (abs $ y2 - y1)

值得一提的是，它的型別聲明表示了該函數(shù)取一個 Shape 值并返回一個 Float 值。寫 Circle -> Float 是不可以的，因?yàn)?Circle 并非型別，真正的型別應(yīng)該是 Shape。這與不能寫True->False 的道理是一樣的。再就是，我們使用的模式匹配針對的都是值構(gòu)造子。之前我們匹配過 []、False 或 5，它們都是不包含參數(shù)的值構(gòu)造子。

我們只關(guān)心圓的半徑，因此不需理會表示坐標(biāo)的前兩項：

ghci> surface $ Circle 10 20 10
314.15927
ghci> surface $ Rectangle 0 0 100 100
10000.0

Yay，it works！不過我們?nèi)魢L試輸出 Circle 10 20 到控制臺，就會得到一個錯誤。這是因?yàn)?Haskell 還不知道該型別的字元串表示方法。想想，當(dāng)我們往控制臺輸出值的時候，Haskell 會先呼叫 show 函數(shù)得到這個值的字元串表示才會輸出。因此要讓我們的 Shape 型別成為 Show 型別類的成員。可以這樣修改：

data Shape = Circle Float Float Float | Rectangle Float Float Float Float deriving (Show)

先不去深究 deriving（派生），可以先這樣理解：若在 data 聲明的后面加上 deriving (Show)，那 Haskell 就會自動將該型別至于 Show 型別類之中。好了，由于值構(gòu)造子是個函數(shù)，因此我們可以拿它交給 map，拿它不全呼叫，以及普通函數(shù)能做的一切。

ghci> Circle 10 20 5
Circle 10.0 20.0 5.0
ghci> Rectangle 50 230 60 90
Rectangle 50.0 230.0 60.0 90.0

我們?nèi)粢∫唤M不同半徑的同心圓，可以這樣：

ghci> map (Circle 10 20) [4,5,6,6]
[Circle 10.0 20.0 4.0,Circle 10.0 20.0 5.0,Circle 10.0 20.0 6.0,Circle 10.0 20.0 6.0]

我們的型別還可以更好。增加加一個表示二維空間中點(diǎn)的型別，可以讓我們的 Shape 更加容易理解：

data Point = Point Float Float deriving (Show)
data Shape = Circle Point Float | Rectangle Point Point deriving (Show)

注意下 Point 的定義，它的型別與值構(gòu)造子用了相同的名字。沒啥特殊含義，實(shí)際上，在一個型別含有唯一值構(gòu)造子時這種重名是很常見的。好的，如今我們的 Circle 含有兩個項，一個是 Point 型別，一個是 Float 型別，好作區(qū)分。Rectangle 也是同樣，我們得修改 surface 函數(shù)以適應(yīng)型別定義的變動。

surface :: Shape -> Float
surface (Circle _ r) = pi * r ^ 2
surface (Rectangle (Point x1 y1) (Point x2 y2)) = (abs $ x2 - x1) * (abs $ y2 - y1)

唯一需要修改的地方就是模式。在 Circle 的模式中，我們無視了整個 Point。而在 Rectangle 的模式中，我們用了一個嵌套的模式來取得 Point 中的項。若出于某原因而需要整個 Point，那么直接匹配就是了。

ghci> surface (Rectangle (Point 0 0) (Point 100 100))
10000.0
ghci> surface (Circle (Point 0 0) 24)
1809.5574

表示移動一個圖形的函數(shù)該怎么寫？它應(yīng)當(dāng)取一個 Shape 和表示位移的兩個數(shù)，返回一個位于新位置的圖形。

nudge :: Shape -> Float -> Float -> Shape
nudge (Circle (Point x y) r) a b = Circle (Point (x+a) (y+b)) r
nudge (Rectangle (Point x1 y1) (Point x2 y2)) a b = Rectangle (Point (x1+a) (y1+b)) (Point (x2+a) (y2+b))

簡潔明了。我們再給這一 Shape 的點(diǎn)加上位移的量。

ghci> nudge (Circle (Point 34 34) 10) 5 10
Circle (Point 39.0 44.0) 10.0

如果不想直接處理 Point，我們可以搞個輔助函數(shù) (auxilliary function)，初始從原點(diǎn)創(chuàng)建圖形，再移動它們。

baseCircle :: Float -> Shape
baseCircle r = Circle (Point 0 0) r

baseRect :: Float -> Float -> Shape
baseRect width height = Rectangle (Point 0 0) (Point width height)

ghci> nudge (baseRect 40 100) 60 23
Rectangle (Point 60.0 23.0) (Point 100.0 123.0)

毫無疑問，你可以把你的數(shù)據(jù)型別導(dǎo)出到模組中。只要把你的型別與要導(dǎo)出的函數(shù)寫到一起就是了。再在后面跟個括號，列出要導(dǎo)出的值構(gòu)造子，用逗號隔開。如要導(dǎo)出所有的值構(gòu)造子，那就寫個..。

若要將這里定義的所有函數(shù)和型別都導(dǎo)出到一個模組中，可以這樣：

module Shapes
( Point(..)
, Shape(..)
, surface
, nudge
, baseCircle
, baseRect
) where

一個 Shape (..)，我們就導(dǎo)出了 Shape 的所有值構(gòu)造子。這一來無論誰導(dǎo)入我們的模組，都可以用 Rectangle 和 Circle 值構(gòu)造子來構(gòu)造 Shape 了。這與寫 Shape(Rectangle,Circle) 等價。

我們可以選擇不導(dǎo)出任何 Shape 的值構(gòu)造子，這一來使用我們模組的人就只能用輔助函數(shù) baseCircle 和 baseRect 來得到 Shape 了。Data.Map 就是這一套，沒有 Map.Map [(1,2),(3,4)]，因?yàn)樗鼪]有導(dǎo)出任何一個值構(gòu)造子。但你可以用，像 Map.fromList 這樣的輔助函數(shù)得到 map。應(yīng)該記住，值構(gòu)造子只是函數(shù)而已，如果不導(dǎo)出它們，就拒絕了使用我們模組的人呼叫它們。但可以使用其他返回該型別的函數(shù)，來取得這一型別的值。

不導(dǎo)出數(shù)據(jù)型別的值構(gòu)造子隱藏了他們的內(nèi)部實(shí)現(xiàn)，令型別的抽象度更高。同時，我們模組的使用者也就無法使用該值構(gòu)造子進(jìn)行模式匹配了。

Record Syntax

OK，我們需要一個數(shù)據(jù)型別來描述一個人，得包含他的姓、名、年齡、身高、體重、電話號碼以及最愛的冰激淋。我不知你的想法，不過我覺得要了解一個人，這些資料就夠了。就這樣，實(shí)現(xiàn)出來！

data Person = Person String String Int Float String String deriving (Show)

O~Kay，第一項是名，第二項是姓，第三項是年齡，等等。我們造一個人：

ghci> let guy = Person "Buddy" "Finklestein" 43 184.2 "526-2928" "Chocolate"
ghci> guy
Person "Buddy" "Finklestein" 43 184.2 "526-2928" "Chocolate"

貌似很酷，就是難讀了點(diǎn)兒。弄個函數(shù)得人的某項資料又該如何？如姓的函數(shù)，名的函數(shù)，等等。好吧，我們只能這樣：

firstName :: Person -> String
firstName (Person firstname _ _ _ _ _) = firstname

lastName :: Person -> String
lastName (Person _ lastname _ _ _ _) = lastname

age :: Person -> Int
age (Person _ _ age _ _ _) = age

height :: Person -> Float
height (Person _ _ _ height _ _) = height

phoneNumber :: Person -> String
phoneNumber (Person _ _ _ _ number _) = number

flavor :: Person -> String
flavor (Person _ _ _ _ _ flavor) = flavor

唔，我可不愿寫這樣的程式碼！雖然 it works，但也太無聊了哇。

ghci> let guy = Person "Buddy" "Finklestein" 43 184.2 "526-2928" "Chocolate"
ghci> firstName guy
"Buddy"
ghci> height guy
184.2
ghci> flavor guy
"Chocolate"

你可能會說，一定有更好的方法！呃，抱歉，沒有。

開個玩笑，其實(shí)有的，哈哈哈～Haskell 的發(fā)明者都是天才，早就料到了此類情形。他們引入了一個特殊的型別，也就是剛才提到的更好的方法 -- Record Syntax。

data Person = Person { firstName :: String
                     , lastName :: String
                     , age :: Int
                     , height :: Float
                     , phoneNumber :: String
                     , flavor :: String
                     } deriving (Show)

與原先讓那些項一個挨一個的空格隔開不同，這里用了花括號 {}。先寫出項的名字，如 firstName，后跟兩個冒號(也叫 Paamayim Nekudotayim，哈哈~(譯者不知道什么意思~囧))，標(biāo)明其型別，返回的數(shù)據(jù)型別仍與以前相同。這樣的好處就是，可以用函數(shù)從中直接按項取值。通過 Record Syntax，Haskell 就自動生成了這些函數(shù)：firstName, lastName, age, height, phoneNumber 和 flavor。

ghci> :t flavor
flavor :: Person -> String
ghci> :t firstName
firstName :: Person -> String

還有個好處，就是若派生 (deriving) 到 Show 型別類，它的顯示是不同的。假如我們有個型別表示一輛車，要包含生產(chǎn)商、型號以及出場年份：

data Car = Car String String Int deriving (Show)

ghci> Car "Ford" "Mustang" 1967
Car "Ford" "Mustang" 1967

若用 Record Syntax，就可以得到像這樣的新車：

data Car = Car {company :: String, model :: String, year :: Int} deriving (Show)

ghci> Car {company="Ford", model="Mustang", year=1967}
Car {company = "Ford", model = "Mustang", year = 1967}

這一來在造車時我們就不必關(guān)心各項的順序了。

表示三維向量之類簡單數(shù)據(jù)，Vector = Vector Int Int Int 就足夠明白了。但一個值構(gòu)造子中若含有很多個項且不易區(qū)分，如一個人或者一輛車啥的，就應(yīng)該使用 Record Syntax。

Type parameters

值構(gòu)造子可以取幾個參數(shù)產(chǎn)生一個新值，如 Car 的構(gòu)造子是取三個參數(shù)返回一個 Car。與之相似，型別構(gòu)造子可以取型別作參數(shù)，產(chǎn)生新的型別。這咋一聽貌似有點(diǎn)深奧，不過實(shí)際上并不復(fù)雜。如果你對 C++ 的模板有了解，就會看到很多相似的地方。我們看一個熟悉的型別，好對型別參數(shù)有個大致印象：

data Maybe a = Nothing | Just a

http://wiki.jikexueyuan.com/project/haskell-guide/images/yeti.png" alt="" />

這里的a就是個型別參數(shù)。也正因?yàn)橛辛怂?code>Maybe 就成為了一個型別構(gòu)造子。在它的值不是 Nothing 時，它的型別構(gòu)造子可以搞出 Maybe Int，Maybe String 等等諸多型別。但只一個 Maybe 是不行的，因?yàn)樗皇切蛣e，而是型別構(gòu)造子。要成為真正的型別，必須得把它需要的型別參數(shù)全部填滿。

所以，如果拿 Char 作參數(shù)交給 Maybe，就可以得到一個 Maybe Char 的型別。如，Just 'a' 的型別就是 Maybe Char 。

你可能并未察覺，在遇見 Maybe 之前我們早就接觸到型別參數(shù)了。它便是 List 型別。這里面有點(diǎn)語法糖，List 型別實(shí)際上就是取一個參數(shù)來生成一個特定型別，這型別可以是 [Int]，[Char] 也可以是 [String]，但不會跟在 [] 的后面。

把玩一下 Maybe！

ghci> Just "Haha"
Just "Haha"
ghci> Just 84
Just 84
ghci> :t Just "Haha"
Just "Haha" :: Maybe [Char]
ghci> :t Just 84
Just 84 :: (Num t) => Maybe t
ghci> :t Nothing
Nothing :: Maybe a
ghci> Just 10 :: Maybe Double
Just 10.0

型別參數(shù)很實(shí)用。有了它，我們就可以按照我們的需要構(gòu)造出不同的型別。若執(zhí)行 :t Just "Haha"，型別推導(dǎo)引擎就會認(rèn)出它是個 Maybe [Char]，由于 Just a 里的 a 是個字元串，那么 Maybe a 里的 a 一定也是個字元串。

http://wiki.jikexueyuan.com/project/haskell-guide/images/meekrat.png" alt="" />

注意下，Nothing 的型別為 Maybe a。它是多態(tài)的，若有函數(shù)取 Maybe Int 型別的參數(shù)，就一概可以傳給它一個 Nothing，因?yàn)?Nothing 中不包含任何值。Maybe a 型別可以有 Maybe Int 的行為，正如 5 可以是 Int 也可以是 Double。與之相似，空 List 的型別是 [a]，可以與一切 List 打交道。因此，我們可以 [1,2,3]++[]，也可以 ["ha","ha,","ha"]++[]。

型別參數(shù)有很多好處，但前提是用對了地方才行。一般都是不關(guān)心型別里面的內(nèi)容，如 Maybe a。一個型別的行為若有點(diǎn)像是容器，那么使用型別參數(shù)會是個不錯的選擇。我們完全可以把我們的Car型別從

data Car = Car { company :: String
                 , model :: String
                 , year :: Int
                 } deriving (Show)

改成：

data Car a b c = Car { company :: a
                       , model :: b
                       , year :: c
                        } deriving (Show)

但是，這樣我們又得到了什么好處？回答很可能是，一無所得。因?yàn)槲覀冎欢x了處理 Car String String Int 型別的函數(shù)，像以前，我們還可以弄個簡單函數(shù)來描述車的屬性。

tellCar :: Car -> String
tellCar (Car {company = c, model = m, year = y}) = "This " ++ c ++ " " ++ m ++ " was made in " ++ show y

ghci> let stang = Car {company="Ford", model="Mustang", year=1967}
ghci> tellCar stang
"This Ford Mustang was made in 1967"

可愛的小函數(shù)！它的型別聲明得很漂亮，而且工作良好。好，如果改成 Car a b c 又會怎樣？

tellCar :: (Show a) => Car String String a -> String
tellCar (Car {company = c, model = m, year = y}) = "This " ++ c ++ " " ++ m ++ " was made in " ++ show y

我們只能強(qiáng)制性地給這個函數(shù)安一個 (Show a) => Car String String a 的型別約束?？吹贸鰜恚@要繁復(fù)得多。而唯一的好處貌似就是，我們可以使用 Show 型別類的 instance 來作 a 的型別。

ghci> tellCar (Car "Ford" "Mustang" 1967)
"This Ford Mustang was made in 1967"
ghci> tellCar (Car "Ford" "Mustang" "nineteen sixty seven")
"This Ford Mustang was made in \"nineteen sixty seven\""
ghci> :t Car "Ford" "Mustang" 1967
Car "Ford" "Mustang" 1967 :: (Num t) => Car [Char] [Char] t
ghci> :t Car "Ford" "Mustang" "nineteen sixty seven"
Car "Ford" "Mustang" "nineteen sixty seven" :: Car [Char] [Char] [Char]

其實(shí)在現(xiàn)實(shí)生活中，使用 Car String String Int 在大多數(shù)情況下已經(jīng)滿夠了。所以給 Car 型別加型別參數(shù)貌似并沒有什么必要。通常我們都是都是在一個型別中包含的型別并不影響它的行為時才引入型別參數(shù)。一組什么東西組成的 List 就是一個 List，它不關(guān)心里面東西的型別是啥，然而總是工作良好。若取一組數(shù)字的和，我們可以在后面的函數(shù)體中明確是一組數(shù)字的 List。Maybe 與之相似，它表示可以有什么東西可以沒有，而不必關(guān)心這東西是啥。

我們之前還遇見過一個型別參數(shù)的應(yīng)用，就是 Data.Map 中的 Map k v。 k 表示 Map 中鍵的型別，v 表示值的型別。這是個好例子，Map 中型別參數(shù)的使用允許我們能夠用一個型別索引另一個型別，只要鍵的型別在 Ord 型別類就行。如果叫我們自己定義一個 Map 型別，可以在 data 聲明中加上一個型別類的約束。

data (Ord k) => Map k v = ...

然而 Haskell 中有一個嚴(yán)格的約定，那就是永遠(yuǎn)不要在 data 聲明中添加型別約束。為啥？嗯，因?yàn)檫@樣沒好處，反而得寫更多不必要的型別約束。Map k v 要是有 Ord k 的約束，那就相當(dāng)于假定每個 Map 的相關(guān)函數(shù)都認(rèn)為 k 是可排序的。若不給數(shù)據(jù)型別加約束，我們就不必給那些不關(guān)心鍵是否可排序的函數(shù)另加約束了。這類函數(shù)的一個例子就是 toList，它只是把一個 Map 轉(zhuǎn)換為關(guān)聯(lián) List 罷了，型別聲明為 toList :: Map k v -> [(k, v)]。要是加上型別約束，就只能是 toList :: (Ord k) =>Map k a -> [(k,v)]，明顯沒必要嘛。

所以說，永遠(yuǎn)不要在 data 聲明中加型別約束 --- 即便看起來沒問題。免得在函數(shù)聲明中寫出過多無謂的型別約束。

我們實(shí)現(xiàn)個表示三維向量的型別，再給它加幾個處理函數(shù)。我么那就給它個型別參數(shù)，雖然大多數(shù)情況都是數(shù)值型，不過這一來它就支持了多種數(shù)值型別。

data Vector a = Vector a a a deriving (Show)
vplus :: (Num t) => Vector t -> Vector t -> Vector t
(Vector i j k) `vplus` (Vector l m n) = Vector (i+l) (j+m) (k+n)
vectMult :: (Num t) => Vector t -> t -> Vector t
(Vector i j k) `vectMult` m = Vector (i*m) (j*m) (k*m)
scalarMult :: (Num t) => Vector t -> Vector t -> t
(Vector i j k) `scalarMult` (Vector l m n) = i*l + j*m + k*n

vplus 用來相加兩個向量，即將其所有對應(yīng)的項相加。scalarMult 用來求兩個向量的標(biāo)量積，vectMult 求一個向量和一個標(biāo)量的積。這些函數(shù)可以處理 Vector Int，Vector Integer，Vector Float 等等型別，只要 Vector a 里的這個 a 在 Num 型別類中就行。同樣，如果你看下這些函數(shù)的型別聲明就會發(fā)現(xiàn)，它們只能處理相同型別的向量，其中包含的數(shù)字型別必須與另一個向量一致。注意，我們并沒有在 data 聲明中添加 Num 的類約束。反正無論怎么著都是給函數(shù)加約束。

再度重申，型別構(gòu)造子和值構(gòu)造子的區(qū)分是相當(dāng)重要的。在聲明數(shù)據(jù)型別時，等號=左端的那個是型別構(gòu)造子，右端的(中間可能有|分隔)都是值構(gòu)造子。拿 Vector t t t -> Vector t t t -> t 作函數(shù)的型別就會產(chǎn)生一個錯誤，因?yàn)樵谛蛣e聲明中只能寫型別，而 Vector 的型別構(gòu)造子只有個參數(shù)，它的值構(gòu)造子才是有三個。我們就慢慢耍：

ghci> Vector 3 5 8 `vplus` Vector 9 2 8
Vector 12 7 16
ghci> Vector 3 5 8 `vplus` Vector 9 2 8 `vplus` Vector 0 2 3
Vector 12 9 19
ghci> Vector 3 9 7 `vectMult` 10
Vector 30 90 70
ghci> Vector 4 9 5 `scalarMult` Vector 9.0 2.0 4.0
74.0
ghci> Vector 2 9 3 `vectMult` (Vector 4 9 5 `scalarMult` Vector 9 2 4)
Vector 148 666 222

Derived instances

http://wiki.jikexueyuan.com/project/haskell-guide/images/gob.png" alt="" />

在 [types-and-type-classes.html#Typeclasses入門 Typeclass 101] 那一節(jié)里面，我們了解了 Typeclass 的基礎(chǔ)內(nèi)容。里面提到，型別類就是定義了某些行為的介面。例如，Int 型別是 Eq 型別類的一個 instance，Eq 類就定義了判定相等性的行為。Int 值可以判斷相等性，所以 Int 就是 Eq 型別類的成員。它的真正威力體現(xiàn)在作為 Eq 介面的函數(shù)中，即 == 和 /=。只要一個型別是 Eq 型別類的成員，我們就可以使用 == 函數(shù)來處理這一型別。這便是為何 4==4 和 "foo"/="bar" 這樣的表達(dá)式都需要作型別檢查。

我們也曾提到，人們很容易把型別類與 Java，Python，C++ 等語言的類混淆。很多人對此都倍感不解，在原先那些語言中，類就像是藍(lán)圖，我們可以根據(jù)它來創(chuàng)造對象、保存狀態(tài)并執(zhí)行操作。而型別類更像是介面，我們不是靠它構(gòu)造數(shù)據(jù)，而是給既有的數(shù)據(jù)型別描述行為。什么東西若可以判定相等性，我們就可以讓它成為 Eq 型別類的 instance。什么東西若可以比較大小，那就可以讓它成為 Ord 型別類的 instance。

在下一節(jié)，我們將看一下如何手工實(shí)現(xiàn)型別類中定義函數(shù)來構(gòu)造 instance?，F(xiàn)在呢，我們先了解下 Haskell 是如何自動生成這幾個型別類的 instance，Eq, Ord, Enum, Bounded, Show, Read。只要我們在構(gòu)造型別時在后面加個 deriving(派生)關(guān)鍵字，Haskell 就可以自動地給我們的型別加上這些行為。

看這個數(shù)據(jù)型別：

data Person = Person { firstName :: String
                     , lastName :: String
                     , age :: Int
                     }

這描述了一個人。我們先假定世界上沒有重名重姓又同齡的人存在，好，假如有兩個 record，有沒有可能是描述同一個人呢？當(dāng)然可能，我么可以判定姓名年齡的相等性，來判斷它倆是否相等。這一來，讓這個型別成為 Eq 的成員就很靠譜了。直接 derive 這個 instance：

data Person = Person { firstName :: String
                     , lastName :: String
                     , age :: Int
                     } deriving (Eq)

在一個型別 derive 為 Eq 的 instance 后，就可以直接使用 == 或 /= 來判斷它們的相等性了。Haskell 會先看下這兩個值的值構(gòu)造子是否一致(這里只是單值構(gòu)造子)，再用 == 來檢查其中的所有數(shù)據(jù)(必須都是 Eq 的成員)是否一致。在這里只有 String 和 Int，所以是沒有問題的。測試下我們的 Eqinstance：

ghci> let mikeD = Person {firstName = "Michael", lastName = "Diamond", age = 43}
ghci> let adRock = Person {firstName = "Adam", lastName = "Horovitz", age = 41}
ghci> let mca = Person {firstName = "Adam", lastName = "Yauch", age = 44}
ghci> mca == adRock
False
ghci> mikeD == adRock
False
ghci> mikeD == mikeD
True
ghci> mikeD == Person {firstName = "Michael", lastName = "Diamond", age = 43}
True

自然，Person 如今已經(jīng)成為了 Eq 的成員，我們就可以將其應(yīng)用于所有在型別聲明中用到 Eq 類約束的函數(shù)了，如 elem。

ghci> let beastieBoys = [mca, adRock, mikeD]
ghci> mikeD `elem` beastieBoys
True

Show 和 Read 型別類處理可與字元串相互轉(zhuǎn)換的東西。同 Eq 相似，如果一個型別的構(gòu)造子含有參數(shù)，那所有參數(shù)的型別必須都得屬于 Show 或 Read 才能讓該型別成為其 instance。就讓我們的 Person 也成為 Read 和 Show 的一員吧。

data Person = Person { firstName :: String
                     , lastName :: String
                     , age :: Int
                     } deriving (Eq, Show, Read)

然后就可以輸出一個 Person 到控制臺了。

ghci> let mikeD = Person {firstName = "Michael", lastName = "Diamond", age = 43}
ghci> mikeD
Person {firstName = "Michael", lastName = "Diamond", age = 43}
ghci> "mikeD is: " ++ show mikeD
"mikeD is: Person {firstName = \"Michael\", lastName = \"Diamond\", age = 43}"

如果我們還沒讓 Person 型別作為 Show 的成員就嘗試輸出它，Haskell 就會向我們抱怨，說它不知道該怎么把它表示成一個字元串。不過現(xiàn)在既然已經(jīng) derive 成為了 Show 的一個 instance，它就知道了。

Read 幾乎就是與 Show 相對的型別類，show 是將一個值轉(zhuǎn)換成字元串，而 read 則是將一個字元串轉(zhuǎn)成某型別的值。還記得，使用 read 函數(shù)時我們必須得用型別注釋注明想要的型別，否則 Haskell 就不會知道如何轉(zhuǎn)換。

ghci> read "Person {firstName =\"Michael\", lastName =\"Diamond\", age = 43}" :: Person
Person {firstName = "Michael", lastName = "Diamond", age = 43}

如果我們 read 的結(jié)果會在后面用到參與計算，Haskell 就可以推導(dǎo)出是一個 Person 的行為，不加注釋也是可以的。

ghci> read "Person {firstName =\"Michael\", lastName =\"Diamond\", age = 43}" == mikeD
True

也可以 read 帶參數(shù)的型別，但必須填滿所有的參數(shù)。因此 read "Just 't'" :: Maybe a 是不可以的，read "Just 't'" :: Maybe Char 才對。

很容易想象 Ord 型別類 derive instance 的行為。首先，判斷兩個值構(gòu)造子是否一致，如果是，再判斷它們的參數(shù)，前提是它們的參數(shù)都得是 Ord 的 instance。Bool 型別可以有兩種值，False 和 True。為了了解在比較中程序的行為，我們可以這樣想象：

data Bool = False | True deriving (Ord)

由于值構(gòu)造子 False 安排在 True 的前面，我們可以認(rèn)為 True 比 False 大。

ghci> True `compare` False
GT
ghci> True > False
True
ghci> True < False
False

在 Maybe a 數(shù)據(jù)型別中，值構(gòu)造子 Nothing 在 Just 值構(gòu)造子前面，所以一個 Nothing 總要比 Just something 的值小。即便這個 something 是 -100000000 也是如此。

ghci> Nothing < Just 100
True
ghci> Nothing > Just (-49999)
False
ghci> Just 3 `compare` Just 2
GT
ghci> Just 100 > Just 50
True

不過類似 Just (*3) > Just (*2) 之類的程式碼是不可以的。因?yàn)?(*3) 和 (*2) 都是函數(shù)，而函數(shù)不是 Ord 類的成員。

作枚舉，使用數(shù)字型別就能輕易做到。不過使用 Enum 和 Bounded 型別類會更好，看下這個型別：

data Day = Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday

所有的值構(gòu)造子都是 nullary 的(也就是沒有參數(shù))，每個東西都有前置子和后繼子，我們可以讓它成為 Enum 型別類的成員。同樣，每個東西都有可能的最小值和最大值，我們也可以讓它成為 Bounded 型別類的成員。在這里，我們就同時將它搞成其它可 derive型別類的 instance。再看看我們能拿它做啥：

data Day = Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday
           deriving (Eq, Ord, Show, Read, Bounded, Enum)

由于它是 Show 和 Read 型別類的成員，我們可以將這個型別的值與字元串相互轉(zhuǎn)換。

ghci> Wednesday
Wednesday
ghci> show Wednesday
"Wednesday"
ghci> read "Saturday" :: Day
Saturday

由于它是 Eq 與 Ord 的成員，因此我們可以拿 Day 作比較。

ghci> Saturday == Sunday
False
ghci> Saturday == Saturday
True
ghci> Saturday > Friday
True
ghci> Monday `compare` Wednesday
LT

它也是 Bounded 的成員，因此有最早和最晚的一天。

ghci> minBound :: Day
Monday
ghci> maxBound :: Day
Sunday

它也是 Enum 的 instance，可以得到前一天和后一天，并且可以對此使用 List 的區(qū)間。

ghci> succ Monday
Tuesday
ghci> pred Saturday
Friday
ghci> [Thursday .. Sunday]
[Thursday,Friday,Saturday,Sunday]
ghci> [minBound .. maxBound] :: [Day]
[Monday,Tuesday,Wednesday,Thursday,Friday,Saturday,Sunday]

那是相當(dāng)?shù)陌簟?/p>

Type synonyms

在前面我們提到在寫型別名的時候，[Char] 和 String 等價，可以互換。這就是由型別別名實(shí)現(xiàn)的。型別別名實(shí)際上什么也沒做，只是給型別提供了不同的名字，讓我們的程式碼更容易理解。這就是 [Char] 的別名 String 的由來。

type String = [Char]

我們已經(jīng)介紹過了 type 關(guān)鍵字，這個關(guān)鍵字有一定誤導(dǎo)性，它并不是用來創(chuàng)造新類（這是 data 關(guān)鍵字做的事情），而是給一個既有型別提供一個別名。

如果我們隨便搞個函數(shù) toUpperString 或其他什么名字，將一個字元串變成大寫，可以用這樣的型別聲明 toUpperString :: [Char] -> [Char]， 也可以這樣 toUpperString :: String -> String，二者在本質(zhì)上是完全相同的。后者要更易讀些。

在前面 Data.Map 那部分，我們用了一個關(guān)聯(lián) List 來表示 phoneBook，之后才改成的 Map。我們已經(jīng)發(fā)現(xiàn)了，一個關(guān)聯(lián) List 就是一組鍵值對組成的 List。再看下我們 phoneBook 的樣子：

phoneBook :: [(String,String)]
phoneBook =
    [("betty","555-2938")
    ,("bonnie","452-2928")
    ,("patsy","493-2928")
    ,("lucille","205-2928")
    ,("wendy","939-8282")
    ,("penny","853-2492")
    ]

可以看出，phoneBook 的型別就是 [(String,String)]，這表示一個關(guān)聯(lián) List 僅是 String 到 String 的映射關(guān)系。我們就弄個型別別名，好讓它型別聲明中能夠表達(dá)更多資訊。

type PhoneBook = [(String,String)]

現(xiàn)在我們 phoneBook 的型別聲明就可以是 phoneBook :: PhoneBook 了。再給字元串加上別名：

type PhoneNumber = String
type Name = String
type PhoneBook = [(Name,PhoneNumber)]

Haskell 程序員給 String 加別名是為了讓函數(shù)中字元串的表達(dá)方式及用途更加明確。

好的，我們實(shí)現(xiàn)了一個函數(shù)，它可以取一名字和號碼檢查它是否存在于電話本?，F(xiàn)在可以給它加一個相當(dāng)好看明了的型別聲明：

inPhoneBook :: Name -> PhoneNumber -> PhoneBook -> Bool
inPhoneBook name pnumber pbook = (name,pnumber) `elem` pbook

http://wiki.jikexueyuan.com/project/haskell-guide/images/chicken.png" alt="" />

如果不用型別別名，我們函數(shù)的型別聲明就只能是 String -> String -> [(String ,String)] -> Bool 了。在這里使用型別別名是為了讓型別聲明更加易讀，但你也不必拘泥于它。引入型別別名的動機(jī)既非單純表示我們函數(shù)中的既有型別，也不是為了替換掉那些重復(fù)率高的長名字型別(如 [(String,String)])，而是為了讓型別對事物的描述更加明確。

型別別名也是可以有參數(shù)的，如果你想搞個型別來表示關(guān)聯(lián) List，但依然要它保持通用，好讓它可以使用任意型別作 key 和 value，我們可以這樣：

type AssocList k v = [(k,v)]

好的，現(xiàn)在一個從關(guān)聯(lián) List 中按鍵索值的函數(shù)型別可以定義為 (Eq k) => k -> AssocList k v -> Maybe v. AssocList i。AssocList 是個取兩個型別做參數(shù)生成一個具體型別的型別構(gòu)造子，如 Assoc Int String 等等。

*Fronzie 說*：Hey！當(dāng)我提到具體型別，那我就是說它是完全呼叫的，就像 ``Map Int String``。要不就是多態(tài)函數(shù)中的 ``[a]`` 或 ``(Ord a) => Maybe a`` 之類。有時我和孩子們會說 "Maybe 型別"，但我們的意思并不是按字面來，傻瓜都知道 ``Maybe`` 是型別構(gòu)造子嘛。只要用一個明確的型別呼叫 ``Maybe``，如 ``Maybe String`` 可得一個具體型別。你知道，只有具體型別才可以儲存值。

我們可以用不全呼叫來得到新的函數(shù)，同樣也可以使用不全呼叫得到新的型別構(gòu)造子。同函數(shù)一樣，用不全的型別參數(shù)呼叫型別構(gòu)造子就可以得到一個不全呼叫的型別構(gòu)造子，如果我們要一個表示從整數(shù)到某東西間映射關(guān)系的型別，我們可以這樣：

type IntMap v = Map Int v

也可以這樣：

type IntMap = Map Int

無論怎樣，IntMap 的型別構(gòu)造子都是取一個參數(shù)，而它就是這整數(shù)指向的型別。

Oh yeah，如果要你去實(shí)現(xiàn)它，很可能會用個 qualified import 來導(dǎo)入 Data.Map。這時，型別構(gòu)造子前面必須得加上模組名。所以應(yīng)該寫個 type IntMap = Map.Map Int

你得保證真正弄明白了型別構(gòu)造子和值構(gòu)造子的區(qū)別。我們有了個叫 IntMap 或者 AssocList 的別名并不意味著我們可以執(zhí)行類似 AssocList [(1,2),(4,5),(7,9)] 的程式碼，而是可以用不同的名字來表示原先的 List，就像 [(1,2),(4,5),(7,9)] :: AssocList Int Int 讓它里面的型別都是 Int。而像處理普通的 Tuple 構(gòu)成的那種 List 處理它也是可以的。型別別名(型別依然不變)，只可以在 Haskell 的型別部分中使用，像定義新型別或型別聲明或型別注釋中跟在::后面的部分。

另一個很酷的二參型別就是 Either a b 了，它大約是這樣定義的：

data Either a b = Left a | Right b deriving (Eq, Ord, Read, Show)

它有兩個值構(gòu)造子。如果用了 Left，那它內(nèi)容的型別就是 a；用了 Right，那它內(nèi)容的型別就是 b。我們可以用它來將可能是兩種型別的值封裝起來，從里面取值時就同時提供 Left 和 Right 的模式匹配。

ghci> Right 20
Right 20
ghci> Left "w00t"
Left "w00t"
ghci> :t Right 'a'
Right 'a' :: Either a Char
ghci> :t Left True
Left True :: Either Bool b

到現(xiàn)在為止，Maybe 是最常見的表示可能失敗的計算的型別了。但有時 Maybe 也并不是十分的好用，因?yàn)?Nothing 中包含的信息還是太少。要是我們不關(guān)心函數(shù)失敗的原因，它還是不錯的。就像 Data.Map 的 lookup 只有在搜尋的項不在 Map 時才會失敗，對此我們一清二楚。但我們?nèi)粝胫篮瘮?shù)失敗的原因，那還得使用 Either a b，用 a 來表示可能的錯誤的型別，用 b 來表示一個成功運(yùn)算的型別。從現(xiàn)在開始，錯誤一律用 Left 值構(gòu)造子，而結(jié)果一律用 Right。

一個例子：有個學(xué)校提供了不少壁櫥，好給學(xué)生們地方放他們的 Gun'N'Rose 海報。每個壁櫥都有個密碼，哪個學(xué)生想用個壁櫥，就告訴管理員壁櫥的號碼，管理員就會告訴他壁櫥的密碼。但如果這個壁櫥已經(jīng)讓別人用了，管理員就不能告訴他密碼了，得換一個壁櫥。我們就用 Data.Map 的一個 Map 來表示這些壁櫥，把一個號碼映射到一個表示壁櫥占用情況及密碼的 Tuple 里。

import qualified Data.Map as Map

data LockerState = Taken | Free deriving (Show, Eq)

type Code = String

type LockerMap = Map.Map Int (LockerState, Code)

很簡單，我們引入了一個新的型別來表示壁櫥的占用情況。并為壁櫥密碼及按號碼找壁櫥的 Map 分別設(shè)置了一個別名。好，現(xiàn)在我們實(shí)現(xiàn)這個按號碼找壁櫥的函數(shù)，就用 Either String Code 型別表示我們的結(jié)果，因?yàn)?lookup 可能會以兩種原因失敗。櫥子已經(jīng)讓別人用了或者壓根就沒有這個櫥子。如果 lookup 失敗，就用字元串表明失敗的原因。

lockerLookup :: Int -> LockerMap -> Either String Code
lockerLookup lockerNumber map =
    case Map.lookup lockerNumber map of
        Nothing -> Left $ "Locker number " ++ show lockerNumber ++ " doesn't exist!"
        Just (state, code) -> if state /= Taken
                                then Right code
                                else Left $ "Locker " ++ show lockerNumber ++ " is already taken!"

我們在這里個 Map 中執(zhí)行一次普通的 lookup，如果得到一個 Nothing，就返回一個 Left String 的值，告訴他壓根就沒這個號碼的櫥子。如果找到了，就再檢查下，看這櫥子是不是已經(jīng)讓別人用了，如果是，就返回個 Left String 說它已經(jīng)讓別人用了。否則就返回個 Right Code 的值，通過它來告訴學(xué)生壁櫥的密碼。它實(shí)際上就是個 Right String，我們引入了個型別別名讓它這型別聲明更好看。

如下是個 Map 的例子：

lockers :: LockerMap
lockers = Map.fromList
    [(100,(Taken,"ZD39I"))
    ,(101,(Free,"JAH3I"))
    ,(103,(Free,"IQSA9"))
    ,(105,(Free,"QOTSA"))
    ,(109,(Taken,"893JJ"))
    ,(110,(Taken,"99292"))
    ]

現(xiàn)在從里面 lookup 某個櫥子號..

ghci> lockerLookup 101 lockers
Right "JAH3I"
ghci> lockerLookup 100 lockers
Left "Locker 100 is already taken!"
ghci> lockerLookup 102 lockers
Left "Locker number 102 doesn't exist!"
ghci> lockerLookup 110 lockers
Left "Locker 110 is already taken!"
ghci> lockerLookup 105 lockers
Right "QOTSA"

我們完全可以用 Maybe a 來表示它的結(jié)果，但這樣一來我們就對得不到密碼的原因不得而知了。而在這里，我們的新型別可以告訴我們失敗的原因。

Recursive data structures (遞回地定義資料結(jié)構(gòu))

如我們先前看到的，一個 algebraic data type 的構(gòu)造子可以有好幾個 field，其中每個 field 都必須有具體的型態(tài)。有了那個概念，我們能定義一個型態(tài)，其中他的構(gòu)造子的 field 的型態(tài)是他自己。這樣我們可以遞回地定義下去，某個型態(tài)的值便可能包含同樣型態(tài)的值，進(jìn)一步下去他還可以再包含同樣型態(tài)的值。

考慮一下 List: [5]。他其實(shí)是 5:[] 的語法糖。在 : 的左邊是一個普通值，而在右邊是一串 List。只是在這個案例中是空的 List。再考慮 [4,5]。他可以看作 4:(5:[])?？纯吹谝粋€ :，我們看到他也有一個元素在左邊，一串 List 5:[] 在右邊。同樣的道理 3:(4:(5:6:[])) 也是這樣。

我們可以說一個 List 的定義是要碼是空的 List 或是一個元素，后面用 : 接了另一串 List。

我們用 algebraic data type 來實(shí)作我們自己的 List！

data List a = Empty | Cons a (List a) deriving (Show, Read, Eq, Ord)

這讀起來好像我們前一段提及的定義。他要碼是空的 List，或是一個元素跟一串 List 的結(jié)合。如果你被搞混了，看看用 record syntax 定義的可能比較清楚。

data List a = Empty | Cons { listHead :: a, listTail :: List a} deriving (Show, Read, Eq, Ord)

你可能也對這邊的 Cons 構(gòu)造子不太清楚。cons 其實(shí)就是指 :。對 List 而言，: 其實(shí)是一個構(gòu)造子，他接受一個值跟另一串 List 來構(gòu)造一個 List?，F(xiàn)在我們可以使用我們新定義的 List 型態(tài)。換句話說，他有兩個 field，其中一個 field 具有型態(tài) a，另一個有型態(tài) [a]。

ghci> Empty
Empty
ghci> 5 `Cons` Empty
Cons 5 Empty
ghci> 4 `Cons` (5 `Cons` Empty)
Cons 4 (Cons 5 Empty)
ghci> 3 `Cons` (4 `Cons` (5 `Cons` Empty))
Cons 3 (Cons 4 (Cons 5 Empty))

我們用中綴的方式呼叫 Cons 構(gòu)造子，這樣你可以很清楚地看到他就是 :。Empty 代表 []，而 4 `Cons` (5 `Cons` Empty) 就是 4:(5:[])。

我們可以只用特殊字元來定義函數(shù)，這樣他們就會自動具有中綴的性質(zhì)。我們也能同樣的手法套用在構(gòu)造子上，畢竟他們不過是回傳型態(tài)的函數(shù)而已。

infixr 5 :-:
data List a = Empty | a :-: (List a) deriving (Show, Read, Eq, Ord)

首先我們留意新的語法結(jié)構(gòu)：fixity 宣告。當(dāng)我們定義函數(shù)成 operator，我們能同時指定 fixity (但并不是必須的)。fixity 指定了他應(yīng)該是 left-associative 或是 right-associative，還有他的優(yōu)先順序。例如說，* 的 fixity 是 infixl 7 *，而 + 的 fixity 是 infixl 6。代表他們都是 left-associative。(4 * 3 * 2) 等于 ((4 * 3) * 2)。但 * 擁有比 + 更高的優(yōu)先順序。所以 5 * 4 + 3 會是 (5 * 4) + 3。

這樣我們就可以寫成 a :-: (List a) 而不是 Cons a (List a)：

ghci> 3 :-: 4 :-: 5 :-: Empty
(:-:) 3 ((:-:) 4 ((:-:) 5 Empty))
ghci> let a = 3 :-: 4 :-: 5 :-: Empty
ghci> 100 :-: a
(:-:) 100 ((:-:) 3 ((:-:) 4 ((:-:) 5 Empty)))

Haskell 在宣告 deriving Show 的時候，他會仍視構(gòu)造子為前綴函數(shù)，因此必須要用括號括起來。

我們在來寫個函數(shù)來把兩個 List 連起來。一般 ++ 在操作普通 List 的時候是這樣的：

infixr 5  ++
(++) :: [a] -> [a] -> [a]
[]     ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)

我們把他偷過來用在我們的 List 上，把函數(shù)命名成 .++：

infixr 5  .++
(.++) :: List a -> List a -> List a
Empty .++ ys = ys
(x :-: xs) .++ ys = x :-: (xs .++ ys)

來看看他如何運(yùn)作：

ghci> let a = 3 :-: 4 :-: 5 :-: Empty
ghci> let b = 6 :-: 7 :-: Empty
ghci> a .++ b
(:-:) 3 ((:-:) 4 ((:-:) 5 ((:-:) 6 ((:-:) 7 Empty))))

如果我們想要的話，我們可以定義其他操作我們list的函數(shù)。

注意到我們是如何利用 (x :-: xs) 做模式匹配的。他運(yùn)作的原理實(shí)際上就是利用到構(gòu)造子。我們可以利用 :-: 做模式匹配原因就是他是構(gòu)造子，同樣的 : 也是構(gòu)造子所以可以用他做匹配。[] 也是同樣道理。由于模式匹配是用構(gòu)造子來作的，所以我們才能對像 8, 'a' 之類的做模式匹配。他們是數(shù)值與字元的構(gòu)造子。

接下來我們要實(shí)作二元搜尋樹 (binary search tree)。如果你對二元搜尋樹不太清楚，我們來快速地解釋一遍。他的結(jié)構(gòu)是每個節(jié)點(diǎn)指向兩個其他節(jié)點(diǎn)，一個在左邊一個在右邊。在左邊節(jié)點(diǎn)的元素會比這個節(jié)點(diǎn)的元素要小。在右邊的話則比較大。每個節(jié)點(diǎn)最多可以有兩棵子樹。而我們知道譬如說一棵包含 5 的節(jié)點(diǎn)的左子樹，里面所有的元素都會小于 5。而節(jié)點(diǎn)的右子樹里面的元素都會大于 5。如果我們想找找看 8是不是在我們的樹里面，我們就從 5 那個節(jié)點(diǎn)找起，由于 8 比 5 要大，很自然地就會往右搜尋。接著我們走到 7，又由于 8 比 7 要大，所以我們再往右走。我們在三步就找到了我們要的元素。如果這不是棵樹而是 List 的話，那就會需要花到七步才能找到 8。

Data.Set 跟 Data.Map 中的 set 和 Map 都是用樹來實(shí)現(xiàn)的，只是他們是用平衡二元搜尋樹而不是隨意的二元搜尋樹。不過這邊我們就只先寫一棵普通的二元搜尋樹就好了。

這邊我們來定義一棵樹的結(jié)構(gòu)：他不是一棵空的樹就是帶有值并含有兩棵子樹。聽起來非常符合 algebraic data type 的結(jié)構(gòu)！

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)

我們不太想手動來建棵二元搜尋樹，所以我們要來寫一個函數(shù)，他接受一棵樹還有一個元素，把這個元素安插到這棵二元搜尋樹中。當(dāng)拿這個元素跟樹的節(jié)點(diǎn)比較結(jié)果比較小的話，我們就往左走，如果比較大，就往右走。重復(fù)這個動作直到我們走到一棵空的樹。一旦碰到空的樹的話，我們就把元素插入節(jié)點(diǎn)。

在 C 語言中，我們是用修改指標(biāo)的方式來達(dá)成這件事。但在 Haskell 中，我們沒辦法修改我們的樹。所以我們在決定要往左或往右走的時候就做一棵新的子樹，走到最后要安插節(jié)點(diǎn)的時候也是做一棵新的樹。因此我們插入函數(shù)的型態(tài)會是 a -> Tree a -> Tree a。他接受一個元素跟一棵樹，并回傳一棵包含了新元素的新的樹。這看起來很沒效率的樣子，但別擔(dān)心，惰性的特性可以讓我們不用擔(dān)心這個。

來看下列兩個函數(shù)。第一個做了一個單節(jié)點(diǎn)的樹，而第二個插入一個元素到一棵樹中。

singleton :: a -> Tree a
singleton x = Node x EmptyTree EmptyTree

treeInsert :: (Ord a) => a -> Tree a -> Tree a
treeInsert x EmptyTree = singleton x
treeInsert x (Node a left right)
      | x == a = Node x left right
      | x < a  = Node a (tr