The functional programming paradigm

👋 歡迎來到函數式編程的世界！

你即將深入了解函數式編程範式 (Functional Programming Paradigm)。這與你可能習慣的程序式編程（即專注於步驟序列和變更變數）有很大的不同。

函數式編程 (FP) 將運算視為數學函數的評估，並避免更改狀態與使用可變數據。它基於嚴謹的數學概念，這使得代碼往往更具預測性、更容易測試，並且非常適合處理像大數據處理這樣的複雜問題！

如果一開始覺得有些抽象，請不用擔心——我們將通過清晰的例子，將這些數學概念拆解成簡單易懂的部分。

1. 函數式編程範式：基礎

1.1 作為映射的函數（數學視角）

在函數式編程中，函數被視為一種將輸入映射到輸出的數學規則。

核心概念：函數類型符號

每個函數 \(f\) 都有一個定義好的類型，指定了它接收什麼樣的輸入，以及產生什麼樣的輸出。

符號：
$$f: A \rightarrow B$$

• A 是定義域 (Domain)（所有有效輸入值的集合）。
• B 是對應域 (Co-domain)（輸出值所選取的集合）。
• 箭頭 (\(\rightarrow\)) 代表「映射至」的關係。

例子： 如果一個函數將整數平方，其類型可能是：

square: Integer $\rightarrow$ Integer

關於對應域的重要說明： 對應域 (B) 中的每個成員都不一定必須是實際的輸出。
例子： 函數 $\texttt{sqr}: \mathbb{R} \rightarrow \mathbb{R}$（實數平方）的對應域是所有實數集合 (\(\mathbb{R}\))。然而，平方的結果不可能是負數，因此 \(\mathbb{R}\) 中的負數永遠不會是輸出。

1.2 常見數系（定義域與對應域）

你必須熟悉函數定義域和對應域中使用的標準數學集合：

• 自然數 ($\mathbb{N}$)： 正整數集合，包含零。
  $$\mathbb{N} = \{0, 1, 2, 3, \ldots\}$$
• 整數 ($\mathbb{Z}$)： 所有整數的集合（正數、負數和零）。
  $$\mathbb{Z} = \{\ldots, -2, -1, 0, 1, 2, \ldots\}$$
• 有理數 ($\mathbb{Q}$)： 可以寫成分數（兩個整數之比）的數。
  你知道嗎？ 由於任何整數 \(n\) 都可以寫成 \(n/1\)，所以所有整數也都是有理數。
• 實數 ($\mathbb{R}$)： 所有「可能的現實世界量」的集合，包括整數、有理數和無理數（例如 \(\pi\) 或 \(\sqrt{2}\)）。

2. 一等公民與函數應用

2.1 一等物件（或值）

在函數式編程語言中，函數本身被賦予了特殊的地位。它們被視為一等物件 (First-class objects)（或一等值）。

將「一等」想像成 VIP——函數可以像標準數據類型（如整數或字串）一樣，去任何地方並做任何事。

一等物件可以：

1. 出現在表達式中（例如 \(2 \times (\texttt{add } 3)\)）。
2. 賦值給變數（例如將函數定義儲存在變數中）。
3. 作為參數傳遞（作為輸入傳遞給另一個函數）。
4. 在函數調用中作為返回值（由另一個函數輸出）。

你知道嗎？ 這種函數可以被傳遞的能力，正是讓高階函數 (Higher-Order Functions) 等概念成為可能的關鍵！

2.2 函數應用與參數

使用特定輸入運行函數的過程稱為函數應用 (Function application)。

例子： 將函數 $\texttt{add}$ 應用於參數 3 和 4，寫作 $\texttt{add } (3, 4)$。

當一個函數接收多個參數時，定義域由參數類型的笛卡兒積 (Cartesian product) 表示。

兩個參數的類型表示法：
$$\texttt{add: integer } \times \texttt{ integer } \rightarrow \texttt{ integer}$$
這意味著函數 $\texttt{add}$ 接收一對整數（笛卡兒積）並返回單個整數。

3. 進階概念：高階函數 (HOFs)

3.1 什麼是高階函數？

如果一個函數符合以下其中一個或兩個條件，它就被視為高階：

1. 它接收一個或多個函數作為參數。
2. 它返回一個函數作為結果。

比喻： 如果普通函數是沖泡咖啡（接收牛奶和糖，返回咖啡），那麼高階函數就像咖啡店經理：它接收配方（一個函數）和原料，甚至可能將得到的咖啡機（另一個函數）轉交給其他人。

3.2 函數組合

函數組合 (Functional composition) 是一種將兩個函數結合以創建第三個新函數的操作。第一個函數的輸出會成為第二個函數的輸入。

逐步組合：

給定兩個函數：
$$f: A \rightarrow B \text{ 和 } g: B \rightarrow C$$

組合 $g \circ f$（讀作「g after f」或「g composed with f」）是一個新函數：
$$g \circ f: A \rightarrow C$$

• 步驟 1： 函數 $f$ 首先應用於定義域 $A$ 中的輸入。它返回對應域 $B$ 中的一個值。
• 步驟 2： 接著將函數 $g$ 應用於 $f$ 返回的結果。它返回對應域 $C$ 中的一個值。

使用實數 ($\mathbb{R}$) 的例子：

• 令 \(f(x) = x + 2\)
• 令 \(g(y) = y^3\)

組合 \(g \circ f\) 為：
$$g \circ f = (x + 2)^3$$

4. 必備高階函數：Map, Filter 與 Fold

這三個函數是函數式編程中的基本工具，通常應用於清單 (Lists) 等數據結構。你必須能夠識別並追蹤它們的用法（考試中通常使用 Haskell 語法）。

4.1 Map

$\texttt{map}$ 函數將指定的函數應用於清單中的每個元素，並生成一個包含結果的新清單。原始清單保持不變。

例子（Haskell 語法）：
想像我們有一個函數 $\texttt{square x = x * x}$ 和一個數字清單。

$$\texttt{numbers = [1, 2, 3, 4]}$$ $$\texttt{map square numbers}$$

產生清單： $\texttt{[1, 4, 9, 16]}$

4.2 Filter

$\texttt{filter}$ 函數透過對清單中的每個元素應用布林條件（返回 $\texttt{True}$ 或 $\texttt{False}$ 的函數）來處理清單。它返回一個新清單，其中僅包含滿足條件的元素。

例子（Haskell 語法）：
我們想要小於 10 的數字。

$$\texttt{filter (<10) [15, 8, 20, 3]}$$

產生清單： $\texttt{[8, 3]}$

4.3 Fold (或 Reduce)

$\texttt{fold}$ 函數通過重複應用一個組合函數 (Combining function)，並從一個初始值開始，將一個值清單縮減為單個值。

你需要了解兩種類型，取決於函數是從左側還是右側處理清單。結果有時是一樣的（例如加法），但有時卻截然不同（例如減法）。

左摺疊 ($\texttt{foldl}$)

$\texttt{foldl}$ 從最左邊的項目開始並向右進行。組合函數會被重複應用，首先合併初始值。

$$\texttt{foldl} (\text{+}) \ 0 \ \texttt{[1, 2, 3, 4]}$$

評估（從左至右）：
$$((((0 + 1) + 2) + 3) + 4) = 10$$

現在，試試減法：
$$\texttt{foldl} (-) \ 0 \ \texttt{[1, 2, 3, 4]}$$
評估（從左至右）：
$$((((0 - 1) - 2) - 3) - 4) = -10$$

右摺疊 ($\texttt{foldr}$)

$\texttt{foldr}$ 從最右邊的項目開始並向左進行。

$$\texttt{foldr} (-) \ 0 \ \texttt{[1, 2, 3, 4]}$$

評估（從右至左）：
$$1 - (2 - (3 - (4 - 0)))$$ $$1 - (2 - (3 - 4))$$ $$1 - (2 - (-1))$$ $$1 - 3 = -2$$

⚠️ 常見錯誤警告： 在追蹤 $\texttt{foldl}$ 和 $\texttt{foldr}$ 時，請務必記住方向性和初始值，特別是在使用像減法這樣非交換運算的時候！

5. 清單、遞歸與模式匹配

5.1 函數式編程中的清單

清單是值的序列，通常用括號括起來，例如 $\texttt{[7, 2, 1]}$。空清單簡稱為 $\texttt{[]}$。

表頭 (Head) 與表尾 (Tail)

在函數式語言中，非空清單本質上被視為兩個部分：

1. 表頭 (Head)： 第一個元素（單個值）。
2. 表尾 (Tail)： 清單的其餘部分（總是另一個清單，即使它是空的）。

例子： 清單 $\texttt{[4, 3, 5]}$ 表示為 $\texttt{4 : [3, 5]}$。
表頭是 $\texttt{4}$。
表尾是 $\texttt{[3, 5]}$。

5.2 基本清單操作（Haskell 例子）

你需要能夠描述並應用這些標準操作：

• 返回表頭： $\texttt{head [1, 2, 3]}$ 評估為 $\texttt{1}$。
• 返回表尾： $\texttt{tail [1, 2, 3]}$ 評估為 $\texttt{[2, 3]}$。
• 測試是否為空： $\texttt{null [1, 2, 3]}$ 評估為 $\texttt{False}$。 $\texttt{null []}$ 評估為 $\texttt{True}$。
• 返回長度： $\texttt{length [1, 2, 3]}$ 評估為 $\texttt{3}$。
• 清單連接： $\texttt{++}$ 運算符連接兩個清單。
  $$\texttt{[1, 2, 3] ++ [4, 5]}$$ 評估為： $\texttt{[1, 2, 3, 4, 5]}$

5.3 遞歸與模式匹配

由於函數式編程避免了傳統的循環（迭代）和變更變數，複雜的任務通常使用遞歸 (Recursion) 來解決。

遞歸函數會調用自身，它依賴於兩個至關重要的組成部分：

1. 基本情況 (Base Case)： 導致函數不再調用自身的條件，從而終止該過程。（必須存在，以防止無限遞歸！）
2. 遞歸情況 (Recursive Case)： 函數調用自身的條件，通常處理稍小一點的輸入。

模式匹配：定義情況

模式匹配 (Pattern matching) 是一種根據參數的結構或值來定義函數不同行為的機制（例如定義基本情況與遞歸情況）。

例子：階乘計算 (n! = n * (n-1)!)

在 Haskell 中，我們清楚地定義基本情況和遞歸情況：
$$\texttt{fact 0 = 1}$$ （基本情況：匹配輸入 0）
$$\texttt{fact n = n * fact (n-1)}$$ （遞歸情況：匹配任何其他數字 n）

在遞歸中引用表頭與表尾

在定義處理清單的遞歸函數時，模式匹配允許我們在函數定義中直接引用清單的表頭和表尾，通常使用 $\texttt{(x:xs)}$：

例子：遞歸求清單中所有元素的和
$$\texttt{sum [] = 0}$$ （基本情況：空清單的和為 0）
$$\texttt{sum (x:xs) = x + sum xs}$$ （遞歸情況）

• 如果輸入清單是 $\texttt{[8, 3, 2]}$，函數會匹配 $\texttt{(x:xs)}$ 模式。
• $\texttt{x}$ 引用表頭 ($\texttt{8}$)。
• $\texttt{xs}$ 引用表尾 ($\texttt{[3, 2]}$)。
• 函數返回：$\texttt{8 + sum [3, 2]}$（對較小的清單調用自身）。