函数式编程的基本思想与 cons 列表

1732 字约 6 分钟

2025-09-02

引言

函数式编程主张使用纯函数和不可变数据来构建程序。与逐步修改状态不同，我们把计算看成表达式的求值。下面通过一个小巧但强大的数据结构——cons 列表来介绍这些思想。

λ 演算与基本函子

λ 演算用最纯粹的函数与应用来刻画计算。变量可以被 λ 绑定，也可以作为自由变量存在，求值过程即是把实参替换形参。最常见的两个组合子（combinator）是恒等函子 I 和常量函子 K：

I = λx. x
K = λx. λy. x

计算 K I 可以直观看出它们的行为：

K I a = (λx. λy. x) I a
      → (λy. I) a
      → I
      → λz. z

K 会丢弃第二个参数，而 I 直接返回输入。借助这些最基本的函子就能表达对二元组的操作。

α、β、η 基础

λ 演算中的三个核心改写规则是：

α 变换：重命名绑定变量而不改变语义，例如 λx. x 与 λy. y 等价。
β 约简：通过替换来应用函数，比如 (λx. x + 1) 2 → 3。
η 变换：描述函数外延相等性，当 x 不在 f 中自由出现时，λx. f x 与 f 等价。

这些规则允许我们代数式地推导程序，判断表达式是否等价。

cons 列表

只用函数就能表示列表：

const NULL = undefined;
const I = x => x;
const K = x => y => x;
const cons = x => y => f => f(x)(y);

借助 K 和 I 组合子，我们可以取出列表的首尾元素：

const head = l => l(K);
const tail = l => l(K(I));

由于列表本质上就是函数，构造和拆解完全依赖函数应用。没有任何可变状态，每一步都会返回一个新的列表。

函子表示循环

在范畴论中，函子会在保持恒等与复合的同时把一个范畴映射到另一个范畴。在编程中，只要某个数据类型实现了满足定律的 map，它就是一个函子。map、fold 等高阶函数因此能把普通函数提升到结构化数据之上。我们描述“对每个元素做什么”，而由函子负责遍历。

const map = f => l => (l ? cons(f(head(l)))(map(f)(tail(l))) : NULL);
const fold = f => init => l => (l ? fold(f)(f(init)(head(l)))(tail(l)) : init);

fold 捕捉了循环的本质——每次递归处理一个结点直到列表为空。由于函子可以组合，这种方式能够扩展成一系列变换的流水线，控制流源自数据结构本身，而无需显式的状态修改。

使用函子实现递归

在没有命名的函数世界中，可以利用不动点组合子 Y 来表达递归：

Y = λf. (λx. f (x x)) (λx. f (x x))

Y g 展开为 g (Y g)，让 g 可以在不显式命名的情况下调用自身。配合 cons 与 fold，我们能够仅用函数编写如排序、过滤等递归算法。

泛型与组合

由于列表构造器本身就是函数，TypeScript 的泛型可以在几乎不增加语法复杂度的前提下对其建模：

type List<T> = (f: (h: T) => (t: List<T>) => unknown) => unknown;
const map = <A, B>(f: (a: A) => B) => (l: List<A>): List<B> =>
    (l ? cons(f(head(l)))(map(f)(tail(l))) : NULL);

类型变量 T 在定义之间穿梭，为我们提供静态保证，同时不影响底层的 λ 项。

构建复杂行为

在这些基础之上，我们可以逐层叠加出更复杂的工具：

const join = fold(concat)(NULL);              // 展平嵌套列表
const concatMap = f => l => join(map(f)(l));  // 先映射再展平
const zip = f => a => b =>                    // 结合两个列表
    (a && b ? cons(f(head(a))(head(b)))(zip(f)(tail(a))(tail(b))) : NULL);
const filter = f =>                           // 用 fold 实现过滤
    compose(reverse)(fold(a => v => (f(v) ? cons(v)(a) : a))(NULL));
const sort = f => l => {                      // 快速排序
    if (!l) return NULL;
    const h = head(l), t = tail(l);
    const l1 = filter(x => f(x)(h) <= 0)(t);
    const l2 = filter(x => f(x)(h) > 0)(t);
    return concat(sort(f)(l1))(cons(h)(sort(f)(l2)));
};

所有这些抽象都重用最初的 cons、head 与 tail 定义。控制流来自函数的组合，而非特殊语法。

示例：寻找 “最幸运” 的学生

为了展示这些函数式原语的力量，让我们考虑一个实际场景：处理学生考试成绩。我们将定义一些示例数据，并构建一个管道来找到及格分数最低的学生（在“勉强及格”的意义上“最幸运”的）。

首先，让我们定义数据结构和辅助函数：

const students = ["Alice", "Bob", "Charlie", "Diana"];
const marks = ["85", "92", "78", "88"];

const pass = score => score >= 80;
const compareMarks = (a, b) => a.score - b.score; // 升序
const student = name => ({ name });
const name = obj => obj.name;

// 更多复杂行为的辅助函数
const average = l => fold((sum, x) => sum + x)(0)(l) / length(l);
const maxBy = f => l => fold((max, x) => f(x) > f(max) ? x : max)(head(l))(l);
const length = fold(x => acc => acc + 1)(0);

下面的管道把学生与成绩拉链组合，筛选出及格者，按分数排序并取出最低的及格分：

const luckiestStudent = pipe(
    marks,
    fromArray,
    map(Number),
    zip(student)(fromArray(students)),
    filter(pass),
    sort(compareMarks),
    head,
    name,
);

为什么这些模式很有用

这些函数式模式提供了几个优势：

不可变性：像 cons 列表这样的数据结构一旦创建就无法修改，防止意外副作用，使代码更可预测。
可组合性：函数可以使用 pipe 或函数组合轻松组合，允许从简单部分构建复杂行为。
可测试性：没有副作用的纯函数更容易进行单元测试和推理。
并行化：由于没有共享的可变状态，操作更容易并行化。
表达力：声明式代码读起来就像问题陈述，使其自文档化。

如此复杂的工作流完全由小巧、纯粹的函数拼装而成，不需要可变状态或显式循环。

总结

cons 列表展示了函数式编程的优势：数据不可变，行为由声明式的函数描述，循环与递归都通过函数应用自然地涌现。从 I、K 这样的微小组合子出发，我们便能构建出丰富的递归结构，并借助泛型把这些思想扩展到拥有强大静态保证的大型系统。