Lists in functional programming

歡迎來到函數式程式設計（Functional Programming）中的列表！

你好！本章將為你介紹 **列表（List）**——這是你在函數式程式設計（FP）世界中，最重要且最基礎的資料結構。

如果你已經在程序式程式語言（例如 Python）中使用過陣列（Array）或列表，這裡的某些概念會讓你覺得很熟悉。但 FP 處理列表的方式非常獨特且強大。理解這種結構是掌握映射（mapping）、過濾（filtering）和摺疊（folding）等函數式演算法的關鍵！

你將學到：

• 列表是如何定義與表示的。
• 頭（Head）與尾（Tail）的關鍵概念。
• 你可以在列表上執行的核心操作。
• 如何在遞迴函數定義中將列表作為參數使用。

---

1. 定義與表示列表

在函數式程式設計中，列表是一串型別相同的數值序列。它們永遠是有序的（ordered）。

1.1 列表標記法

列表通常使用方括號（[ ]）來表示。

• 整數列表範例：[7, 2, 1]
• 字串列表範例：["Adam", "Ananya", "Ben"]

重點： 與程序式程式設計中的陣列不同，函數式列表通常設計為不可變的（immutable），這意味著一旦創建，就無法直接更改。如果你想要一個「修改後」的列表，你必須創建一個新的！

1.2 空列表

空列表顧名思義——就是一個不包含任何元素的列表。

• 空列表的標記法非常簡單：[]

---

2. 頭與尾：解構列表

函數式列表處理中最核心的概念，是列表如何能遞迴地拆解為兩個部分：頭（Head）與尾（Tail）。這種技巧在遞迴函數定義中被頻繁使用。

2.1 連接（頭 : 尾結構）

任何非空列表都可以表示為其頭與尾的連接，通常在 Haskell 等語言中使用冒號運算子（:）來書寫（Head : Tail）。

想像列表 [4, 3, 5]。

• 頭（Head） 是第一個元素（單個數值）。
  對於 [4, 3, 5] 而言，頭是 4。
• 尾（Tail） 是列表中其餘的部分（它本身也是一個列表）。
  對於 [4, 3, 5] 而言，尾是 [3, 5]。

因此，我們可以將原始列表表示為：4 : [3, 5]。

💡 比喻：一副撲克牌
想像一疊牌。頭就是你拿起來的最上面那張牌（單個項目）。尾就是剩下那堆牌（仍然是一個牌的列表）。

關於尾的重要規則

列表的尾永遠是一個列表，即使它只包含一個元素或者是空的。

考慮列表 [5]：

• 頭是 5。
• 尾是 []（空列表）。
• 表示法：5 : []

關鍵總結：列表在本質上是遞迴定義的：列表要麼是空列表，要麼由一個頭元素和一個尾列表組成。

---

3. 基礎列表操作

函數式程式語言提供了與列表互動的基本操作。讓我們看看常見的考試函數，並以類似 Haskell 的語法進行示範。

列表範例：listOne = [1, 2, 3]

1. 回傳列表的頭（head）
這會回傳第一個元素。
head listOne 的結果是 1。

2. 回傳列表的尾（tail）
這會回傳除第一個元素外的所有內容（作為一個列表）。
tail listOne 的結果是 [2, 3]。

3. 檢查是否為空列表（null）
這會回傳一個布林值（True 或 False），表示列表是否為空。
null listOne 的結果是 False。
null [] 的結果是 True。

4. 回傳列表長度（length）
這會回傳列表中元素的個數。
length listOne 的結果是 3。

5. 加入項目或連接列表（++）
++ 運算子用於將兩個列表連接在一起（串接）。
如果 listTwo = [4, 5]，那麼：
listOne ++ listTwo 的結果是 [1, 2, 3, 4, 5]。

若要加入單個項目（例如 9），你必須將該項目視為一個單元素的列表：
listOne ++ [9] 的結果是 [1, 2, 3, 9]。

關鍵總結：函數式列表操作的設計目的，不是提取組件（頭、尾），就是檢查屬性（長度、null），或者是建立新的列表（連接）。

---

4. 函數中的模式匹配（Pattern Matching）

在函數式程式設計中，列表通常以遞迴方式處理。為了簡化這個過程，我們在定義函數時使用一種稱為模式匹配的技術。

4.1 以頭與尾作為參數參考

當你定義一個接收列表作為輸入的函數時，可以使用 (x:xs) 模式自動將列表拆解為頭與尾。

• x 代表頭（Head）（第一個元素）。
• xs 代表尾（Tail）（剩餘的列表部分）。

如果將列表 [8, 3, 2] 傳遞給函數 sum：

函數內部的 (x:xs) 參數會自動分配：
x = 8
xs = [3, 2]

4.2 遞迴列表處理範例

模式匹配的一個經典用法，是使用遞迴計算列表中所有元素的總和。我們需要兩種情況：

1. 基底情況（停止條件）：如果列表為空，則總和為 0。
   sum [] = 0
2. 遞迴情況：如果列表非空（符合 x:xs 模式），總和就是頭（x）加上其餘列表的總和（xs）。
   sum (x:xs) = x + sum (xs)

讓我們追蹤 sum [8, 3, 2] 的過程：

1. sum [8, 3, 2] = 8 + sum [3, 2]
2. sum [3, 2] = 3 + sum [2]
3. sum [2] = 2 + sum []
4. sum [] = 0（觸發基底情況）
5. 結果：8 + 3 + 2 + 0 = 13

如果這看起來有點複雜，別擔心！多練習追蹤這些步驟，重點在於觀察列表如何在每一次遞迴調用中縮減一個元素（頭），直到到達空列表（基底情況）為止。