1.6 簡單資料型態

藉由一些例子，我們已經看過 Haskell 的一些數值型別：Int, Float 等等。 在本節中我們將簡短介紹我們將用到的一些其他型別。

1.6.1 布林值

布林值 (Boolean)常用於程式中表達真和假。 在 Haskell 中，我們可假想有這樣的一個型別定義：

data Bool = False | True 

其中，data 是 Haskell 宣告新資料型別的保留字。 上述定義可用口語描述成「定義一個稱作 Bool 的新資料型別， 有兩個可能的值，分別為 False 和 True.」 False 和 True 是型別 Bool 的唯二兩個建構元 --- 任何型別為 Bool 的值，如果有正規式，必定是它們兩者之一。 在 Haskell 之中，建構元必須以大寫英文字母或冒號(:)開頭。

樣式配對   有了資料，我們來看看怎麼定義該型別上的函數。以布林值為輸入的函數中， 最簡單又常用的可能是 not:

not :: Bool -> Bool
not False  = True
not True   = False 

這和我們的的直覺理解一致：not False 是 True, not True 是 False. 我們看到這個定義寫成兩行（正式說來是兩個「子句」），\emph{每一個子句分別對應到 Bool 的一個可能的值}。 以下則是邏輯上的「且」和「或」（分別寫作(⋀)與(⋁)）的定義： (註10) 邏輯「且」又稱作合取(conjunction)；邏輯「或」又稱作析取(disjunction). 在 Haskell 中，「且」與「或」需分別寫成 $(\mathtt{\&\&})$ 和 $(\mathtt{||||})$。本書中採用數學與邏輯領域較常使用的 (⋀)與(⋁).

(⋀), (||) :: Bool -> Bool -> Bool
False  ⋀ y  = False
True   ⋀ y  = y 

False  || y  = y
True   || y  = True 

運算子(⋀)與(⋁)的定義同樣是各兩個子句，每個子句分別考慮其第一個參數的值。 以 x ⋀ y 為例：如果 x 是 False, 不論 y 的值為何，x ⋀ y 都是 False； 如果 x 是 True, x & y 的值和 y 相同。(⋁) 的情況類似。

leapyear :: Int -> Bool
leapyear y =  (y `mod` 4 == 0) ⋀
               (y `mod` 100 /= 0 || y `mod` 400 == 0) 

我們來算算看 leapyear 2016。依照定義展開為

  (2016 `mod` 4 == 0) ⋀ (2016 `mod` 100 /= 0 || 2016 `mod` 400 == 0) 

接下來該怎麼做呢？函數 (⋀) 的定義有兩個子句，我們得知道 2016 `mod` 4 == 0 的值才能得知該歸約成哪個。因此只好先算 2016 `mod` 4 == 0，得到 True:

  True ⋀ (2016 `mod` 100 /= 0 || 2016 `mod` 400 == 0) 

然後依照(⋀) 的定義歸約為 2016 `mod` 100 /= 0 ⋁ 2016 `mod` 400 == 0. 接下來也依此類推。

我們發現這是第1.1 節中所提及的被迫求值的例子：我們得先把參數算出，才知道接下來如何走。 函數 not, (⋀), (⋁) 定義成許多個子句，每個都分析其參數的可能外觀，據此決定該怎麼走。這種定義方式稱作樣式配對 (pattern matching)：等號左手邊的 False, True 等等在此是樣式(pattern)。使用這些函數時，例如 x ⋀ y 中， x 得先被算到可以和這些樣式配對上的程度，才能決定接下來的計算如何進行。

樣式配對也可用在不止一個參數上。例如，以下的運算元 (==) 判斷兩個布林值是否相等。

(==) :: Bool -> Bool -> Bool
False  == False  = True
False  == True   = False
True   == False  = False
True   == True   = True 

讀者可能注意到我們用了同一個符號 (==) 來表示整數與布林值的相等測試。 請讀者暫且接受，相信 Haskell 有某些方式可得知任一個算式中的 (==) 到底是什麼型別的相等。詳情 \todo{where?}

Haskell 中另有一個專用來做樣式配對的 case 算式。例如，(⋀) 也可寫成如下的形式：

(⋀) :: Bool -> Bool
x ⋀ y =  case x of
            False  -> False
            True   -> y 

由於 case 是算式，如同 let 一樣可出現在其他算式中，也可巢狀出現。

x == y = (x ⋀ y) || (not x ⋀ not y) 

1.6.2 字元

我們可把「字元」這個型別想成一個很長的 data 宣告：

data Char = 'a' | 'b' | ... | 'z' | 'A' | 'B' ....

其中包括所有字母、符號、空白... 目前的 Haskell 甚至有處理 Unicode 字元的能力。 但無論如何，Char 之中的字元數目是有限的。我們可用樣式配對定義字元上的函數。 注意：字元以單引號括起來。

我們也可假設字元是有順序的，每個字元對應到一個內碼。 關於 Char 的常用函數中，ord 將字元的內碼找出，chr 則將內碼轉為字元：

ord  :: Char -> Int 
chr  :: Int -> Char 

isUpper :: Char -> Bool
isUpper c = let x = ord c in ord 'A' <= x ⋀ x <= ord 'Z' 

toLower :: Char -> Char
toLower c  | isUpper c  = chr (ord c - ord 'A' + ord 'a')
           | otherwise  = c 

1.6.3 序對

數學上，將兩個值（如 3 和 'a') 放在一起，就成了一個有序對(ordered pair)，可寫成(3,'a')。 之所以稱作「有序」對，因為其中兩個元素的順序是不可忽略的 --- (3,'a') 與 ('a',3) 是不同的有序對。 另一個常見譯名是「數對」。由於我們處理的不只是數字，本書將之簡稱為「序對」。

給兩個集合 A 和 B, 從 A 之中任取一元素 x，從 B 之中也任取一元素 y， 兩者的序對 (x,y) 形成的集合稱作 A 和 B 的笛卡兒積(Cartesian product)，寫成 A × B:

   A × B = {(x,y) | x ∈ A, y ∈ B} 

Haskell 之中也有類似的構造。給定型別 a 與 b, 它們的序對的型別是 (a × b). (註11) 然而，由於「程式可能不終止」這個因素作怪，a × b 的元素並不僅是 a 與 b （如果視做集合）的笛卡兒積。詳見 \todo{where?} 我們可以想像 Haskell 有這麼一個型別定義：

data (a × b) = (a,b) 

以口語說的話，(a × b) 是一個新型別，而具有此型別的值若有範式，必定是 (x,y) 的形式，其中 x 的型別是 a, y 的型別是 b. (註12) 其實這個定義並不符合 Haskell 的語法，因此只是方便理解的想像。另，型別 (a × b) 在 Haskell 中寫成 (a,b). 我的經驗中，讓型別與值的語法太接近，反易造成困惑。 序對的建構元寫成(,)，型別為 a -> b -> (a × b). 例如 (,) 4 'b' = (4,'b').

兩個常用的函數 fst 與 snd 分別取出序對中的第一個和第二個元素：

fst :: (a × b) -> a
fst (x,y) = x 

snd :: (a × b) -> b
snd (x,y) = y 

函數 fst 與 snd 的定義方式也是樣式配對：輸入值必須先計算成 (x,y) 的形式。

swap :: (a × b) -> (b × a)
swap (x,y) = (y,x) 

序對也可以巢狀構成。例如 ((True,3), 'c') 是一個型別為 ((Bool × Int) × Char) 的序對，而 snd (fst ((True,3), 'c')) = 3. 在 Haskell 之中，((a × b) × c) 與 (a × (b × c)) 被視為不同的型別，但他們是同構的 --- 我們可定義一對函數在這兩個型別之間作轉換：

assocr :: ((a × b) × c) -> (a × (b × c))
assocr ((x,y),z) = (x,(y,z)) 

assocl :: (a × (b × c)) -> ((a × b) × c)
assocl (x,(y,z)) = ((x,y),z) 

並且滿足 assocr . assocl = id, 和 assocl . assocr = id.

assocl  p = ...
assocr  p = ...

from . to = id 
to . from = id 

另外可一提的是，Haskell 允許我們在 $\lambda$ 算式中做樣式配對。例如 fst 的另一種寫法是：

fst = \(x,y) -> x 

Haskell 另有提供更多個元素形成的有序組，例如 (True, 3, 'c') 是一個型別為 (Bool × Int × Char) 的值。但本書暫時不使用他們。

分裂與積   在我們將介紹的程式設計風格中，以下兩個產生序對的運算子相當好用。 第一個運算子利用兩個函數產生一個序對：

fork :: (a -> b) -> (a -> c) -> a -> (b × c)
(fork f g) x = (f x, g x) 

給定兩個函數 f :: a -> b 和 g :: a -> c, fork f g :: a -> (b × c) 是一個新函數，將 f 和 g 的結果 收集在一個序對中。 我們借用範疇論的詞彙，將此稱作分裂(split) --- fork f g 可讀成「f 與 g 的分裂」。

如果我們已經有了一個序對，我們可用 (f *** g) 算出一個新序對：

(***) :: (a -> b) -> (c -> d) -> (a × c) -> (b × d)
(f *** g) (x,y) = (f x, g x) 

函數(f *** g) 將 f 和 g 分別作用在序對 (x,y) 的兩個元素上。 這個操作稱作「f 和 g 的乘績(product)」，同樣是借用範疇論的詞彙。

關於分裂與乘積，有兩條重要的性質，將會在之後用到：

目前 Haskell 的標準階層函式庫將分裂與乘積收錄在 \texttt{Control.Arrow} 中， fork f g 寫作：\texttt{f \&\&\& g}, (f *** g) 則寫作 \texttt{f *** g}.

Currying 與 Uncurrying   如前所述，Haskell 的每個函數都只拿一個參數。拿多個參數的函數可以 傳回函數的函數來模擬，稱作 currying. 有了序對之後，另一種模擬多參數的方式是把參數都包到一個序對中。 例如，型別為 (a × b) -> c) 的函數可視為拿了兩個型別為 a 與 b 的參數。

函數 curry 與 uncurry 幫助我們在這兩種表示法之間轉換 --- curry 將拿序對的函數轉換成 curried 函數， uncurry 則讓 curried 函數改拿序對當作參數：

curry :: ((a × b) -> c) -> (a -> b -> c)
curry f x y = f (x,y) 

uncurry :: (a -> b -> c) -> ((a × b) -> c)
uncurry f (x,y) = f x y 

例：如果(==) 的型別為 Int -> Int -> Bool, uncurry (==) 的型別為 (Int × Int) -> Bool。 後者檢查一個序對中的兩個值是否相等（例：uncurry (==) (3,3) = True）。

     curry . uncurry = id
<=>    {- 外延相等及 id 之定義 -}
     (∀ f : curry (uncurry f) = f)
<=>    {- 外延相等 -}
     (∀ f x y : curry (uncurry f) x y = f x y) 

   curry (uncurry f) x y
=   {- curry 之定義 -}
   uncurry f (x,y)
=   {- uncurry 之定義 -}
   f x y  

map (uncurry ($)) [((1+), 3), (square, 4), (smaller 5, 3)]