Haskell Tutorial（17）定義與使用模組 << 前情

到目前為止，介紹了不少 Haskell 基本語法，當然，還有些進階語法沒談到，不過，暫且換個方向，來看看 Haskell 中提供的標準模組中，有哪些基本常用的函式可以使用，詳細介紹每個 API 如何使用其實也蠻沒意義的，這是 API 文件該做的事，這邊的重點還是擺在一個足夠讓你往後探索的基礎上。

Hackage 與 Hoogle

Haskell 可用的套件相關說明資訊，可以在 Hackage 找到，標準套件可以在 The base package 找到。

在開始之前，得介紹一下 Hoogle，一個 Haskell API 搜尋引擎，搜尋頁面 http://www.haskell.org/hoogle/，對於查詢 API 如何使用相當方便：

Data.List 模組

之前介紹過不少 List 的應用，也用過幾個函式，像是 ++、head、tail 等，這些函式實際上是位於 Data.List 模組，不過這幾個函式因為常用，基於方便將之匯入了 Prelude 模組之中，因此，之前不用特別 import 也能使用。

如先前介紹，++ 可以串接兩個 List，這沒什麼好多做解釋的，到是來看看怎麼實現會比較有趣：

add :: [a] -> [a] -> [a]
add [] xs2 = xs2
add (x:[]) xs2 = x : xs2
add (x:xs) xs2 = x : add xs xs2

這個 add 函式，用起來就像 ++，例如：

從 add 實作中可以看到，它會走訪第一個 List，因此若第一個 List 很長，使用 add 會比較沒效率，也就是說，對於 ++ 左邊的 List 很長時，使用 ++ 串接會沒有效率，因此，如果是單純地在 List 中收集元素，應當避免 xs ++ [1]、xs ++ [2, 3] 這樣的動作，改使用 1 : xs、2 : 3 : xs 會是比較好的選擇。

依此類推的話，就是說，對於字串的串接，若 ++ 左邊的字串很長，也要避免使用 ++ 來串接，例如，單純地收集字元的話，應避免使用 xs ++ "a"、xs ++ "bc"，而可以改用 'a' : xs、b : c : xs，會是比較好的選擇。

head、tail 實際上都可以改用 Pattern Matching，視情況而定，有時用 head、tail 方便或易讀，有時用 Pattern Matching 方便或易讀，與它們相對的是 init 與 last，分別取首清單與尾元素，實作上像是：

init' :: [a] -> [a]
init' [] = error "empty list"
init' (x:[]) = []
init' (x:xs) = x : init' xs

last' :: [a] -> a
last' [] = error "empty list"
last' (x:[]) = x
last' (_:xs) = last' xs

對於一個元素在不在 List 中，可以使用 elem，如果想知道索引位置，可以使用 elemIndex，後者沒有匯入 Prelude，需要 import Data.List 才能使用，來看看怎麼實現：

elem' :: Ord a => a -> [a] -> Bool
elem' _ [] = False
elem' ele (x:xs) = if ele == x then True else elem' ele xs

elemIdx :: (Eq a, Num a) => a -> [a] -> Maybe a
elemIdx _ [] = Nothing
elemIdx ele xs = idxOf xs 0
    where
        idxOf (x:xs) idx =
            if ele == x then Just idx 
            else if null xs then Nothing else idxOf xs (idx + 1)

elem' 比較簡單，就是傳回 True 或 False，而在 elemIdx 這方面，因為元素可能不存在於 List 中，因此搜尋結果可能有索引值也可能沒有，因此，傳回型態會是 Maybe。

像這樣來試著做一些基本函式的實作，對於模組中函式的原理與使用，就會有比較多的認識。

關於 fold 的相關函式

在〈Haskell Tutorial（7）filter、map、fold 模式〉中，談過 fold 模式，當時的 fold 函式實現方式，其實就類似 Haskell 內建的 foldr 函式，不過，實際的 foldr 函式還接受一個起始值，例如：

實現的方式會像是：

foldR :: (a -> b -> b) -> b -> [a] -> b
foldR f z []     = z
foldR f z (x:xs) = x `f` (foldR f z xs)

之所以稱之為 foldr，是因為這就像是在折紙，把 1、2、3、4、5 由左而右畫在紙上，你就是從右折紙，每折一次，就將上次執行結果與左邊的元素用指定的函式處理，foldr 的 r 就是 right 的意思，記得，foldr 接受的函式，左邊參數當次的元素，第右參數是上一次計算的結果，記法是，每次折紙時處理的是左邊的元素。以下是 foldr (+) 0 [1, 2, 3, 4, 5]，在走訪整個 List 到最右端之後，接下來就是：

1 + (2 + (3 + (4 + (5 + 0)))
1 + (2 + (3 + (4 + 5)))
1 + (2 + (3 + 9))
1 + (2 + 12)
1 + 14
15

有 foldr，那是不是表示有 foldl？是的！foldl 也像是在折紙，foldl (+) 0 [1, 2, 3, 4, 5] 的話，就像是把 1、2、3、4、5 由左而右畫在紙上，你就是從左折紙，每折一次，就將上次執行結果與右邊的元素用指定的函式處理，實作上像是：

foldL :: (a -> b -> a) -> a -> [b] -> a
foldL f z []     = z
foldL f z (x:xs) = let z' = z `f` x  
                   in foldL f z' xs

記得，foldl 接受的函式，左邊參數是上一次計算的結果，右邊參數是當次的元素，與 foldr 接受的函式是相反的，記法是，每次折紙時處理的是右邊的元素。單從 foldL 示範實作看來，如果執行 foldl (+) 0 [1, 2, 3, 4, 5]，過程會像是：

foldl f (0 + 1) [2, 3, 4, 5]
foldl f (1 + 2) [3, 4, 5]
foldl f (3 + 3) [4, 5]
foldl f (6 + 4) [5]
foldl f (10 + 5) []
15  

這就像是逐步消減 List 來計算，因此，foldl 有時在其他語言中稱為 reduce，不過，上面的過程，應該是嚴格版本的 foldl' 之行為，foldl' 不會進行惰性求值，而 foldl 會進行惰性求值，因此，foldl 實際在運算時，會像是：

foldl f (0 + 1) [2, 3, 4, 5]
foldl f ((0 + 1) + 2) [3, 4, 5]
foldl f (((0 + 1) + 2) + 3) [4, 5]
foldl f ((((0 + 1) + 2) + 3) + 4) [5]
foldl f (((((0 + 1) + 2) + 3) + 4) + 5) []
foldl f ((((1 + 2) + 3) + 4) + 5) []
foldl f (((3 + 3) + 4) + 5) []
foldl f ((6 + 4) + 5) []
foldl f (10 + 5) []
foldl f 15 []
15  

因此，使用 foldl 處理很長的 List 時，常會遇到 stackoverflow 的問題，這時可改用嚴格版本的 foldl'。

如果指定的處理函式不具結合律，應瞭解 foldl、foldr 的差別，例如 +、* 具有結合律，因為 (a + b) + c 與 a + (b + c) 是相同的，- 就不具結合律，例如 foldl (-) 0 [1 .. 10] 結果是 -55，而 foldr (-) 0 [1 .. 10] 結果是 -5。

有時指定的函式本身具有結合律，也要留意一下函式本身的特性，例如 foldl (++) "" ["Justin", "Monica", "Irene"]，雖然 ++ 具結合律，不過在上面討論過，++ 會將左邊的 List 整個走訪過一遍，因此左邊的 List 若很長，會有效率上的問題，執行 foldl (++) "" ["Justin", "Monica", "Irene"] 的話，最後會有 "JustinMonica" ++ "Irene" 的結果，也就是左邊的字串會越來越長，++ 效率就會越來越差，換用 foldr (++) "" ["Justin", "Monica", "Irene"] 會比較好一些，類似地，如果結果是要產生新的 List，使用 foldr 效率會好一些。

foldl、foldr 必須指定初值，foldl1、foldr1 會使用折紙時第一個遇到的元素當初值，因此使用 foldl1 處理 [1, 2, 3, 4, 5] 時，因為是從左折，初值就是 1，使用 foldr1 處理 [1, 2, 3, 4, 5] 時，因為從右折，初值就是 5。

恒等值的考量

除了惰性、結合律以及指定處理函式本身的特性考量之外，fold 相關函式還可以有讓初值為恒等值（Identity）的考量。所謂恒等值，是指使用指定的函式 f 來處理恒等值 n 及 List 中任一元素 m，結果還是還是 m，也就是 f m n 結果會是 m，例如，指定函式為 + 而恒等值為 0 時， 0 + 1 還是 1、0 + 2 還是 2，這麼做的目的在於，如果 List 很長，打算將之切為數等分來計算時，也不致於因為發生累計問題（處理函式要具有結合律）。

例如，foldl (+) 0 [1 .. 100] 的結果是 5050，也許將來你可以實現一個 parallelFoldl，會將 [1 .. 100] 切成四份平行運算，實作概念相當於 (foldl (+) 0 [1 .. 25]) + (foldl (+) 0 [26 .. 50]) + (foldl (+) 0 [51 .. 75]) + (foldl (+) 0 [76 .. 100])，這樣就沒有問題，結果還是 5050。

如果因為某個原因，希望從 5 開始累加，在不平分處理下，雖可以寫成 foldl (+) 5 [1 .. 100]，結果就是 5055，不過，若 foldl 改為自定義的 parallelFoldl (+) 5 [1 .. 100]，結果會相當於 (foldl (+) 5 [1 .. 25]) + (foldl (+) 5 [26 .. 50]) + (foldl (+) 5 [51 .. 75]) + (foldl (+) 5 [76 .. 100])，也就是 5070，那就不對了，對於這個需求，一開始應該是寫成 5 + foldl (+) 0 [1 .. 100] 才是正確的，這樣若 foldl 改為 parallelFoldl，結果就相當於 5 + (foldl (+) 0 [1 .. 25]) + (foldl (+) 0 [26 .. 50]) + (foldl (+) 0 [51 .. 75]) + (foldl (+) 0 [76 .. 100])，這樣就沒有問題。

誰能處理無限長 List？

foldl、foldr 經常被討論的問題之一就是，誰能處理無限長的 List？這問題就在於，無限長的 List 長什麼樣呢？[1 ..]！從左開始折的話，這紙一定是折不盡的，可是，如果從右邊開始折，開始折的邊界又在哪呢？再來看一下 foldR：

foldR :: (a -> b -> b) -> b -> [a] -> b
foldR f z []     = z
foldR f z (x:xs) = x `f` (foldR f z xs)

為了完成 f 的處理，除了 x 之外，還得等待 f 第二個引數，也就是 foldR f z xs 的結果，這就是上面對 foldr 指定 + 時，必須走訪整個 List 才能得到結果的情況。那麼，如果 f 不用等待第二個引數呢？像是指定 \ele y -> ele 會如何？

這就是了，真的是蠻聰明的，雖說打算從右折無限長的 List，不過，每次都只傳回當次元素，一路往左看到，盡頭不就是個 1 嗎？

不過，指定 \ele y -> ele 看起來沒什麼用，來想個有用的好了！嗯！對一個元素為 Bool 的無限長 List 做 || 處理如何（裏頭可能有 True 也可能有 False）？在 Data.List 中有個 iterate 可以建立無限長的 List，例如，iterate not True 就會產生 [True, False, True, False, True ...] 一直循環下去，那麼 foldr (||) False $ iterate not True 會如何？

簡單！雖說是無限長，不過 || 的特性是，只要有一個為 True，就可以判定整個為 True 了，不用等另一個引數處理完畢了，那麼 foldr (||) $ iterate not True 又有什麼用？只能判定 List 是不是有 True 存在嘛！那麼這個呢？

any' :: (a -> Bool) -> [a] -> Bool
any' f = (foldr (||) False) . (map f)

f 是可將值對應至 Bool 的函式，map f 就可以將任意 List 轉為 Bool 元素的 List，這個 List 交給 foldr (||) False，就成了一個，可以判斷 List 中，是否有符合特定條件的元素存在之函式，例如，想知道無限長的 List 中，是不是有能某值整除的數：

在 Data.List 中，已經存在 any 這個函式，不過以上的探討，是個蠻有趣的過程。

如果你想快速地瞭解 Data.List 中有哪些現成的函式可以使用，可以參考 Data.List 中的說明。

後續 >> Haskell Tutorial（19）Data.Set 與 Data.Map 模組