關於函數編程（二）摺疊與抽象化

函數編程提倡以函數為組織程式的基本單元。所謂函數是純粹的、，將一個值對應到另一個值的數學函數。和指令式程式比較，函數語言中不能直接使用賦值(assignment)、輸出入等等副作用。對用慣指令語言的人來說，這似乎是函數語言的主要特徵。

但這種負面表列聽來沒什麼建設性。不允許副作用有什麼好處？John Hughes 在他有名的文章 Why Functional Programming Matters 中解釋，函數語言能增進程式的模組化。此話怎說呢？

從現在起我們得選定一個程式語言來舉例了。 Haskell 是一個惰式純函數語言，從 90 年代中期發展到現在，已廣被接受為函數語言界溝通的工具之一。我們將用 Haskell 來給例子。

串列

沿襲自 LISP 以來的傳統，串列(list)在很多函數語言中都是基本資料結構。一個串列也就是將一串元素依序排出。在 Haskell 中，

• 空串列，也就是一個沒有東西的串列，寫作 []，通常念做 ‘nil’.
• 如果 xs 是一個串列，x : xs（念做 ‘x cons xs’）也是一個串列， 代表將 x 接在 xs 左邊。

例如，1 : 2 : 3 : [] 是由三個元素組成的串列。由於串列常用，Haskell 另外提供了一些特殊語法，同一個串列可寫作 [1, 2, 3].

有了資料，我們還得有些處理資料的函數。例如，給定一個數字串列，我們若想知道數字的和，可以定義這麼一個函數 sum:

sum [] = 0
sum (x : xs) = x + sum xs

數學上我們習慣把函數 f 在 x 上的值寫作 f(x). 在 Haskell 中我們只寫作 f x. 上述定義第一行說函數 sum 在 [] 上的值是 0. 白話一點說，空串列的和是 0. 如果不是空串列呢？那麼這個串列一定可以分解成 x : xs, 而 sum (x : xs) 的值就是 x 加上 sum xs — 串列 xs 的和。

既然知道怎麼算數列的和，數列的積也不難算：

prod [] = 1
prod (x : xs) = x × prod xs

上面的定義說，空串列的積是 1; 而 x : xs 的積是 x 乘上 xs 的積。

舉一反三，給定一個布林值串列，要如何檢查是否每個元素都是 True 呢？我們可以這麼做：

and [] = True
and (x : xs) = x && and xs

其中 && 是 Haskell 的二元合取(conjunction)運算元。

不過，看到這裡讀者是否發現，這幾個函數的結構其實差不多？

摺疊

比較 sum, prod, 和 and 的定義，我們發現其實只有紅色的地方不同：三個函數都同樣地把串列從左至右走訪一遍，差別僅在碰到串列結尾時分別傳回不同的值，並用不同的運算元處理遞迴呼叫的結果。我們能不能讓這三個函數共用同一個定義呢？

我們把定義中的不同之處抽出當作參數，並把抽象後的函數稱作 foldr:

foldr f e [] = e
foldr f e (x : xs) = f x (foldr f e xs)

在碰到空串列時我們傳回 e, 而遞迴呼叫的結果用函數 f 來處理（字母開頭的函數預設使用前置語法，所以這時 f 寫在前面，而不是中間）。有了 foldr 後，sum, prod, 與 and 可分別定義為:

sum  = foldr (+) 0
prod = foldr (×) 1
and  = foldr (&&) True

到了這裡我們應緩一下，回顧一下剛剛發生了什麼。有人說計算科學是關於抽象化的學問。我們捨棄 GOTO 改用 for, while, repeat 等種種控制結構，是控制結構的抽象化；呼叫副函式，是程序的抽象化；對資料封裝是一種抽象化；物件導向是一種抽象化。而函數語言又提供另一種抽象化的方式：我們可以對程式結構做抽象化。

函數 foldr 是一個特例。這類型的函數在函數語言中統稱作「摺疊(fold)」。除了串列，二元樹、多元樹、自然數等資料結構也有自己的摺疊函數。某一類型的資料結構的摺疊函數是可以機械化地產生的。除了摺疊之外還有其他常見的程式結構，如「展開(unfold)」, 「映射(map)」, hylomorphism, .. 等等。

有了抽象，我們便可從這角度去談程式：凡是能寫成摺疊的函數都有哪些性質？在什麼條件下，一個摺疊和另一個函數組合後仍然是一個摺疊？一個摺疊和一個展開接在一起，會是什麼？對一個摺疊函數有哪些最佳化技巧可以用？摺疊有沒有辦法快速地實作？哪些程式結構可以在多核機器上執行？

再回頭看，函數語言的什麼設計讓我們可做這層抽象化呢？在 foldr 的定義中, 參數 f 是一個函數。函數語言提供的便利性之一是函數也像一般的值，能當參數傳，能當作回傳值。Hughes 便說，高次函數(higher-order functions, 把函數當資料的函數)的使用是促進模組化的利器之一。

還沒被唬住的讀者這時差不多該抗議了：也許在 Hughes 寫那篇文章的時代，把函數當參數傳是函數語言的獨有特色，但現在時代已經不同了。很多語言都有 closure 的概念, 甚至我們要用 C 的函數指標來蠻幹也是可以的。況且，這跟我們最開頭所說的「純函數只是數學函數，沒有副作用」有什麼關係呢？一個有 printf 指令的函數難道就不能當作參數嗎？

答案其實是上面說過的一句話：有了類次「摺疊」這樣的抽象化，我們接下來希望能談所有摺疊的性質，而這在純函數的範疇下將容易得多。不過我們下次再談。

其他摺疊範例

在結束之前，我們多看一些使用 foldr 的例子，並順便多介紹一些語法。

關於串列，另一個常需要知道的性質是其長度。空串列的長度當然是 0. 串列如果是 x : xs，其長度應該是 xs 的長度加一。所以我們可以這麼定義:

length [] = 0
length (x : xs) = 1 + length xs

和 sum 比較，差異是在第二行定義中參數 x沒有用到。要把 length 寫成 foldr, 我們可以這樣做：

length = foldr len 0
    where len x n = 1 + n

其中 where 是定義區域變數的語法。但有時像 len 這樣的小函數並沒有重要到需要給一個名字。另一種寫法是這樣：

length = foldr (λ x n → 1 + n) 0

(λ x1 .. xn → e)是一個沒有名字的函數，參數是 x1 ... xn, 而 e 是函數主體。這是由 λ calculus 衍生出的符號。

給定一個數字串列，我們要怎麼把每個數字都加一？我們其實可以考慮更一般的問題：給定一個函數 f, 和一個串列 xs。如果 xs 是 [x1, x2,... ,xn], 怎麼定義函數 map 使得 map f xs 的值會是 [f x1, f x2,... f xn]？提醒一下：map f [x1, x2,... ,xn] = [f x1, f x2,... f xn] 並不算是正式的定義。只要用到「點點點」，就不是正式的定義了。

一個可能的定義是這樣的：

map f [] = []
map f (x : xs) = f x : map f xs

如果輸入是空串列，我們仍得到一個空串列。否則我們求出 f x 的值，並遞迴計算 map f xs，然後把它們接在一起。

值得注意的一點是 map 也是一個高次函數的例子：這是一個產生函數的函數。給一個函數 f 後, map f 又是一個函數；這個函數把 [x1, x2,... ,xn] 對應到 [f x1, f x2,... ,f xn].

仔細看看 map 的結構，其實仍和本文說到的幾個函數很像。我們能不能把 map f 寫成 foldr 呢？可以的。一種可能寫法如下：

map f = foldr (λ x ys → f x : ys) []

有了 map 的幫助，「把串列的每個數字都加一」可寫成 map (λ x → x + 1).

像 map 這樣的函數統稱為「映射」。不只是串列，某類資料結構的映射函數可用折疊定義，因此也是可以公式化地導出的。