Haskell Tutorial（7）filter、map、fold 模式


在〈Haskell Tutorial（6）從 List 處理初試函數式風格〉最後出的題目應該很簡單吧！解答如下 …

sum' :: [Int] -> Int
sum' lt =
    if null lt
        then 0
        else head lt + (sum' $ tail lt)

main = do
    putStrLn $ show $ sum' []         -- 顯示 0
    putStrLn $ show $ sum' [1, 2]     -- 顯示 3
    putStrLn $ show $ sum' [3, 4, 5]  -- 顯示 12

打鐵趁熱，繼續來看更多的函數式風格，你會發現沒那麼難！該從哪邊開始呢？有稍微涉獵過函數式的開發者，應該多少都有聽過 filter、map 之類的，在〈Haskell Tutorial（5）如喝水般自然的高階函式〉中也會稍微談到，就來介紹一下吧！

List 的 filter 模式

實際上，filter 函式是處理 List 時經常遇到的一個模式實現，就稱它為 filter 模式好了，此模式的發掘很簡單，舉例來說，若你想寫一個 greaterThan5 函式，如果 List 為空，那就直接回傳，否則測試首元素是否為大於 5，是的話留下，不是就別理它了，然後測試剩餘清單，因此函式會是：

greaterThan5 :: [Int] -> [Int]
greaterThan5 lt =
    if null lt then lt
    else 
        if head lt > 5 then head lt : (greaterThan5 $ tail lt)
        else greaterThan5 $ tail lt

如果想寫一個 smallerThan4 函式呢？

smallerThan4 :: [Int] -> [Int]
smallerThan4 lt =
    if null lt then lt
    else    
        if head lt < 4 then head lt : (smallerThan4 $ tail lt)
        else smallerThan4 $ tail lt

如果你真的誠實地自己寫了這個 smallerThan4，而不是從上頭 greaterThan5 複製、貼上之後，把 > 5 修改為 < 4，greaterThan5 修改為 smallerThan4，應該也發現了，兩個結構是一模一樣地，就只有 > 5、< 4 不同以及函式名稱不同，> 5、< 4 是函式，這在〈Haskell Tutorial（5）如喝水般自然的高階函式〉中說過了，為什麼不寫個 filter' 呢？

filter' :: (Int -> Bool) -> [Int] -> [Int]
filter' cond lt =
    if null lt then lt
    else
        if cond $ head lt then head lt : (filter' cond $ tail lt)
        else filter' cond $ tail lt

如果你還不是很習慣 Haskell 的型態宣告方式，暫時忽略它沒有關係，Haskell 會試為你推斷出一個適當的型態，雖然我還是建議試著看懂它，因為其實沒那麼難！好吧！我承認，-> 是多了一點！

總之，這個 filter' 的結構跟前兩個函式還是很像，只不過，現在可以用這個 filter' 加上你指定的過濾條件，來做任何你想要過濾的事了：

使用 filter'

看到了嗎？因為你將 List 分而治之，因而，很容易發覺 greaterThan5 與 smallerThan4 有著類似的結構，因而重構出 filter' 函式，單看這函式也很簡單，如果 List 為空，那就直接回傳，否則測試首元素，True 的話留下，不是就別理它了，然後過濾剩餘清單。

List 的 map 模式

類似地，map 函式是處理 List 時經常遇到的一個模式實現，照樣也稱它為 map 模式好了。照例從一個簡單需求開始，將一個整數 List 全部加 5，傳回一個新的 List：

map5To :: [Int] -> [Int]
map5To lt =
    if null lt then lt
    else head lt + 5 : (map5To $ tail lt)

夠簡單！應該稍微熟悉這種思考方式了！空 List 就直接回傳，要不然就是首元素加 5，然後剩下的 List 繼續 map5To。如果要寫個 multify3To 呢？也許你會阻止我寫出實作了，因為必然會有類似的結構，僅僅只是將 (+ 5) 改為 (* 3)，然後函式名稱改一改而已，(+ 5)、(* 3) 沒問題地就是函式，直接來寫個 map' 函式：

map' :: (Int -> Int) -> [Int] -> [Int]
map' mapper lt =
    if null lt then lt
    else (mapper $ head lt) : (map' mapper $ tail lt)

map' 本身也不難理解，如果是空 List 的話直接回傳，要不然就用 mapper 處理一下首元素，剩下的 List 繼續 map'，遞迴就是這麼一回事，只要關心這次遞迴該做什麼就好，剩下的 List 如何處理？那是下一次 map' 該擔心的事。

當然，這邊的 filter'、map' 只是針對 Int，Haskell 內建的 filter、map 不只針對 Int，這是為了簡化範例而已，對應瞭解這兩個模式而言是足夠了。

List 的 fold 模式

接下來要談的 fold 模式稍微囉嗦一點，出發點是一開始看到的 sum' 函式，一般來說，如果是空 List，加總值應該就是 0，不過，也許你會有不同的意見，既然要對清單中的元素加總，那麼傳入空 List 就應該是個錯誤，如果是這樣的話，來修改一下 sum' 函式：

sum' :: [Int] -> Int
sum' lt =
    if null $ tail lt
        then head lt
        else head lt + (sum' $ tail lt)

因為 tail 函式若傳入一個空 List，就會引發錯誤，因此，sum' 現在也不能接受空 List 了，接下來，來看看如果你要寫個將 List 所有元素乘在一起的 multiplyTogether 該怎麼寫：

multiplyTogether :: [Int] -> Int
multiplyTogether lt =
    if null $ tail lt
        then head lt
        else head lt * (multiplyTogether $ tail lt)

依照前面的經驗，一眼就可以看出結構很像，那麼就來重構，寫個 fold 如何？

fold :: (Int -> Int -> Int) -> [Int] -> Int
fold fn lt =
    if null $ tail lt
        then head lt
        else fn (head lt) (fold fn $ tail lt)

注意！這次需要的是一個接受兩個引數的函式，因此 fn 參數的型態是 (Int -> Int -> Int)，現在，你可以用 fold 來做加總或相乘的動作了：

使用 fold

感覺很神奇嗎？若從結構上來看，無疑地，sum'、multiplyTogether 與 fold 都是類似的，只是這個 fold 直接看，感覺比較抽象，以 fold (+) [1, 2, 3, 4, 5] 來說，fold 的相加順序是 5 會 4 相加得到 9，然後 9 與 3 相加得到 12，然後 12 與 2 相加得到 14，然後 14 與 1 相加得到最後的 15。

其實這就像是在折紙，把 1、2、3、4、5 由左而右畫在紙上，你就是從最右邊開始折紙，每折一次，就將上一次執行結果與左邊的元素用 fn 處理，這就是為什麼它叫做 fold 的原因，簡單來說，如果你打算走訪整個 List 來求得單一值，可以使用這個 fold。

Haskell 中有一些函式以 fold 開頭，像是 foldl、foldr、foldl1、foldr1，概念類似，不過有些比較深入的細節要探討，以後有機會再來談！