關於函數編程(三)摺疊-映射融合定理

高次函數讓我們對程式的結構進行抽象化。也就是說,我們多了一種模組化的方法。但精明的讀者要質疑了:這並不是函數語言獨佔的特色吧?很多語言都有 closure 的概念;況且如果只是為了達到這個目的,並不非得要求函數沒有副作用不可呀。

重點其實是這裡:把常用的程式結構找出來之後,我們希望能開始談這些結構的性質。

來看一個例子。給定一個數字串列,我們想要寫個函數 sumsq 求每個數字的平方的和。例如 sumsq [1,7,5,8] = 1² + 7² + 5² + 8² = 139. 這個函數怎麼寫呢?

上次我們已介紹過幾個常用函數:sum 把一個數字串列加總;map f 把函數 f 套用到串列的每個元素上。假設我們又有一個函數 square x = x × x, 那麼 sumsq 可重用這些函數很簡潔地定義成:

sumsq = sum . map square

其中運算元 . 表示函數合成:如果 fg 都是函數,(f . g) x 是先把 g 套用在 x 上,再把 f 套用到其結果 — 操作性地說是「先做 g, 再做 f」。函數合成的定義是:

(f . g) x = f (g x) 

上述 sumsq 的定義很簡潔清楚,但在操作上,電腦會怎麼執行它呢?輸入串列 [1,7,5,8] 會先給 map square 處理,產生一個中間串列 [1,49,25,64], 再被 sum 加總。實務上這個中間串列並不會多耗多少資源,但為了舉例,我們還是想想:能否把中間串列省掉呢?

摺疊-映射融合定理

可以的,而且其實我們可直接套用現有的定理來做。上次的討論已提到 sum 是一個摺疊:

sum  = foldr (+) 0

map f 是映射。摺疊-映射融合定理告訴我們,一個摺疊與一個映射的合成可以寫成單獨的一個摺疊:

摺疊-映射融合定理

foldr f e . map g = foldr (λ x y → f (g x) y) e

所以 sumsq 可以改寫成:

sumsq = foldr (λ x y → square x + y) 0

而這個程式不會產生中間串列!

直覺上我們可以想像摺疊-映射融合的原理:等號的左邊是先對串列的每個元素做 g 的動作,然後用 f 把串列摺起來。右邊則是把 g 的動作留到摺疊時一起做。熟悉指令語言的讀者可以想像成是把兩個迴圈合而為一。但使用函數語言,我們可以精確地描述哪種迴圈可以融合,融合成什麼。

對程式做數學推論

在這裡我們看到抽象化帶給我們兩方面的好處。一方面,抽象化讓我們能模組化地重用已知的組件,例如用 foldr 定義 sum, 用 summap 定義 sumsq。這是讀者可能比較熟悉的。另一方面,一旦我們辨識出一個函數其實是個摺疊、或其實是個映射,那麼許許多多已知的、關於摺疊或映射的定理和性質都可用在這個函數上。在我的理解中,後者才是函數語言獨有的優點。

如果換成指令語言呢?對於一段指令語言程式,我們能夠談的性質少得多。別說迴圈融合,連 f(1) + f(1) 能不能代換成 2 × f(1) 都不是那麼確定 — 誰知道 f 裡頭有沒有副作用在作怪呢?

函數語言程式有比較好的數學性質。我們可用來對程式做各種推論和操作,如上述的融合定理,將一個程式轉換成另一個比較有效率的的程式;我們可以證明兩個函數的結果是否永遠相同;我們可去開發一些函數的新實作法,例如把映射分配到很多機器上平行地做。只要它仍保有映射該有的性質,程式就仍會是對的。

這裡該附帶說明一下:指令語言上當然也可做數學推論。例如 Dijkstra 的最弱前提運算(weakest precondition calculus)就是為此目的發展的。然而後者在處理指標、別名(aliasing)等問題上碰到瓶頸,而函數語言則避免了這些問題。兩者可說各有適用的範圍。

另一方面,函數語言程式終究也是得用到副作用的。不僅程式得要輸出入、讀寫檔案,一些演算法本來就有著狀態的觀念。這時我們怎麼辦呢?答案是把需要用到的副作用納為數學模型的一部份,將他們的數學性質也描述出來。「函數語言沒有副作用」其實是個概略的說法。較精確地說,「純」函數語言以一套沒有副作用的語意為基底,在需要副作用時則明確地描述副作用的使用。

在寫作大程式時,這樣的做法更有其好處:副作用變成了可以模組化地加上的功能。Haskell 用單子 (monad) 的觀念描述各種副作用,包括狀態變數 (mutable state)、例外 (exception)、非確定性 (non-determinism)、續繼 (continuation) 等等副作用成為可以一個個分別加入的功能。詳情也許以後再談。

摺疊融合定理

關於映射還有些常用的性質。例如,直覺上,我們先把函數 g 應用到串列的每個元素上,得到一個新串列,再把函數 f 應用在每個元素上,這和一次把 f . g 應用到元串列的每個元素應該是一樣的。確實,我們有個映射的函子(functor)定理:

map f . map g = map (f . g)

眼尖的讀者會發現這其實是摺疊-映射融合的一個特例 — 別忘了 map f 本身也是一個摺疊呢。讀者可以試著簡單證明一下。

那麼摺疊-映射融合定理本身要怎麼證明呢?直接的做法是用結構歸納法 — 我們要證明下式對所有的 xs 成立:

(foldr f e . map g) xs = foldr (λ x y → f (g x) y) e xs

那麼我們先檢查當 xs 是空串列 [] 時,上式成立;然後假設上式對 xs 成立,檢查一下上式仍對 x : xs 成立。

寫程式成了很數學的行為。可惜的是國內的資訊科學教育在數學推理方面的訓練比較不夠。這也是我們想要辦 FLOLAC 的理由。

不過,摺疊-映射融合定理其實也是另一定理的特例:

摺疊融合定理
如果對任意 xy, 函數 h, fg 滿足 h (f x y) = g x (h y),則下式成立:

h . foldr f e = foldr g (h e)

摺疊融合定理告訴我們在什麼條件下,在摺疊後面的函數 h 可以融合到摺疊裡。

摺疊融合是個很重要的定理。在 FLOLAC 研習營中我曾對學員說,如果在這門課結束後你只會記得一件事情,我希望會是這個摺疊融合定理。但摺疊融合大概是太抽象了,對上這種密集課程的學生來說,一時要吸收真是挺不容易的。

讀者不妨檢查一下,如何由摺疊融合定理推出摺疊-映射融合定理。

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

Post a Comment

Your email is never published nor shared. Required fields are marked *

You may use these HTML tags and attributes <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*
*