Lists in functional programming

欢迎来到函数式编程中的列表！

你好！本章将为你介绍列表 (List)——这是你在函数式编程 (Functional Programming, FP) 世界中工作时最重要、最基础的数据结构。

如果你在过程式语言（如 Python）中使用过数组或列表，那么这里的一些概念你会觉得很熟悉，但 FP 处理列表的方式非常独特且强大。理解这种结构是掌握映射 (mapping)、过滤 (filtering) 和折叠 (folding) 等函数式算法的关键！

你将学到：

• 列表是如何定义和表示的。
• 头部 (Head) 和 尾部 (Tail) 的关键概念。
• 你可以对列表执行的核心操作。
• 列表如何作为参数用于递归函数定义中。

---

1. 列表的定义与表示

在函数式编程中，列表是相同类型值的序列。它们始终是有序的。

1.1 列表符号

列表通常使用方括号 ([ ]) 来表示。

• 整数列表示例：[7, 2, 1]
• 字符串列表示例：["Adam", "Ananya", "Ben"]

关键点： 与过程式编程中的数组不同，函数式列表通常被设计为不可变 (immutable)，这意味着一旦创建，就无法直接修改。如果你想要一个“修改后”的列表，你得创建一个新的！

1.2 空列表

空列表正如其名——一个不包含任何元素的列表。

• 空列表的符号表示非常简单：[]

---

2. 头部与尾部：解构列表

函数式列表处理中最核心的概念是：列表可以递归地拆分为两部分——头部 (Head) 和 尾部 (Tail)。这种技术在递归函数定义中会被不断使用。

2.1 连接（Head : Tail 结构）

任何非空列表都可以表示为其头部与尾部的连接，在 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]。

关键要点： 函数式列表操作旨在提取组件（头部、尾部）、检查属性（长度、空值）或构建新列表（连接）。

---

4. 函数中的模式匹配

在函数式编程中，列表经常以递归方式处理。为了简化这一过程，我们在定义函数时使用一种称为模式匹配 (Pattern Matching) 的技术。

4.1 将头部和尾部作为参数引用

当你定义一个接受列表作为输入的函数时，可以使用 (x:xs) 模式自动将列表拆分为头部和尾部。

• x 代表头部（第一个元素）。
• xs 代表尾部（剩余的列表）。

如果函数 sum 接收到列表 [8, 3, 2]：

函数内部的参数 (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

别担心，如果这看起来有点复杂！练习追踪这些步骤，重点关注列表如何在每次递归调用中缩短一个元素（即头部），直到到达空列表（基本情况）为止。