從大二玩 functional programming 到現在，終於決定寫篇文章向同學們 介紹它。顧名思義，functional programming 是以「函數」為主體的程 式設計典範。支援這個典範的程式語言自然地稱作 functional language, 「函數語言」。有些開相關課程的學校便將課名取做「函數語言」。本文 取用縮寫 FP 來表示 functional programming。

FP 想要解決的是軟體工程的老問題。如何讓軟體元件更容易組合、重用？ 由例子來說明比較容易，我們用排序來當作貫穿本文的例子。 為了完整起 見，複習一下 insertion sort：把尚未排序的元素一個個插入到已經排序 好的部份中。 通常對陣列做排序時，我們用陣列的半邊當已經排好的部份， 另外半邊是未排好的部份。如果用 C 的話，我們可能這樣寫：

在這個 C 程式中，我們可以看出最外面的迴圈負責把所有元素一個個依序 處理， 可以分辨出那一段是在找插入的地方，那一段是作插入和搬移的動 作。但是，這些 isort() 的組成成份都已經深深「嵌入」這個程式裡頭， 沒辦法搬出來重用了。

我們也可以看出，i 這個變數把陣列分割成兩部份。小於 i 的部份是已經 排序完成的，i 以上的部份是尚待插入的。 能從程式中看出意義，可不簡 單， 因為演算法的邏輯並沒有被正面寫出來，而是隱晦地隱藏在這些變數 中了。鍛煉到一定程度的程式員， 才能從一連串的變數設值、搬移、拷貝 中讀解出程式本來的意義。

而若是以 FP 的方式，這個 insertion sort 又要怎麼寫呢？

FP 所謂的「函數」比 C, Pascal 裡面的函數還要嚴格，是真正「把一個 值對應到另一個值」的數學函數。函數語言中，我們不僅可以定義函數， 也可以把函數當作參數傳給別的函數，或把函數當傳回值。

FP 程式是由許多基本函數組合而成的，我們將以 Haskell 這個 FP 語言 為例，介紹幾個將會用到的基本函數。函數語言通常不太會處理陣列，而 擅長處理串列。串列是一連串的元素，用中括號括起來。目前我們不妨把 它想成資料結構中談到的 linked list，適合從頭到尾一個方向的操作。 例如 takeWhile 這個函數，給一個條件和一個串列， 它從頭開始抓取所 有合乎條件的元素，直到遇到第一個不合的元素為止。

在 Haskell 裡面，叫用一個函數 f 寫作 f x ，而不是數學中的 f(x)。 上面的例子是連餵兩個參數給 takeWhile. 和 takeWhile 相對的是 drop- While, 從頭開始，把所有合乎條件的元素丟掉。例如

如何把兩個串列連接起來呢？用另一個內建函數 ++ 。

其實，把 takeWhile 和 dropWhile 得到的兩個串列再接起來，又會得到 原來的串列了。 可以把這個關係寫成

串列內的元素也可以單獨抓出來處理。用 head 這個函數可以抓出串列的 第一個元素，head [1,2,3,4] = 1; 和 head 相對的是 tail, 把第一個 元素丟掉。 tail [1,2,3,4] = [2,3,4].

另一種也和串列有關，相當重要的函數是 fold。Haskell 的 foldr 函數 接受三個參數, 分別是一個二元運算元, 一個初始值, 和一個串列. 例如:

意謂以 0 為初始值, 從串列右邊開始一個接一個做加法 （foldr 的 r 表示右邊 ）, 也就是 1+(2+(3+(4+(5+0)))) 。 所以在互動式的 Haskell 環境中，鍵入上面的式子，就會得到 15. 同樣的,

就是 1*(2*(3*(4*(5*1)))), 故得到 120. 注意到 + 和 * 本身就是函數， 但是在這裡我們把它當參數傳給了 foldr。前面傳給 takeWhile 和 drop- While 的 (< 5) 也是函數當作參數的例子。其他的幾個例子 :

由於 fold 看起來像是把二元運算元 @ 給「插入」串列的兩兩元素之間, 因此在一些函數語言之中, 同樣功能的函數被稱做「insert」或「inter- leave」. 又因為 fold 把一個長串列變成一個值，所以有些語言裡把這 個函數叫做「reduce」。

回到 insertion sort。 我們首先需要一個函數能把一個元素插入一個已 經排好的串列裡面。與其想怎麼做，不如想想插入後的串列會變成什麼樣 子？假設我們的排序由小到大，如果把 v 插入 list 裡，顯然比 v 小的 元素全跑到左邊，剩下的就到右邊。 這樣一來，insert 這個函數就很直 覺了

Insertion sort 接下來要反覆把原有的元素一個個插入這個已經排好的 串列裡。 「一個個」？ 沒錯，用 foldr！最初的時候還沒開始排，所以 foldr 的初始值是空的串列，寫作 [] :

我們的 insertion sort 就這樣完成了！（寫成 isort list = foldr insert [] list 也可以，不過這裡的寫法比較 強調 isort 是怎麼組合成的）

分析一下這個 Haskell 版的排序。 首先，我們的確達到了「重用」的原 則。程式由 takeWhile, dropWhile, fold 等更小的小單元像拼積木一樣 的組成，這些通用目的的小單元經由別的組成方式，又可以成為不同的程 式。另一方面，我們自己寫的 insert 函數也可以很容易移作別的用途， 被別的函數呼叫使用。

takeWhile, dropWhile 和 fold 都是描述控制結構的函數。 一個是「從 頭開始拿」，一個是「從頭開始丟」，一個是「一個個餵給 f 」。 還有 另一個重要的函數 map ，表示「對每個分別做」。

傳統語言把這些結構都寫成看起來差不多的迴圈。這些結構在程式中時常 出現，許多演算法（例如這個 insertion sort ）說穿了也不過是它們的 組合而已。把這些控制結構獨立出來是很有用的，不但可以反覆的重用， 也可以加強程式的可讀性，使我們一眼看出這個演算法在做什麼。

但在傳統語言中，這些控制結構是沒有辦法獨立出來的。一方面因為傳統 語言不允許我們把 (< 5), (< v), insert 這些「應該放在迴圈裡面」的 東西那麼容易地當成參數傳進去。一方面也因為資料型別的問題（語言必 需容許多形 -- polymorphism）。

最後，你是否同意， FP 是一種 declarative programming -- 宣告式的 程式設計？在這個例子中，我們並不告訴電腦「怎麼做(how)」排序， 只 告訴電腦「是什麼(what)」：把一個元素插到串列中，得到的新串列「是」 什麼樣子？isort 「是」哪些基本函數的組合？

宣告式的程式設計要比一般所謂「指令式(imperative)」的程式設計要輕 鬆許多。程式員只需要寫出一個物體的定義，這個定義本身就是一個可以 跑的程式。不必將一個個的指令餵給電腦，告訴電腦許多「把這個搬過來， 把那個搬過去」的細節。為了告訴電腦「怎麼作」，傳統程式設計有太多 的細節要處理。在描述這些細節的同時，演算法原本很清楚的邏輯也被弄 模糊了。

定義一個函數有兩種方式，第一個是像前面的例子所示範的，用現有的函 數堆積木似的把自己要的函數拼出來。當沒有適合的函數可用，例如沒有 適合的控制結構時，只好用數學定義的方式，寫出遞迴函數的定義。本文 的示範以前者為主，實際寫程式時，兩種方式都會用到。

在結束這篇文章之前，我們再舉另一個排序演算法, merge sort, 作第二 個例子。通常談到 merge sort, 我們想到的是：把所有元素分成大約等 長的兩段，分別遞迴下去排序，然後想辦法花 O(n) 的時間把兩串排過的 元素合併起來。不過在這裡，我們不妨把 merge sort 想成反覆合併的過 程。把一個長串列

想像成許多只有一個元素的小串列

假如有一個函數 merge, 可以把這樣的一個串列給兩兩合併成

那麼我們再呼叫 merge 一次，不就可以得到

只要反覆把 merge 一層層地套，直到最後一定只剩下一個大串列

只要再把 [[1,2,3,4,5,6,7,8,9]] 還原成 [1,2,3,4,5,6,7,8,9], 我們 不就完成了排序嗎？

把 merge sort 用 Haskell 實作，需要哪些組成元件呢？

1. 反覆套用一個函數 f ，在 Haskell 中可以用 iterate f 來表示； iterate f x 會產生一個長串列

2. 接下來我們要作的是從這個長串列中取出第一個已經合併完成的計算結 果。取出第一個合乎某條件的元素，其實就是把不合條件的都去掉，然 後抓剩下的第一個。所以

這個 first 函數是很好用的，不僅可以用在這裡，也可以用在很多其他地方。

3. 只剩下「一個」大串列，可以寫成 (==1).length, 即長度等於一，只有一 個東西的意思。

4. 最後考慮的是怎麼把一個串列 [6,2,1,3] 打散成小串列 [[6],[2],[1],[3]]? 其實只要用我們提過的 map, 「對每個元素」都把它變成一個小串列。

最後，我們的 merge sort 就可以清楚的寫成

現在只剩下 merge 的定義了。 merge 的工作是把串列給「兩兩」合併， 和 fold, map 比較起來，這並不是常見的流程，沒有適當的現成積木可 用，還是寫成遞迴函數比較方便些。我們只把它附在附錄中。

Functional Programming 用自己的一套方法解決了軟體元件組合重用的 問題。讀者們不妨想想，是哪些限制（和哪些該限制而沒限制的）使得傳 統程式語言無法這麼容易地把元件組合起來？「重用」和「函數」兩個詞， 字面上看起來八竿子打不著邊，為什麼函數能幫助重用？要達到如此便利 的重用，非得使用函數不可嗎？

如果換您來設計程式語言，以同樣的目的為考量點，您也會走上同樣的路 嗎？

[1] Richard Bird and Philip Wadler. Introduction to functional programming. Prentice-Hall 1988

[2] John Hughes. Why functional programming matters. The Computer Journal, 32(2), February 1989

對 FP 有什麼好處、為什麼要有 FP，有深闢的探討。 Hughes 寫過不少好 paper, 但流傳最廣的恐怕還得屬這篇介紹性的文章。

[3] Paul Hudak and Joseph H. Fasel. A gentle introduction to Haskell. SIGPLAN Notices, 27(5), May 1992

一份簡潔扼要的 Haskell 入門。許多 Haskell implementation 都會建議你去讀這篇入門。