關於函數編程(二)摺疊與抽象化

函數編程提倡以函數為組織程式的基本單元。所謂函數是純粹的、,將一個值對應到另一個值的數學函數。和指令式程式比較,函數語言中不能直接使用賦值(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

數學上我們習慣把函數 fx 上的值寫作 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 這樣的函數統稱為「映射」。不只是串列,某類資料結構的映射函數可用折疊定義,因此也是可以公式化地導出的。

This entry was posted in 函數編程簡介, 計算算計 and tagged , . Bookmark the permalink. Post a comment or leave a trackback: Trackback URL.

3 Comments