map/filter/fold

在〈無所不在的函式〉談過 filter 函式，這是觀察到程式執行的流程具有重複性的樣版，將之抽象化後建立的函式，這邊來從 list 處理看看如何進行這類的抽象化。

map

先來看看如何將數字 list 中的元素全部加 5，傳回一個新 list：

plus5To :: Num a => [a] -> [a]
plus5To lt =
    if null lt then lt
    else head lt + 5 : (plus5To $ tail lt)

空 list 就直接回傳，要不然就是首元素加 5，然後剩下的 list 繼續 plus5To。如果要寫個 multify3To，將全部的元素乘以 3 呢？

multify3To :: Num a => [a] -> [a]
multify3To lt =
    if null lt then lt
    else head lt * 3 : (multify3To $ tail lt)

你應該發現了，除了 + 5、* 3 以及函式名稱不同，兩個流程幾乎是一模一樣，+ 5、* 3 是函式，何不將相同的流程抽取出來，將 + 5、* 3 作為函式傳入就好呢？例如寫個 map' 呢？

map' :: (a -> a) -> [a] -> [a]
map' mapper lt =
    if null lt then lt
    else (mapper $ head lt) : (map' mapper $ tail lt)
    
main = do
    putStrLn $ show $ map' (+ 5) [3, 4, 5]
    putStrLn $ show $ map' (* 3) [3, 4, 5]

Haskell 本身就有定義 map 函式，因此這邊的範例就在 map' 名稱上多了個 '，以區別內建的 map 函式；在函式型態定義中，a -> a 表示接受 a 傳回 a 的函式，a 型態變數這邊不用約束其必須具有什麼行為，真正要的行為是由 mapper 函式的本體決定，a -> a 僅表示接受的參數與傳回型態必須一致。

進一步地，(a -> a) -> [a] -> [a] 表示接受一個函式，一個 list，傳回一個 list，執行後會顯示 [8, 9, 10] 與 [9, 12, 15]。

看到了嗎？因為將 list 分而治之，因而，很容易發覺 plus5To 與 multify3To 有著類似流程，因而重構出 map' 函式，單看這函式也很簡單，如果 list 為空，那就直接回傳，否則依指定的 mapper 進行元素轉換，將結果置於轉換後的尾 list 之前。

實際上 list 實現了 Haskell 的 Functor 行為，而且可進行映射換的，也不只有 list，詳情可見後續文件〈可以映射的 Functor〉。

filter

類似地，若想寫個 greaterThan5 函式，如果 list 為空，那就直接回傳，否則測試首元素是否為大於 5，是的話留下，不是就別理它了，然後測試剩餘 list：

greaterThan5 :: (Ord a, Num a) => [a] -> [a]
greaterThan5 lt =
    if null lt then lt
    else 
        if head lt > 5 then head lt : (greaterThan5 $ tail lt)
        else greaterThan5 $ tail lt

因為要能比較順序，a 也必須要具有 Ord 的行為；如果想寫一個 smallerThan4 函式呢？

smallerThan4 :: (Ord a, Num a) => [a] -> [a]
smallerThan4 lt =
    if null lt then lt
    else 
        if head lt < 4 then head lt : (smallerThan4 $ tail lt)
        else smallerThan4 $ tail lt

應該也發現了，兩個流程是類似的，就只有 > 5、< 4 以及函式名稱不同，> 5、< 4 是函式，何不將相同的流程抽取出來，將 > 5、< 4 作為函式傳入就好呢？例如寫個 filter' 呢？

filter' :: (a -> Bool) -> [a] -> [a]
filter' predicate lt =
    if null lt then lt
    else
        if predicate $ head lt then head lt : (filter' predicate $ tail lt)
        else filter' predicate $ tail lt
    
main = do
    putStrLn $ show $ filter' (> 5) [3, 4, 5, 6, 7]
    putStrLn $ show $ filter' (< 4) [3, 4, 5, 6, 7]

Haskell 本身就有定義 filter 函式，因此這邊的範例就在 filter' 名稱上多了個 '，以區別內建的 filter 函式；在函式型態定義中，a -> Bool 表示接受 a 傳回 Bool 的函式，(a -> Bool) -> [a] -> [a] 表示接受一個函式，一個 list，傳回一個 list，執行後會顯示 [6, 7] 與 [3]。

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

fold

來看看怎麼寫個將 list 元素加總的函式：

sum' :: Num a => [a] -> a
sum' lt =
    if null $ tail lt
        then head lt
        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

若 list 內容是數字，如果是空 list，加總結果當然就是 0；接下來，若想實作串接字串 list 的 join' 呢？

join' :: [String] -> String
join' lt =
    if null lt
        then ""
        else head lt ++ (join' $ tail lt)

main = do
    putStrLn $ show $ join' []               -- 顯示 ""
    putStrLn $ show $ join' ["1", "2"]       -- 顯示 "12"
    putStrLn $ show $ join' ["3", "4", "5"]  -- 顯示 "345"

流程上非常類似，差別在於空 list 時的傳回值、函式名稱以及 +、++，有沒有辦法抽取可共用的流程呢？這要先處理一下空 list 時的傳回值，你可以指定空 list 時應該傳回什麼預設值，或者是收到空 list 時發生錯誤，若採取後者的話，sum'、join' 可以這麼實作：

sum' :: Num a => [a] -> a
sum' lt =
    let t = tail lt in
    if null t
        then head lt
        else head lt + (sum' t)

join' :: [String] -> String
join' lt =
    let t = tail lt in
    if null t
        then head lt
        else head lt ++ (join' t)

tail 函式若傳入空 list 會引發錯誤，因此，sum'、join' 若指定空 list 也會引發錯誤，現在可以來重構，將重複的流程抽取為 fold：

fold :: (a -> a -> a) -> [a] -> a
fold reducer lt =
    let t = tail lt in
    if null t
        then head lt
        else (head lt) `reducer` (fold reducer t)

main = do
    putStrLn $ show $ fold (+) [1, 2]            -- 顯示 3
    putStrLn $ show $ fold (++) ["3", "4", "5"]  -- 顯示 "345"

因為 +、++ 是需要兩個引數的函式，因此 reducer 的函式型態是 (a -> a -> a)，如上所示，可以使用 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)))
1 + (2 + (3 + 9))
1 + (2 + 12)
1 + 14
15

這就像是在折紙，每折一次，就將上一次執行結果與傳入的元素用 reducer 處理，這就是為什麼它叫做 fold 的原因，簡單來說，如果你打算走訪整個 list 來求得單一值，可以使用這個 fold。

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

實際上 list 實現了 Haskell 的 Fordable 行為，而且可進行 fold 的，也不只有 list，詳情可見後續文件〈發掘具有組合性的行為〉。