Writing functional programs

歡迎來到函數式程式設計：實戰篇！

哈囉！你已經學習過函數式程式設計範式（Functional Programming Paradigm）的理論基礎（例如：定義域、對應域與一等物件）。現在，我們要進入最令人興奮的部分：編寫實際的函數式程式。

本章重點在於使用函數式語言（例如考試中使用的 Haskell）編寫程式碼時的技巧與工具。理解這些概念——特別是遞迴（Recursion）與高階函數（Higher-Order Functions）——將會徹底改變你解決問題的思維方式！

如果覺得這與程序式程式設計（Procedural Programming）有很大落差，請不用擔心。函數式程式設計鼓勵以簡單、優雅的方式解決問題，通常只需極少量的程式碼。讓我們開始吧！

3.12.2 編寫函數式程式：核心概念

函數式程式設計將計算視為數學函數的求值過程，並避免可變狀態（Mutable State）與副作用（Side Effects）。

1. 定義與使用基本函數

在函數式程式設計中，定義函數通常很直接，就像數學定義一樣。

核心概念：函數定義

• 定義函數時，你需要指定它的名稱、參數以及計算結果所使用的規則。
• 函數必須配合其參數（Argument(s)）來定義。
• 為函數提供輸入（參數）的過程稱為函數應用（Function Application）。

範例（Haskell 語法）：

若要定義一個名為 add 的函數，它接收兩個參數 a 和 b，並返回它們的和：

add a b = a + b

呼叫此函數（函數應用）：add 3 4 將會得出結果 7。

算術與布林運算

函數式語言支援標準運算，你必須熟悉如何應用這些運算：

• 算術運算：加 (+)、減 (-)、乘 (*)、除 (/) 以及次方 (^)。
• 布林比較：等於 (==)、不等於 (/=)、大於 (>)、小於 (<)、大於等於 (>=)、小於等於 (<=)。
• 布林邏輯：AND (&&)、OR (||)、NOT (not)。

重點總結：函數式程式是透過將簡單、純粹的函數應用於輸入來構建的，就像在數學中組成公式一樣。

2. 遞迴與模式匹配

在程序式語言中，我們通常使用迭代（迴圈）來重複執行任務。在函數式語言中，遞迴（函數呼叫自身）是重複執行任務的主要方法。

使用遞迴定義函數

為了防止無限遞迴，遞迴函數的定義必須包含以下兩個部分：

1. 基底案例（Base Case）：停止條件。這是問題最簡單的形式，不需要進一步遞迴，會直接返回一個固定值。
2. 遞迴案例（Recursive Case）：將問題拆解為較小規模的自身問題的規則，並逐漸逼近基底案例。

範例：計算階乘 (n!)

n 的階乘是 \( n \times (n-1) \times ... \times 1 \)。數學規則是 \( fact(n) = n \times fact(n-1) \)，而基底案例為 \( fact(0) = 1 \)。

在函數式程式碼中（Haskell）：
fact 0 = 1
fact n = n * fact (n - 1)

常見錯誤：忘記基底案例會導致無限遞迴！

模式匹配（Pattern Matching）

在上述階乘範例中，編譯器如何知道該使用第一行還是第二行呢？這就是利用模式匹配。

• 模式匹配是指函數式語言將輸入值（或結構）與定義好的模式（情況）進行比對的能力。
• 當你呼叫 fact 3 時，輸入 3 不符合模式 0，因此會執行第二行（遞迴案例）。
• 當你呼叫 fact 0 時，輸入 0 精確符合模式 0，因此返回基底案例 1，從而結束遞迴。

重點總結：遞迴使用基底案例與遞迴案例，而模式匹配則根據輸入的結構或數值來決定使用哪個案例。

3. 高階函數 (Higher-Order Functions, HOFs)

高階函數 (HOF) 是指將另一個函數作為參數、將函數作為結果返回，或兩者兼具的函數。

HOF 對於編寫簡潔且強大的函數式程式碼至關重要。你需要熟練掌握三種主要的 HOF：map、filter 與 fold (reduce)。

A. Map

map HOF 會將給定的函數應用於列表中的每一個元素，並返回一個包含結果的新列表。原始列表不會被修改（這是函數式純粹性的關鍵！）。

類比： 如果你有一個價格列表 [10, 20, 30] 和一個函數 addTax，將此函數 map 到列表上，就會得到 [12, 24, 36]。

課程範例：

定義一個函數 square x = x * x。

執行 map square [1, 2, 3, 4]

產生列表：[1, 4, 9, 16]

B. Filter

filter HOF 會處理列表，並返回一個僅包含原始列表中符合特定條件（謂詞函數）元素的新列表。

類比： 從通訊錄中篩選出所有年齡大於 30 歲的人。

課程範例：

執行 filter (<10) [15, 8, 20, 3]（其中 (<10) 是「小於 10」的條件）。

產生列表：[8, 3]

C. Fold (Reduce)

fold（有時稱為 reduce）HOF 會透過重複應用一個結合函數，將列表中的值縮減為單一數值，並從初始值（累加器）開始。

類比： 加總考試成績。從初始值 0 開始，逐個將成績加總，將整個列表縮減為一個總和。

在 Haskell 中，有兩種版本，具體取決於應用的方向，這對於非交換性運算（如減法）至關重要：

• foldl (Fold Left)：從最左邊的項目開始，由左至右處理。
• foldr (Fold Right)：從最右邊的項目開始，由右至左處理。

範例：減法（順序很重要！）
列表：[1, 2, 3, 4]，初始值：0，運算函數：減法 (-)

使用 foldl：從左邊開始，先應用累加器。
\( (((0 - 1) - 2) - 3) - 4 = -10 \)

使用 foldr：從右邊開始，先將初始值應用於最右邊的元素。
\( 1 - (2 - (3 - (4 - 0))) = -2 \)

重點總結：Map 轉換所有項目，Filter 根據條件選擇項目，而 Fold 將所有項目組合為單一結果。

3.12.3 函數式程式設計中的列表

列表（List）是函數式程式設計中的基本資料結構，常與 HOF 結合使用。

1. 定義與理解列表

• 列表儲存的是一個數值序列。
• 列表通常使用方括號表示，例如 [7, 2, 1]。
• 空列表直接表示為 []。

2. 頭部 (Head) 與尾部 (Tail) 的概念

處理遞迴列表的一個核心概念是將列表分為兩部分：頭部（Head）與尾部（Tail）。

• 頭部 (Head) 是列表的第一個元素。（這是一個單一元素/值）。
• 尾部 (Tail) 是列表的其餘部分。（這始終是另一個列表）。

類比： 想像一列火車。頭部是火車頭。尾部是剩下所有車廂組成的列表。

在函數式語言中，列表通常寫成頭部與尾部的串接，中間以冒號 (:) 分隔。

範例： 列表 [4, 3, 5] 可以表示為 4 : [3, 5]。
其中，4 是頭部，而 [3, 5] 是尾部。

在函數中使用頭部與尾部（遞迴）

定義處理列表的遞迴函數時，通常會在函數參數中使用模式匹配來立即分離頭部與尾部。

如果你定義一個 sum 函數：
sum (x:xs) = x + sum (xs)

• 如果參數是 [8, 3, 2]：
  • x（頭部）指向 8。
  • xs（尾部）指向 [3, 2]。

3. 基本列表運算（Haskell 實作）

你必須了解並能應用以下標準列表運算：

• 取得頭部 (Head)：取得第一個元素。
  範例： head [1, 2, 3] 的值為 1。
• 取得尾部 (Tail)：取得除了第一個元素以外的列表。
  範例： tail [1, 2, 3] 的值為 [2, 3]。
• 測試是否為空 (Null)：檢查列表是否為 []。
  範例： null [1, 2, 3] 的值為 False。
• 取得長度 (Length)：計算元素數量。
  範例： length [1, 2, 3] 的值為 3。
• 建構空列表：直接使用 []。
• 附加項目（串接，Concatenation）：使用 ++ 連接兩個列表。
  範例： [1, 2] ++ [4, 5] 的值為 [1, 2, 4, 5]。

快速複習：列表組成

Head (頭) = 單一元素。
Tail (尾) = 元素列表。
Head 容易取得。
Tail 則需要較長時間處理（因為它本身就是個列表）。

重點總結：列表是透過 HOF 與遞迴來操作的，處理時高度依賴於將其拆解為「單一元素的頭」與「其餘部分的尾」。