又一個 Haskell 教程/型別基礎/解答

簡單型別

1. String 或 [Char]
2. 型別錯誤：列表是同質的
3. Num{a} => (a, Char)
4. Int
5. 型別錯誤：無法新增不同型別的值

多型型別

這些型別

1. (a,b) -> b
2. [a] -> a
3. [a] -> Bool
4. [a] -> a
5. [[a]] -> a

函式型別

函式引數

這些型別

1. a -> [a]。此函式接收一個元素並返回只包含該元素的列表。
2. a -> b -> b -> (a,[b])。第二個和第三個引數必須是相同型別，因為它們進入同一個列表。第一個元素可以是任何型別。
3. (Num a) => a -> a。由於我們將 (+) 應用於 a，它必須是 Num 的例項。
4. a -> String 或 a -> [Char]。這會忽略第一個引數，因此它可以是任何型別。
5. (Char -> a) -> a。在此表示式中，x 必須是一個函式，它接收 Char 作為引數。然而，我們不知道它會產生什麼，所以我們稱之為 a。
6. 型別錯誤。在這裡，我們假設 x 的型別是 a。但是 x 應用於自身，所以它必須是 b -> c 型別。但然後它必須是 (b -> c) -> c 型別，然後它必須是 ((b -> c) -> c) -> c 型別，等等，導致無限型別。
7. (Num a) => a -> a。同樣，由於我們將 (+) 應用於 a，它必須是 Num 的例項。

資料型別

對

定義類似於

data Triple a b c = Triple a b c

tripleFst (Triple x y z) = x
tripleSnd (Triple x y z) = y
tripleThr (Triple x y z) = z

帶有型別簽名的程式碼為

data Quadruple a b = Quadruple a a b b

firstTwo :: Quadruple a b -> [a]
firstTwo (Quadruple x y z t) = [x,y]

lastTwo :: Quadruple a b -> [b]
lastTwo (Quadruple x y z t) = [z,t]

我們注意到這裡只有兩個型別變數，a 和 b 與 Quadruple 相關聯。

多個建構函式

程式碼

data Tuple a b c d = One a
                     | Two a b
                     | Three a b c
                     | Four a b c d

tuple1 (One   a      ) = Just a
tuple1 (Two   a b    ) = Just a
tuple1 (Three a b c  ) = Just a
tuple1 (Four  a b c d) = Just a

tuple2 (One   a      ) = Nothing
tuple2 (Two   a b    ) = Just b
tuple2 (Three a b c  ) = Just b
tuple2 (Four  a b c d) = Just b

tuple3 (One   a      ) = Nothing
tuple3 (Two   a b    ) = Nothing
tuple3 (Three a b c  ) = Just c
tuple3 (Four  a b c d) = Just c

tuple4 (One   a      ) = Nothing
tuple4 (Two   a b    ) = Nothing
tuple4 (Three a b c  ) = Nothing
tuple4 (Four  a b c d) = Just d

程式碼

fromTuple :: Tuple a b c d -> Either (Either a (a,b)) (Either (a,b,c) (a,b,c,d))
fromTuple (One   a      ) = Left  (Left  a        )
fromTuple (Two   a b    ) = Left  (Right (a,b)    )
fromTuple (Three a b c  ) = Right (Left  (a,b,c)  )
fromTuple (Four  a b c d) = Right (Right (a,b,c,d))

在這裡，我們使用巢狀的 Either 來表示有四個（而不是兩個）選項。

遞迴資料型別

程式碼

listHead (Cons x xs) = x
listTail (Cons x xs) = xs

listFoldl f y Nil = y
listFoldl f y (Cons x xs) = listFoldl f (f y x) xs

listFoldr f y Nil = y
listFoldr f y (Cons x xs) = f x (listFoldr f y xs)

二叉樹

程式碼

elements (Leaf x) = [x]
elements (Branch lhs x rhs) =
  elements lhs ++ [x] ++ elements rhs

程式碼

treeFoldr :: (a -> b -> b) -> b -> BinaryTree a -> b
treeFoldr f i (Leaf x) = f x i
treeFoldr f i (Branch left x right) = treeFoldr f (f x (treeFoldr f i right)) left

elements2 = treeFoldr (:) []

或

elements2 tree = treeFoldr (\a b -> a:b) [] tree

第一個 elements2 只是第二個的更緊湊版本。

程式碼

treeFoldl :: (a -> b -> a) -> a -> BinaryTree b -> a
treeFoldl f i (Leaf x) = f i x
treeFoldl f i (Branch left x right) = treeFoldl f (f (treeFoldl f i left) x) right

elements3 t = treeFoldl (\i a -> i ++ [a]) [] t

延續傳遞風格

它既不完全模仿。它的行為最接近 foldr，但在初始值的處理上略有不同。我們可以在直譯器中觀察差異

示例

CPS> foldr (-) 0 [1,2,3]
2
CPS> foldl (-) 0 [1,2,3]
-6
CPS> fold  (-) 0 [1,2,3]
-2

很明顯，它的行為不同。透過寫下 fold 和 foldr 的推導，我們可以確切地看到它們在何處不同

     foldr (-) 0 [1,2,3]
==>  1 - foldr (-) 0 [2,3]
==>  ...
==>  1 - (2 - (3 - foldr (-) 0 []))
==>  1 - (2 - (3 - 0))
==>  2

     fold  (-) 0 [1,2,3]
==>  fold' (-) (\y -> 0 - y) [1,2,3]
==>  0 - fold' (-) (\y -> 1 - y) [2,3]
==>  0 - (1 - fold' (-) (\y -> 2 - y) [3])
==>  0 - (1 - (2 - 3))
==>  -2

本質上，主要的區別在於，在 foldr 的情況下，"初始值"在最後使用（替換 []），而在 CPS 的情況下，初始值在開頭使用。

CPS 中的 map 函式

map' :: (a -> [b] -> [b]) -> [a] -> [b]
map' f [] = []
map' f (x:xs) = f x  (map' f xs)

map2 :: (a -> b) -> [a] -> [b]
map2 f l = map' (\x y -> f x : y) l

點消除

map2 f = map' (\x y -> (:) (f x) y)
map2 f = map' (\x -> (:) (f x))
map2 f = map' (\x -> ((:) . f) x)
map2 f = map' ((:) . f)

CPS 中的 filter 函式：（需要仔細檢查）

filter' :: (a -> [b] -> [b]) -> [a] -> [b]
filter' f [] = []
filter' f (x:xs) = f x  (filter' f xs)

filter2 :: (a -> Bool) -> [a] -> [a]
filter2 f l = filter' (\x y -> if (f x) then x:y else y) l