Writing functional programs

欢迎来到函数式编程：实践篇！

你好！你已经学习了函数式编程范式的理论基础（如定义域、陪域和一等公民对象）。现在，我们要进入令人兴奋的部分：编写实际的函数式程序。

本章重点介绍在函数式语言（如考试中使用的 Haskell）中编写代码时所使用的技术和工具。理解这些概念——特别是递归和高阶函数——将彻底改变你解决问题的思路！

如果觉得这比命令式编程（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. 高阶函数 (HOFs)

高阶函数（Higher-Order Function）是指接收另一个函数作为参数、返回一个函数作为结果，或两者兼有的函数。

高阶函数对于编写简洁且强大的函数式代码至关重要。你需要掌握三个主要的高阶函数：map、filter 和 fold (reduce)。

A. Map

map 高阶函数将指定的函数应用于列表中的每一个元素，并返回一个包含结果的新列表。原列表保持不变（这是实现函数式纯粹性的关键！）。

类比：如果你有一个价格列表 [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 高阶函数处理一个列表，生成一个仅包含原列表中满足特定条件（谓词函数）的元素的新列表。

类比：筛选联系人列表，只保留年龄超过 30 岁的人。

教学大纲示例：

执行 filter (<10) [15, 8, 20, 3]（其中 (<10) 为“小于 10”的条件）。

生成列表：[8, 3]

C. Fold (Reduce)

fold（有时称为 reduce）高阶函数通过重复应用组合函数，将列表中的值缩减为一个单一的值，其从一个初始值（累加器）开始。

类比：计算一系列测试成绩的总分。累加器从 0 开始，将每个分数逐个相加，从而将整个列表缩减为一个总和。

在 Haskell 中，根据应用的方向有两种版本，这对非交换运算（如减法）很重要：

• foldl (左折叠)：从最左侧项开始，向右处理。
• foldr (右折叠)：从最右侧项开始，向左处理。

示例：减法（顺序很重要！）
列表：[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 函数式编程中的列表

列表是函数式编程中的基本数据结构，常与高阶函数结合使用。

1. 定义和理解列表

• 列表存储一个值的序列。
• 列表通常使用方括号表示，例如 [7, 2, 1]。
• 空列表简单地表示为 []。

2. 表头（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。
• 构造空列表：直接使用 []。
• 追加项（连接）：使用 ++ 连接两个列表。
  示例： [1, 2] ++ [4, 5] 的结果为 [1, 2, 4, 5]。

快速复习：列表结构

Head (表头) = 单个元素。
Tail (表尾) = 元素列表。
Head 很容易找到。
Tail 需要更“Long”（更长时间，因为它总是一个列表）。

重点回顾：列表通过高阶函数和递归进行操作，核心在于将其拆分为单元素的表头和剩余的列表（表尾）。