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

引言

函数式编程主张使用纯函数和不可变数据来构建程序。与逐步修改状态不同，我们把计算看成表达式的求值。下面通过一个小巧但很有表达力的数据结构——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 或函数组合轻松组合，允许从简单部分构建复杂行为。
可测试性：没有副作用的纯函数更容易进行单元测试和推理。
并行化：没有共享可变状态，可以少掉一类协调错误；但真正的并行执行仍然取决于 runtime 和数据表示。
可读性：pipeline 会直接暴露每一步 transformation。

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

总结

cons 列表能很紧凑地展示函数式编程的习惯：数据不可变，行为通过函数组合建立，递归也可以不依赖可变循环状态来表达。从 I、K 这样的微小组合子出发，我们可以构造递归结构，再借助泛型让这些结构在扩展时保持类型约束。

引言