Haskell Tutorial（6）從 List 處理初試函數式風格


老實說，到目前為止，除了沒有變數、函式一定得有傳回值之外，你沒有接觸到什麼函數式風格，那麼，就透過 List 來體會一下吧！開發者一定很熟悉 List，基本上它是一種有序、具索引的資料結構，怎樣能透過它來體會函數式？這樣吧！先透露後面要寫的一個 length' 函式，先想一下，你怎麼實作它，才能讓 length' 在接受一個 List 後，傳回它的長度？

用迴圈？Haskell 中沒有這種東西！無論如何，還是先從簡單的開始 …

List 基本操作

在 Haskell 中要建立一個 List，可以使用 [] 來建立，例如，[1, 2, 3, 4, 5] 是一個 List，['a', 'b', 'c'] 是一個 List，只要元素型態相同，就可以放在同一個 List 中。例如：

建立 List

第三個 List 的建立失敗了，因為元素不是同一型態，你可能會聯想到 Java 的泛型（Generic），像是 List<Integer>、List<Char> 這樣的特性，在 Haskell 中這特性是有點類似，稱為 Type variable。

舉例而言，Haskell 中有個 head 函式，可以取 List 的第一個元素，如果在 GHCI 中使用 :t head 檢驗這個函式的型態，結果會是 [a] -> a，a 是個 Type variable，也就是 a 可以代換為任何型態。

建立一個 List 之後，你可以使用 ++ 來串接兩個 List，使用 : 在一個 List 前置一個元素，使用 == 可以比較兩個 List 的內容是否相同：

++、: 與 ==

你可以一直用 : 不斷地在一個 List 前置元素，實際上，之後你會看到，[1, 2, 3] 其實就是 1:2:3:[] 的語法蜜糖，[] 是個空 List，真正在構造時，其實是透過 : 函式遞迴地在 [] 前置元素，類似地，[1, 2, 3] ++ [4, 5, 6] 時，其實是遞迴地在 [4, 5, 6] 前置元素，也就是 1:2:3:[4, 5, 6] 這樣的過程，因此，如果 ++ 左邊是個很長的清單時，就會有效能上的問題，日後你更熟悉 Haskell 之後，可以思考調整演算過程，想辦法改用 : 來取得效能改進。

有注意到一開始的 List 示範中，['a', 'b', 'c'] 建立後，在 GHCI 中的顯示結果嗎？"abc"？是的！如果你使用 "abc" 建立了字串，那也不過只是 ['a', 'b', 'c'] 的語法蜜糖，如果你比較 "abc" == ['a', 'b', 'c']，結果會是 True，因此，++ 等函式，都可以套用在字串上。

除了 == 之外，List 比較還可以使用 /=（不等於）、>、<、>=、<= 等，這幾個函式比較時是逐個元素比較，而每個元素必須具有 Ord 這個 Typeclass 的行為，== 的話需要有 Eq 的行為。例如：

List 比較

當然，List 是有順序、具索引的資料結構，你當然會想要指定索引取得元素，指定索引要使用 !! 函式，索引是從 0 開始。例如，[10, 20, 30] !! 1 結果就是 20。

head、tail、null

如果你要取得 List 第一個元素該怎麼做呢？使用 !! 指定索引 0 是個方式，但不建議，你可以使用 head 函式，如果要取得尾清單，也就是扣掉第一個元素之後的子清單，則可以使用 tail，這兩個函式很重要，在還沒認識模式匹配（Pattern match）與代數資料型態（Algebraic data types）之前，在需要取首元素及尾清單時，都會先使用 head 與 tail。

head、tail

在 Haskell 中，[] 就代表了空 List，要怎麼判斷一個 List 為空？是可以使用 list == []，不過不建議，使用 null 函式會比較好。例如：

null

來寫個 length' 吧！

Haskell 中確實是有個 length 函式，不過，這邊要自己來寫一個，為了避免名稱衝突，就叫做 length' 吧！這在 Haskell 中是個完全合法的函式名稱，那麼該怎麼寫？如果你是來自命令式（Imperative）語言，像是 Java，可能會寫個迴圈來計數（我知道有 size 方法可以用，不過現在是說要自己寫）：

List<Integer> lt = Arrays.asList(1, 2, 3);
int size = 0;
for(Integer ele : lt) {
    size += 1;
}

不好意思！這在 Haskell 中做不到，因為光是要變更 size 的值就是不可能的，迴圈的本質就是可變的（Muttable），Haskell 中沒有迴圈這東西，怎麼辦？很簡單，觀察一下 for each 語法做的是什麼事？看看清單中還有沒有元素，如果沒有的話，長度當然就是 0，如果有的話就加 1，然後使用剩餘清單進入下一次檢查。將這段描述寫成 Haskell 就可以了：

length' :: [a] -> Int
length' lt =
    if null lt
        then 0
        else 1 + (length' $ tail lt)

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

基本上，length' 幾乎就是你的需求宣告（或稱為描述），這就是為什麼函數式程式設計常被稱為宣告式（Declarative）設計的原因。你看到了遞迴！嗯 … 遞迴只應天上有，凡人應當用迴圈？

迴圈的本質就是重複，會重複表示你每一次都做相同的事，很多開發者為了一些效能或其他因素，常常會在迴圈中額外做很多事，因而讓迴圈本體變得複雜，如果要你將這麼複雜的迴圈本體變成遞迴，那麼往往你得記得每一次遞迴的狀態，因而使得遞迴更加令人難以理解。

實際上，遞迴的本質應該是易於理解的，關鍵在於一次做一件事，這一次做完了，就是下個子任務了，不用再去記得上一次任務的狀態，這樣就會容易掌控遞迴，這是分而治之（Divide and conquer）的概念，以 length' 來說，這次只要傳進來的 List 不為空，那我只要取得尾清單的長度，再加上 1 就可以得到答案了，至於尾清單長度？那是 length' $ tail lt 的事，不關我的事！

自己寫個 sum' 吧！

如果有個 Int 的 List，想取得當中元素加總值該怎麼做呢？Haskell 中有內建的 sum 函式可以使用，不過這邊請你自己寫一個 sum'，沒辦法直接想出來的話，還是先思考一下，命令列你會怎麼寫：

List<Integer> lt = Arrays.asList(1, 2, 3);
int sum = 0;
for(Integer ele : lt) {
    sum += ele;
}

那麼你每一次的迴圈到底做了什麼事呢？看看清單中還有沒有元素，如果沒有的話，加總當然就是 0，如果有的話就加上元素值，然後使用剩餘清單進入下一次檢查。使用 Haskell 來宣告這段描述，就會是答案：

自己寫個 sum' 吧！