Java 開發者的函數式程式設計（1）初探函數式程式設計



English

你可以在 Google Play 或 Pubu 上取得收錄本系列文章的 Java Lambda Tutorial 電子書。
在 認識 Lambda/Closure 系列 中，我談到了什麼是 Lambda/Closure、不同程式語言的支援方式，以及為什麼 JDK8 採用了目前的 Lambda 語法。想要善用 Lambda，可以從其它已具備一級函式的語言中借鏡，實際上在這些語言中，許多一級函式的概念是直接或間接來自於函數式程式設計（Functional programming），更進一步地，函數式程式設計的模型是基於 Lambda 演算。若能一步步深入這些概念，就更能夠瞭解 Lambda/Closure 的實際應用場合。
在 認識 Lambda/Closure（6）一級函式與 Lambda 演算 中，曾經簡介過 Lambda 演算的基本概念，而從這篇文章開始，我會介紹何謂函數式程式設計，以及在 Java 中如何進行函數式程式設計。不過，為什麼要認識函數式程式設計？
在 〈你的程式語言可以這樣做嗎？〉（Can Your Programming Language Do This?）中，Joel Spolsky 說過：

...有第一級函數的編程語言讓你找到更多抽象化的機會...

在《編程的領尖對話》（Coders at Work） 這本書中，Simon Peyton Jones 提到：

...純函數式領域中學到的觀念與想法，可能給主流領域帶來資訊，帶來啟發...

在 《Java 開發者的函數式程式設計》（Functional Programming for Java Developers）這本書中，Dean Wampler 在第一章〈為何要函數式程式設計？〉（Why Function Programming?）列出了五個看法：
  • 我想寫好並行程式（Concurrent program）
  • 大部份程式只是在做資料處理問題（Data Management Problem）
  • 函數式程式設計更模組化
  • 工作上我要更有效率
  • 函數式程式設計是返樸歸真
想瞭解這幾點在說些什麼，最好的方式就是親自進行函數式程式設計。首先來看看，要怎麼取得費式數（Fibonacci number）。根據維基百科中對費式數列的定義：

在數學上，費波那西數列是以遞歸的方法來定義：

F0 = 0 F1 = 1 Fn = Fn-1 + Fn-2

在命令式程式設計（Imperative programming）中，你必須告訴電腦求解問題的每個步驟。例如，可以使用 Java 實作一個如下的 static 方法： 
static int fib(int n) {
    if(n == 0 || n == 1) {
        return n;
    }
    int a = 0;
    int b = 1;
    for(int i = 2; i <= n; i++) {
        int tmp = b;
        b = a + b;
        a = tmp;
    }
    return b;
}
在函數式程式設計中，只要定義問題就可以了。也就是說，以你使用的程式語言來宣告問題。例如，可以使用 Java 如下宣告問題： 
static int fib(int n) {
    if(n == 0 || n == 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}
這個程式碼的可讀性比第一個好此，不過如果程式語言直接支援函數式程式設計的話，會有更好的可讀性。例如，使用 Haskell 來實作的話，程式碼看起來與費式數的數學定義就很像： 
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)
不過，這個函式的效能不太好。因為每次呼叫都會再進行兩次自身呼叫，如此呼叫下去，遞迴呼叫次數會呈指數增長。可以使用遞迴中的一個特定形式 - 尾遞迴（Tail recursion） - 來改寫這個函式。在尾端迴中，函式會直接呼叫自身，或者是在最後一個步驟進行回傳，因此在呼叫堆疊中增加一個堆疊框架（Stack frame）時會耗用較少的資源，例如，此時就不再需要記錄區域變數，因為必要的運算都已完成；從遞迴返回時，也只需回傳相同的值，更重要的是，函數式語言常允許尾遞迴消去（Tail recursion elimination），像是在編譯時期用迴圈來取代尾遞迴，或者在執行時期進行最佳化，藉以增進效能。使用尾遞迴來重寫先前函式的話，會像是： 
fib 0 = 0
fib 1 = 1
fib n = addPrevsRecusivelyUntilCounterIsN (fib 1) (fib 0) 2 n

addPrevsRecusivelyUntilCounterIsN prev1 prev2 counter n
    | counter == n = result
    | otherwise = addPrevsRecusivelyUntilCounterIsN result prev1 (counter + 1) n
    where result = prev1 + prev2
呃...尾遞迴可能會增加一些複雜性。效能與可讀性幾乎總是對立的，即便如此，至少函數式程式設計的基本原則還是存在的，我們還是在定義問題，只是定義變得比較囉嗦而已，只不過，使用函數式語言的話，可以有更多的機會在效能與可讀性之間找到平衡點。你也可以運用尾遞迴來改寫先前的 Java 方法，只不過，程式碼會更複雜，而且 Java 並不支援尾遞迴消去。
這邊的重點在於，如果使用的語言並非函數式語言，你不能不假思索地直接套用函數式設計的所有概念，否則就有可能事倍功半，可讀性與效能都會變差。如果你想進行純函數式程式設計，使用函數式語言會比較好，像是 Scala、Haskell 等。
那麼使用非函數式語言，要怎麼撰寫函數式風格的程式碼呢？只有先瞭解函數式設計的本質，才可以讓我們明瞭，如何適當地擷取函數式設計的概念。
函數式程式設計中一個顯而易見的外在形式就是遞迴，不過，遞迴不是重點，將問題分解為子問題才是重點，通常子問題在分解之後，自然而然就會形成遞迴。以加總數列為例，以命令式方式求解的話，就必須要求電腦將變數 sum 初始為 0，取得數列的下個元素，將元素加至 sum，重複這個動作直到所有元素都迭代過為止，接著傳回 sum。 
static int sum(int... nums) {
    int sum = 0;
    for(int num : nums) {
        sum += num;
    }
    return sum;
}
那麼，以函數式要如何求解呢？讓我們重新思考加總數列這個問題，子問題之一是，空數列的加總為何？是 0！子問題之二是，首元素為 x 而尾數列為 xs 的加總為何？那就是 x 與 xs 的總和進行加總！使用 Haskell 寫下這兩個子問題的話就會是… 
sum [] = 0
sum (x:xs) = x + sum xs
那麼要怎麼求解呢？不用求解，Haskell 會幫你求解，你只要定義問題就好了。
「等一下！等一下！現在是在討論 Java 啊！別老是寫 Haskell...XD」好的！不過呢！物件導向程式設計是 Java 的主流典範，在使用 Java 以函數式方式求解之前，得先來談談代數資料型態（Algebraic data type）、處理數列時共通的模式、以及不可變特性（Immutability），這會在之前的文章中分別探討...