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\)（读作“f 之后的 g”或“g 与 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

这三个函数是函数式编程中的基石，常用于处理列表等数据结构。你必须能够识别并跟踪它们的使用方式（考试中常使用 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]}\)（在较小的列表上调用自身）。