Haskell簡介[3]--型別的定義與史考特編碼

Posted on

這是目前庫存的haskell裡面最後一篇文啦><
在本文中，會介紹如何在haskell中定義新的型別，並介紹在Prelude中就包含的各種型別與型別建構子。
接著會簡單解釋這種型別的建構被稱為 ADT。
在文末會提到如何用純的FP來實作這些看似不是很FP的東西。

定義型別

type

type的運作方式類似C++的typedef，語法是type MyInt = Int
在之後的MyInt跟Int就是等價的，所有需要Int當參數的函式都可以傳入Int，反之亦然。

data

data是宣告新型別所用的關鍵字，例如data PairInt = Pair Int Int。
這時就可以用Pair 3 5來建構一個PairInt。
注意型別和建構子的首字母必須大寫，而一般函式的首字母必須小寫。
而利用模式匹配就可以拿到那些欄位的值。例如

1
2
sum' :: PairInt -> Int
sum' (Pair a b) = a + b

記得加上括號。

而對於一個型別也可以定義多於一個建構子。
例如data Node = Leaf | Node Node Node就是一個二元樹的節點。
建構子的名稱是可以跟型別重複的，但是不能跟其他建構子重複。
而建構子也可以傳入新定義的型別，也可以什麼都不傳。
所以在Prelude中，Bool的定義方式就是data Bool = False | True。

常常，定義新型別後，我們會需要定義一堆函式來得到每個欄位的值，例如

1
2
3
4
5
6
7
data Student = Student Int Int Int String String

getGrade (Student g _ _ _ _) = g
getClass (Student _ c _ _ _) = c
getSeatN (Student _ _ s _ _) = s
getID    (Student _ _ _ i _) = i
getName  (Student _ _ _ _ n) = n

而Haskell很貼心的引入了語法糖，使以上的程式碼可以簡化為

1
2
3
4
5
6
7
data Student = Student {
    getGrade :: Int,
    getClass :: Int,
    getSeatN :: Int,
    getID    :: String,
    getName  :: String
}

讀者可以去檢查建構子Student以及其他的函式的型別是不是跟你想像的一樣。

另外，在定義型別時也可以傳入型別當作引數，例如

1
data Pair a = Pair a a

Pair 3 5的型別就會是Num a => Pair a的。這時的Pair是一個型別建構子。而由於他是接受一個型別產生新的型別，他的型別種類(kind)是* -> *。

問題：如果data Foo a b c = Bar a | Foo (b c)，那Foo的種類會是什麼？

deriving

我們定義了新型別時，要怎麼把它加入一個型別類別呢？用的就是關鍵字deriving。有些型別類別有新加入型別的預設定義，因此只要在宣告型別時加入即可。例如
data Node = Leaf | Node Node Node deriving Show
你就可以執行 show $ Node (Node Leaf Leaf) Leaf了。

又例如Eq和Ord都是有預設的型別定義，於是
data Node = Leaf | Node Node Node deriving (Eq, Ord)
就可以讓Node屬於Eq和Ord。
Eq的定義就是最直覺的那個，而Ord則是依照定義建構子的順序由小到大。同樣建構子再依字典序比較每個欄位的值。
因此data Bool = False | True 會使得False < True。

將型別加入一個沒有預設定義的型別類型的方法會在之後提到型別類型的定義時一併說明。

Prelude內建型別

串列

事實上，串列的定義也是用類似的概念達成的。讓我們來看看以下的定義

1
data List a = Nil | Cons a (List a)

可以看出，List是一個種類為* ->　*的型別建構子。
而一個a的List的確是一堆a依序跟一個空串列(Nil)做連接Cons
事實上在Prelude裡的Nil就是[]，Cons就是(:)，而[1,2,3]只是1:(2:(3:[]))的語法糖。

因此在模式匹配時，可以直接用(a:b)匹配到串列的head跟tail。拿上一篇文的take做例子就是

1
2
3
4
take' :: Int -> [a] -> [a]
take' _ [] = []
take' 0  _ = []
take' x (a:b)  = a:(take' (x-1) b)

Maybe

Maybe :: * -> *是一個Prelude包含的一個型別建構子。他的定義如下
data Maybe a = Nothing | Just a
當函式會有例外時，常常會使用Maybe。Just代表函式如預期執行，並回傳那個數值，而Nothing代表函式出了例外。
例如對空串列呼叫head時會直接丟出錯誤，因此我們來試圖實做一個safeHead，將例外包到Maybe中：

1
2
3
safeHead :: [a] -> Maybe a
safeHead [] = Nothing
safeHead (a:_) = Just a

這樣就可以在外面再處理這個例外。

Either

Either :: * -> * -> *是令一個Prelude包含的一個型別建構子。他的定義如下
data Either a b = Left a | Right b
當函式不但有例外，這個例外還需要包含錯誤訊息時就會使用Either。例如

1
2
3
safeHead :: [a] -> Either String a
safeHead [] = Left "the list is empty"
safeHead (a:_) = Right a

代數資料型別(ADT)

先來進行一個小小的數數測驗吧><
請你告訴我每個型別總共有多少個可能的取值

  • ()
  • data Bool = False | True
  • data Numbers = One | Two | Three
  • data Void
  • (Bool, Bool)
  • (Numbers, Bool)
  • data Foo = Foo Bool Numbers
  • data Bar = Bar Bool | BarBar ()

你應該會發現，用|分隔的會讓左右的可能數相加，而共用同一個建構子則會讓兩個可能數相乘。
因此，用|建構出的型別叫做加法型別(sum types)，而用一個多元建構子建構的型別稱作乘法型別(product types)。用這兩者建構的型別就稱為代數資料型別。

更詳細的型別論觀點就等有朝一日我提到這方面的東西再說吧Q (或許沒有這一天Q)。

史考特編碼(Scott encoding)

讀者可能會想問，這些data超interface的，根本只是假藉FP在偷渡一些OOP的東西吧。
讓我們來看看這些型別是如何實做的吧

箱子裡的數字

在試接下來的例子之前，請先在ghci內打上:set -XRank2Types
先來考慮這個型別forall r. (Int -> r) -> r[1]。
只要任給一個需要Int作為參數的函數，他就可以算出這個函數的值。
那他是不是就等價於一個Int？

當我看到一個函數，它走路像Int，游泳像Int，叫聲像Int，我就稱其為Int

所以這個函數事實上擁有一個Int的所有資訊。他儲存著一個Int。

箱子裡的兩個東西

再來考慮這個型別type SPair a b = forall r. (a -> b -> r) -> r。
是不是就等價於一個存著兩個東西的二組了呢？
我們可以來實作fst和snd以及makePair：

1
2
3
4
5
6
7
8
fst' :: SPair a b -> a
fst' f = f (\a b -> a)

snd' :: SPair a b -> b
snd' f = f (\a b -> b)

makePair :: a -> b -> SPair a b
makePair a b = \f -> f a b

我有一個Bool

接著考慮這個型別type SBool = forall r. r -> r -> r。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
false :: SBool
false = \a b -> a

true :: SBool
true = \a b -> b

ifThenElse :: SBool -> r -> r -> r
ifThenElse f = f
-- ifThenElse a b c == if a then b else c

and' :: SBool -> SBool -> SBool
and' a b = ifThenElse a b a

or' :: SBool -> SBool -> SBool
or' a b = ifThenElse a a b

toBool :: SBool -> Bool
toBool a = a False True

讀者會發現只要能做到ifThenElse就可以做到Bool可以做到的所有事情！
而SBool的型別基本上就是ifThenElse。
更仔細看的話ifThenElse事實上就是在做模式匹配；只要能做到模式匹配就是一個Bool！

我有一個Maybe

接著是這個型別type SMaybe a = forall r. r -> (a -> r) -> r。
以及實作

1
2
3
4
5
6
7
8
just :: a -> SMaybe a
just a = \x f -> f a

nothing :: forall a. SMaybe a
nothing = \x f -> x

toMaybe :: Maybe a -> SMaybe a
toMaybe f = f Nothing \a -> Just a

其實SMaybe的型別就是在做模式匹配的型別。
仔細看看Maybe和SMaybe的定義的異同

1
2
data  Maybe a = Nothing    | Just a
type SMaybe a =         r ->     (a -> r) -> r

這種對應關係就是史考特編碼。
問題：你能否寫出Either a b的史考特編碼？
問題：你能否寫出data Data a = This | That | These a | Those a a的史考特編碼？

我有一個List

至於List是遞迴定義的，因此我們的型別也需要被遞迴定義。Haskell的type是不支援遞迴定義的，所以我們必須使用data。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
data SList a = SList (forall r. r -> (a -> SList a -> r) -> r

length' :: SList a -> Int
length' (SList f) = f 0 \_ xs -> 1 + (length' xs)

toList :: SList a -> [a]
toList = undefined

safeHead :: SList a -> SMaybe a
safeHead = undefined

map' :: (a -> b) -> SList a -> SList b
map' = undefined

zip' :: SList a -> SList b -> SList (SPair a b)
zip' = undefined

問題：你可以完成以上的函數嗎？
問題：你能否寫出data Nat = Z | S Nat的史考特編碼？事實上這就是用皮亞諾公理建構的自然數。請問你能否實作出pred succ (+) (*)呢？
問題：你能否寫出data Tree a = Leaf a | Node a Tree Tree的史考特編碼？

事實上除了史考特編碼，還有另外一種邱奇編碼，但筆者就不多提了，有興趣的讀者可以自行參考維基百科。

後記

希望這次比之前的內容有趣多了><
也希望我的說明夠清楚><
第一次遇到FP的想法會覺得卡卡的是很自然的，多想幾遍、多試幾遍腦袋就會越來越靈活喔><

  1. 等等什麼是forall？什麼又是Rank2Types？
    我可能會之後特別開一篇文來解釋，不過就目前而言，前者的意思只是這個函數必須能夠接受任何的Int -> r，不論r的型別是什麼。而後者只是能讓我們這麼寫的語言擴展。 ↩