1.9 全麥編程

讀者至此應已注意到本章採用的特殊編程風格。 一般說到串列，大家會先想到資料結構課程中常提到的連結串列(linked list)。 介紹連結串列的範例程式大多用迴圈或遞迴追蹤著指標，一個一個地處理串列中的元素。 在指令式語言中做關於陣列的操作時，也常用變數或指標指著「目前的」元素， 並在一個迴圈中將該變數逐次遞增或減。 總之，我們處理聚合型資料結構時，總是將其中元素一個個取出來處理。 但本章的做法不同：我們將整個串列視為一個整體，對整個串列做 map, filter, dropWhile 等動作，或將它和另一個串列整個 zip 起來...。

這種編程方式被稱作全麥編程(wholemeal programming)， 第1.11 節中將解釋此詞的由來。 全麥編程的提倡者們認為：一個個地處理元素太瑣碎，而鼓勵我們拉遠些， 使用組件，以更抽象的方式組織程式的結構。

諸如 map, filter, iterate, zipWith 等等組件其實都是常見的編程模式。 它們可被視為為了特定目的已先寫好的迴圈。 拜高階函數與惰性求值之賜，這些組件能容易地被重用在許多不同脈絡中。 這麼做的好處之一是：諸如 map, filter, zip 等組件的意義清楚， 整個程式的意義也因此會比起自行在迴圈中一個個處理元素來得容易理解。 事實上，這麼做可以養成我們思考演算法的新習慣。 一些常見的編程模式現在是有名字的，我們把編程模式抽象出來了。 而如同第0 章所述，抽象化是我們理解、掌握、操作事物的重要方法。 我們現在有了更多詞彙去理解、討論程式與演算法： 「這個演算法其實就是先做個 map，把結果 concat 起來，然後做 filter...」

在本書其他章節中我們也將看到：這些抽象化方便我們去操作、轉換程式。 具體說來，如果程式用這些組件拼湊成，我們對這些組件知道的性質都可用在我們的程式上。 例如，如果我們知道 map f . map g = map (f . g)， 當我們看到程式中有兩個相鄰的 map, 我們可用已知的性質把他們合併成一個 --- 這相當於合併兩個迴圈。或著我們可以把一個 map 拆成兩個，以方便後續的其他處理。 程式的建構方法使得程式含有更多資訊，使我們有更多可操作的空間。

全麥編程之所以成為可能，有賴程式語言的支援。 例如，高階函數使得我們能將與特定問題相關的部分 （如 map f 與 filter p 中的 f 與 p）抽象出來； 惰性求值使我們勇於使用大串列或無限串列作為中間值，不用擔心它們被不必要地真正算出。

此外，全麥編程也需要豐富的組件函式庫。設計良好的組件捕捉了常見的編程模式， 有了它們的幫忙，我們的程式可寫得簡潔明暸 --- 本章之中大部分的程式都是都是一行搞定的 ``one-liner''. 但，這些組件不可能窮舉所有的編程模式。我們仍會需要自行從頭寫些函數。 受到全麥編程影響，在自行寫函數時，我們也常會希望將它們寫得更通用些， 藉此發現常見的編程模式，設計出可重用的組件。

全麥編程能寫出多實用的程式？ 第1.11 節中會提及其他學者嘗試過的，包含解密碼、解數獨在內的有趣例子。 在本節，我們則想示範一個小練習：由下至上的合併排序(merge sort)。

合併排序   假設我們已有一個函數 merge' :: (List Int × List Int) -> List Int, 如果 xs 與 ys 已經排序好，merge' (xs,ys) 將它們合併為一個排序好的串列。 (註15) 之所以取名為 merge'，因為在第2.12 節中我們將使用一個類似且相關的函數 merge :: List Int -> List Int -> List Int. 函數 merge' 可用第2.13 節的方式歸納寫成， 也可使用將在第\todo{where}章提及的組件 unfoldr 做出。 我們如何用 merge' 將整個串列排序好呢？

一般書中較常提及由上至下的合併排序： 將輸入串列（或陣列）切成長度大致相等的兩半，分別排序，然後合併。 本節則以由下至上的方式試試看。 如果輸入串列為[4,2,3,5,8,0,1,7]，我們先把 每個元素都單獨變成串列，也就是變成[[4],[2],[3],[5],[8],[0],[1],[7]]。 然後把相鄰的串列兩兩合併：[[2,4],[3,5],[8,0],[1,7]]， 再兩兩合併成為 [[2,3,4,5],[0,1,8,7]]， 直到只剩下一個大串列為止。

如果我們定義兩個輔助函數：wrap 將一個元素包成一個串列， isSingle 判斷一個串列是否只剩下一個元素，

wrap :: a -> List a
wrap x = [x] 

isSingle :: List a -> Bool
isSingle [x]  = True
isSingle xs   = False 

那麼上述的合併排序可以寫成：

msort = head . until isSingle mergeAdj . map wrap 

這幾乎只是把口語描述逐句翻譯：先把每個元素都包成串列， 反覆做 mergeAdj 直到只剩下一個大串列，然後將那個大串列取出來。

下一項工作是定義 mergeAdj :: List (List Int) -> List (List Int), 其功能是將相鄰的串列兩兩合併。 如果我們能訂出一個函數 adjs :: List a -> List (a × a), 將相鄰的元素放在序對中，mergeAdj 就可以寫成：

mergeAdj = map merge' . adjs 

但 adjs 該怎麼定義呢？ 對大部分讀者來說，最自然的方式也許是用第2 章將討論的歸納法。 但作為練習，我們姑且用現有的組件試試看。 先弄清楚我們對 adjs 的期待。 當 xs = [x0,x1,x2,x3], 我們希望 adjs xs = [(x0,x1),(x2,x3)]. 但當 xs 有奇數個元素時，例如 xs = [x0,x1,x2,x3,x4], 最後一個元素 x4 便落單了。 如果是為了合併排序，我們也許可以把 x4 和 [] 放在一起， adjs xs = [(x0,x1),(x2,x3),(x4,[])]. 但為使 adjs 適用於更多的情況，也許我們應該讓它多拿一個參數， 當作落單的元素的配對。 因此我們把 adjs 的型別改為 a -> List a -> List (a × a), 希望 adjs z xs = [(x0,x1),(x2,x3),(x4,z)].

我們試著看看這可如何辦到。

• 首先，zip xs (tail xs) 可把 xs 的每個元素和其下一個放在序對中。 例：當 xs = [x0,x1,x2,x3,x4] 時， zip xs (tail xs) 的值是 [(x0,x1), (x1,x2), (x2,x3), (x3,x4)].

• 如果我們為 zip 的第二個參數補上一個 z, 成為 zip xs (tail (xs ++ [z]))， 這可歸約為 [(x0,x1),(x1,x2),(x2,x3),(x3,x4),(x4,z)]。

• 再將位置（由 0 算起）為奇數的元素丟棄，我們便得到原先希望的 [(x0,x1),(x2,x3),(x4,z)] 了！

讀者可試試看當 xs 有偶數個元素時的情況。 總之，adjs 可定義成：

adjs ::  a -> List a -> List (a × a)
adjs z xs = everyother (zip xs (tail xs ++ [z])) 

其中 everyother ys 把 ys 中位置為奇數的元素丟棄。

最後，考慮如何把串列中位置為奇數的元素丟棄。 一種做法是：一直從串列中丟掉頭兩個元素，直到串列用完：

everyother :: List a -> List a
everyother = map head . takeWhile (not . null) . iterate (drop 2) 

總而言之，由下至上的合併排序可寫成：

msort :: List Int -> List Int
msort = head . until isSingle mergeAdj . map wrap 

其中 mergeAdj 的定義是：

mergeAdj :: List (List Int) -> List (List Int)
mergeAdj = map merge' . adjs [] 

如果我們想看到合併排序完成前的每一步驟，可將 msort 中 （以 iterate 與 dropWhile 定義出）的 until 改為 iterate 與 takeWhile:

msortSteps :: List Int -> List (List (List Int))
msortSteps = takeWhile (not . isSingle) . iterate mergeAdj . map wrap 

例如，msortSteps [9,2,5,3,6,4,7,0,5,1,8,2,3,1] 可得到

[  [[9],[2],[5],[3],[6],[4],[7],[0],[5],[1],[8],[2],[3],[1]],
   [[2,9],[3,5],[4,6],[0,7],[1,5],[2,8],[1,3]],
   [[2,3,5,9],[0,4,6,7],[1,2,5,8],[1,3]],
   [[0,2,3,4,5,6,7,9],[1,1,2,3,5,8]]] 

最後兩個串列合併為 [0,1,1,2,2,3,3,4,5,5,6,7,8,9]，即為 msort 的結果。