Reading 17: 递归数据类型（Recursive Data Types）

目录 · ← l16 · l18 →

Reading 17: 递归数据类型（Recursive Data Types）

说明：本讲 sp22 原版使用 TypeScript，本笔记按用户要求提供 Java 代码示例；类型/API 与 sp21（6.031 Java 版）原文保持一致。

概述

本讲讨论递归数据类型（recursive data type）：一种用自身来定义自身的数据类型，正如递归函数用自身来定义自身一样。我们要回答四个问题：如何读写数据类型定义（datatype definition）；如何为这种类型的每个 variant 分别实现操作；不可变列表 ImList<E> 这个经典例子长什么样；以及写 ADT 时应当遵循的「配方（recipe）」。核心设计原则是：把操作的规格声明在抽象接口上，把操作的实现按 variant 递归地分散到各个具体类里（这一模式有时被戏称为 interpreter pattern），从而使「数学定义」到「代码」的转换几乎是机械的。

它与三大目标的关系如下。Safe from bugs：递归数据类型没有下标、没有可变状态、没有 null 哨兵，Cons 与 Empty 分派由动态派发（dynamic dispatch）而非运行期类型检查完成，因此整类越界与空指针 bug 在类型层面被消除。Easy to understand：写好的代码「little more than the definition, with some semicolons to placate the compiler」——size(Empty) = 0、size(Cons(elt, rest)) = 1 + size(rest) 与 Java 实现几乎逐字对应，阅读者可以像读数学定义一样读代码。Ready for change：只要隐藏具体 variant、不违反表示不变量的前提下，内部表示（加缓存字段、改用数组支撑 get、换成别的实现）都可以自由替换，而客户端的规格不变。

核心概念与设计原则详解

递归数据类型与数据类型定义（Recursive Data Type & Datatype Definition）

• 定义与目的：若一个数据类型在自己的定义中出现在右端（作为某个字段的类型），它就是递归数据类型。数据类型定义则把「抽象类型 = 若干 variant 的并集」这一结构写清楚，用来思考抽象类型、特别是递归抽象类型。
• 直观解释（”它是什么？”）：想象俄罗斯套娃：一个套娃里面可以装另一个套娃，也可以什么都不装。ImList 就是这样——一个 Cons 里装着另一个 ImList，而最里层是一个什么也不装的 Empty。递归函数有 base case 与 recursive step，递归数据类型同样有 base case（Empty）与 recursive step（Cons）。
• 关键规则与最佳实践：
  • 数据类型的正式构成：左边是抽象数据类型，右边是它的表示（representation，也称具体数据类型）；表示由若干 variant（变体） 用并集运算符 + 组合而成；每个 variant 是「类名 + 零个或多个字段」，字段写成 名字:类型。
  • ImList<E> = Empty + Cons(elt:E, rest:ImList<E>) 表示：ImList 的值要么由无字段的 Empty 对象表示，要么由字段为「一个元素 elt 与一个 ImList 类型的 rest」的 Cons 对象表示。
  • 任何值都可以写成项（term）：[0, 1, 2] 写成 Cons(0, Cons(1, Cons(2, Empty)))。整个无限集合可以从 base case Empty 出发，反复应用 Cons 生成出来。
  • 把递归数据类型定义作为注释写在接口里（sp21 原文用 // Datatype definition:），这样读接口的人立刻能看到全貌。
  • 这种「variant 并集」在函数式编程中叫代数数据类型（algebraic data type）；Haskell/ML 用另一套语法，但思想一致。
  • 常见的递归数据类型还有二叉树 Tree<E> = Empty + Node(e:E, left:Tree<E>, right:Tree<E>)、可选值 Optional<E> = None + Some(value:E)、布尔公式 Formula = Variable(name:String) + Not(formula:Formula) + And(left:Formula, right:Formula) + Or(left:Formula, right:Formula)。
  • 定义必须保证能构造出值：V = F(z:int, v:V) + G(z:int, v:V) 无法构造任何实例（没有 base case），而 W = K(n:int) + L(n:int, m:W) 虽然递归但没有表示空序列的 variant，因此不能像 X = M + N(here:int, there:X) 那样当作列表使用。

不可变列表与四个基本操作（Immutable Lists: empty/cons/first/rest）

• 定义与目的：ImList<E> 是递归数据类型的经典例子，它提供不可变的列表抽象，其不可变性不仅带来安全性，还带来共享（sharing）的可能，从而减少内存占用与复制时间。
• 直观解释（”它是什么？”）：它不是数组，也不是可变链表，而更像一条「焊死了的链条」：每次添加元素都是在前端接上新的一节，原来的链条一动不动，别人手中的链条也不会变。
• 关键规则与最佳实践：
  • 四个基本操作：empty: void → ImList（返回空列表）、cons: E × ImList → ImList（在另一个列表前端加入一个元素并返回新列表）、first: ImList → E（返回第一个元素，要求非空）、rest: ImList → ImList（返回除第一个元素外的所有元素，要求非空）。
  • 这四个操作历史悠久：在 Lisp/Scheme 中被称为 nil、cons、car、cdr；函数式编程中 first/rest 也常叫 head/tail。
  • 它们之间的根本关系是 first(cons(elt, list)) = elt 与 rest(cons(elt, list)) = list——cons 组合起来的，由 first 和 rest 拆开。
  • cons 加在前端，因此 nil.cons(2).cons(1).cons(0) 的结果是 [0, 1, 2]：后调用者位于更前面。
  • 共享结构：ImList<Integer> y = x.rest().cons(4); 得到的 [4, 1, 2] 与 x（[0, 1, 2]）共享子列表 [1, 2] 的那份表示，内存中只有一份，两个引用都指向它；因为列表不可变，这种别名（aliasing）完全安全。
  • 注意只有尾部能被共享：如果两个列表前缀相同而后缀不同，前缀必须各自存储（因为每个 Cons 只有一个 rest 字段，无法让两个不同的后缀共享同一个 Cons 前缀）。

两个实现类协作实现一个抽象类型（Empty and Cons Cooperate）

• 定义与目的：ImList 的表示由 Empty 与 Cons 两个类合作构成：它们不是 ArrayList/LinkedList 那种「同一抽象的两个可替换表示」，而是同一个表示的两个 variant，缺一不可。
• 直观解释（”它是什么？”）：像拼装玩具的两半——「空槽」与「一节车厢」——只有合起来才能拼出任意长度的列车；而 ArrayList 与 LinkedList 更像是两种不同材质造出的同型列车，任选其一即可。
• 关键规则与最佳实践：
  • 接口 public interface ImList<E> 声明所有操作；Empty<E> 与 Cons<E> 各自实现同一批操作，但语义按 variant 不同。
  • 不要在客户端代码里 new Empty<>()：那会牺牲表示独立性（representation independence），因为客户端必须知道 Empty 这个类。正确做法是用静态工厂 ImList.empty()（Java 8+ 允许接口中的静态方法），并进一步把 Empty/Cons 声明为包私有（package-private），让包外的类根本看不到它们。
  • ImList 是接口：new ImList() 被 Java 禁止，因为它没有自己的对象值，也没有构造器。
  • 任何 ADT 的规格都不能谈论 rep。递归 ADT 的具体 variant 就是它的 rep，因此规格中绝不能出现 Empty、Cons 这些名字。例如 isEmpty 的规格是「当且仅当本列表不含元素时返回 true」，而不是「当且仅当 this 是 Empty 的实例时返回 true」。
  • first/rest 的规格写着「requires the list to be nonempty」；Empty 的实现应当快速失败（fail fast），抛出 UnsupportedOperationException 之类的异常，而不是返回 null 或某个默认值。

递归数据类型的操作：每个 variant 一个 case（Functions with One Case per Variant）

• 定义与目的：这种「把类型看成 variant 并集」的思考方式之所以有吸引力，不只是因为它能处理列表、树这类递归且无界的结构，还因为它提供了一个描述操作的方便途径：每个 variant 一个 case 的函数。
• 直观解释（”它是什么？”）：像按食谱做菜：先写「空列表怎么做」（size(Empty) = 0），再写「非空列表怎么做」（size(Cons(elt, rest)) = 1 + size(rest)），两步合起来就完整规定了操作的含义，也天然对应到接口方法与两个实现类。
• 关键规则与最佳实践：
  • 实现一个操作的固定套路：① 在抽象接口里声明该操作；② 在每个具体 variant里递归地实现它。
  • 用一系列「归约步骤（reduction steps）」来心算递归：size(Cons(0, Cons(1, Empty))) = 1 + size(Cons(1, Empty)) = 1 + (1 + size(Empty)) = 1 + (1 + 0) = 2。
  • 常用操作的函数式定义：
    • isEmpty(Empty) = true；isEmpty(Cons(elt, rest)) = false。
    • contains(Empty, e) = false；contains(Cons(elt, rest), e) = (elt = e) or contains(rest, e)。
    • get(Empty, n) = undefined；get(Cons(elt, rest), n) = if n = 0 then elt else get(rest, n - 1)。
    • append(Empty, list2) = list2；append(Cons(elt, rest), list2) = cons(elt, append(rest, list2))。
    • reverse(Empty) = empty()；reverse(Cons(elt, rest)) = append(reverse(rest), cons(elt, empty()))。
  • 注意 reverse 的这个递归定义产生的实现性能很差：其代价与列表长度的平方成正比（每次 append 都要走一遍左前缀），需要时可以用迭代方式重写。
  • 实现 contains 时判等要用 equals（Reading 15），不要用 ==；否则对 String、Integer 之外的引用类型会得到错误结果。

递归类型的抽象函数与表示不变量（AF and RI for Recursive Types）

• 定义与目的：抽象函数（abstraction function, AF）说明「rep 的一个取值代表哪个抽象值」，表示不变量（representation invariant, RI）说明「哪些 rep 取值是合法的」。对递归数据类型，AF/RI 必须按 variant 分别写，因为每个 variant 的 rep 字段不同。
• 直观解释（”它是什么？”）：AF 是「内部零件 → 外部含义」的翻译表，RI 是「内部零件必须满足的组装规则」。Empty 的 AF 只说一件事：它代表空列表；Cons 的 AF 要说清「第一个元素是 elt，其余元素是 rest 所代表的列表」。
• 关键规则与最佳实践：
  • Empty：AF() = the empty list []；RI: true（没有需要约束的字段）。注意 AF(first) = an empty list 这样的写法是错的，因为 Empty 没有名为 first 的字段。
  • Cons：AF(elt, rest) = 第一个元素是 elt、其余元素是 rest 所代表列表的那个列表。像「AF(elt, rest) = a non-empty list」这种说法信息量不足（没有说明哪个元素在前），而「AF(elt, rest) = a two-element list where the first element is elt and the second element is rest」则是错误的（把 rest 说成了元素，而它其实是一个列表）。
  • Cons 的 RI：elt != null、rest != null（以及实现缓存时新增的条款，见下文）。
  • 规格中绝不提及 variant，AF/RI 中也绝不混入抽象值以外的承诺。
  • 因为 cons、first、rest 都返回或接收 ImList 而非具体类，AF 的递归描述才能自然地把「子列表」交给下一层的 AF 处理。

表示独立性、表示暴露与受益人式修改（Rep Independence, Rep Exposure, Beneficent Mutation）

• 定义与目的：表示独立性意味着客户端只依赖抽象操作，实现可以自由更换；表示暴露意味着内部 rep 的引用泄漏给了客户端，从而可能被破坏。受益人式修改（beneficent mutation）则是一种特殊技巧：不可变类型内部可以有可变的 rep，只要状态变化不改变对象所表示的抽象值。
• 直观解释（”它是什么？”）：前两者像「只提供柜台服务，不让顾客进后厨」；受益人式修改则像「餐厅把算好的账单金额贴在墙上做备忘」——贴与不贴，顾客看到的账单一模一样。
• 关键规则与最佳实践：
  • ImList 的实现确实保持了表示独立性：Empty 构造器被 ImList.empty() 隐藏，客户端不需要也不应该直接使用 Empty/Cons 构造器。
  • 因此实现有很大的自由度：可以给 Cons 加 size 字段，甚至可以在内部加一个数组让 get() 变快（代价是空间），这些取舍由实现者决定。
  • 像 isEmpty 这样的操作不会破坏表示独立性：它的规格是抽象的（「列表是否不含元素」），任何实现方式（递归的 Empty/Cons、数组支撑、可变链表）都能满足。
  • Cons.rest() 返回内部列表的引用，看似是表示暴露——但因为内部列表不可变，任何人都无法通过它威胁 Cons 的不变量（既不能破坏不可变性，也不能让缓存的 size 失效）。
  • 引入缓存字段时必须同步更新 RI，明确写出缓存正确性条款，例如 size > 0 implies size == 1 + rest.size()。

哨兵对象与 null 的对比（Sentinel Objects vs null）

• 定义与目的：用一个真实对象（Empty）而不是 null 引用去表示数据结构的 base case 或端点，这一设计模式称为哨兵对象（sentinel objects）。它的巨大优势在于「它像数据类型中的普通对象一样工作，因此可以在它上面调用方法」。
• 直观解释（”它是什么？”）：就像队列里放一个「空位」的牌子而不是把这一格挖掉——你依然可以对牌子做操作，不必每次都先判断「这里有没有东西」。
• 关键规则与最佳实践：
  • 若用 null 表示空列表，代码里就会充满 if (list != null) n = list.size(); 这类检查，它们污染代码、掩盖意图、而且容易忘记写。
  • 有哨兵对象时可以直接写 n = list.size();，对空列表也永远有效。
  • 「把 null 值赶出你的数据结构，你的日子会好过得多」——这条规则与 Reading 15（相等性）中对 equals(null) 处理的要求、以及 Reading 07（设计规格）中「避免用 null 表示缺失」的建议一脉相承。
  • 需要表达「可能没有值」时，用 Optional<E> 这类显式类型（其数据类型定义为 Optional<E> = None + Some(value:E)），而不是 null。

静态类型与实际类型；instanceof 反模式（Declared Type vs Actual Type）

• 定义与目的：编译期每个变量有一个声明类型（declared type，也叫静态类型、编译期类型），运行期每个对象有一个由构造器赋予的实际类型（actual type，也叫动态类型、运行期类型）。理解这个区分，才能理解动态派发如何让我们「按 variant 分派实现」。
• 直观解释（”它是什么？”）：变量的声明类型像「合同上写的职位」，对象的实际类型像「这个人实际会做什么」。ImList<String> words2 = ImList.empty(); 中变量的声明类型是 ImList，而它指向的对象的实际类型是 Empty。
• 关键规则与最佳实践：
  • String hello = "Hello" 中 hello 的声明类型是 String、实际类型也是 String（对基本类型与不可变值类型，两者一致）；List<String> words1 = new ArrayList<>() 中变量的声明类型是 List、实际类型是 ArrayList。
  • 动态派发使客户端调用 size() 时自动执行 variant 对应的实现，这就是我们「免费」得到按 variant 分派的原因。
  • 不要用 instanceof 检查运行期类型。课程明确说：instanceof 是运行期类型检查，比静态类型检查既更不安全（less safe from bugs）也更难适应变化（less ready for change）。if (this.rest instanceof Empty) { return this.first; } 这样的写法是反模式。
  • 当 instanceof 看起来很诱人时，正确反应是回头重新思考问题：Cons 并不关心 rest 的表示，只关心它的抽象值。如果类型提供的操作不够用，就给类型增加操作，而不是去窥探 rep。
  • 唯一可能「least-bad」的例外是为不可变类型定义 equalValue（Reading 15）：由于客户端只知道 ImList，需要在接口上声明 equalValue(ImList<E>)，此时或者用 size() + get() 等观察者操作在不看 variant 的前提下判等（笨重但完全在抽象屏障之上，更安全），或者检查运行期类型（优雅、递归结构与数据同形，但引入了运行期类型检查的风险）。

不可变链表的性能特征与回溯搜索（Performance & Backtracking）

• 定义与目的：不可变列表的共享结构决定了它的性能画像；理解这一点，才能在「何时用 ImList、何时用数组或可变结构」上做出正确取舍，并理解为什么回溯搜索特别适合不可变结构。
• 直观解释（”它是什么？”）：cons 像在前端接一节车厢，代价恒定；而 append 像要把整列车拆开重接到另一列车前面，代价与左列表长度成正比。共享则像两列火车共用同一段尾轨。
• 关键规则与最佳实践：
  • cons、first、rest 都是 O(1)；contains 是 O(n)；get(i) 是 O(i)；朴素的 size() 是 O(n)。
  • append 是 O(this 的长度)：它复制左列表的「脊柱」，而右列表被完整共享（append(Empty, list2) = list2 直接返回 list2 本身，这是共享的直接体现）。
  • 按递归定义实现的 reverse 是 O(n²)，因为每一步 append 都要走一遍前缀；需要时改用迭代（用一个累加器从前往后 cons）可降到 O(n)。
  • 给 size 加缓存可把后续查询降到 O(1)，这是受益人式修改的典型用法；因为 Cons 的 size 永远不为 0，sp21 用 0 作为「尚未计算」的哨兵值，并在 RI 中写明 size >= 0 与 size > 0 implies size == 1 + rest.size()。
  • 回溯搜索（如布尔公式的可满足性问题）是这类列表的绝佳应用：搜索空间中的每一步只需在前端 cons 一次就能共享此前全部信息；回溯时「停止使用当前状态」即可，而之前的状态仍然被引用着，不需要像可变 Map 那样逐个撤销绑定。
  • 但「完全没有共享的不可变结构」并不好：如果每一步都要完整复制环境，空间开销会随步数平方增长，因为你必须保留路径上所有历史环境以便回退。
  • 用不可变数据结构实现的搜索立刻可并行：可以把多条路径分给多个处理器，不必担心它们在共享可变结构上互相踩踏（见 Reading 21 并发）。

代码示例与对比分析

场景 1：空列表上的 first()/rest()——快速失败而不是返回默认值

❌ 错误代码

public class Empty<E> implements ImList<E> {
    public Empty() {
    }
    public ImList<E> cons(E elt) {
        return new Cons<>(elt, this);
    }
    public E first() {
        return null;          // 错误：用 null 掩盖「不允许调用」
    }
    public ImList<E> rest() {
        return this;          // 错误：返回一个看似合理的空列表
    }
}

【错误代码的问题】

1. 违反规格。first/rest 的规格写着「requires the list to be nonempty」，在空列表上调用是调用者的 bug；返回 null/this 把调用者的错误伪装成正常结果，bug 会沿着调用链继续传播到很远的地方才以 NullPointerException 或错误答案的形式爆发。
2. first() 返回 null 之后，调用点往往写成 if (list.first() == null) ...，于是「空列表」与「首元素恰好是 null」两种完全不同的情况被混为一谈——这正是 Reading 15 关于 equals(null) 所警告的语义混淆。
3. rest() 返回 this 让 rest().rest().rest() 在任何列表上都永远不报错，掩盖了下标越界式的逻辑错误。

✅ 正确代码

public class Empty<E> implements ImList<E> {
    // Abstraction function:
    //   AF() = the empty list []
    // Representation invariant:
    //   true
    // Safety from rep exposure:
    //   no fields at all

    public Empty() {
    }
    public ImList<E> cons(E elt) {
        return new Cons<>(elt, this);
    }
    public E first() {
        throw new UnsupportedOperationException("first() of an empty list");
    }
    public ImList<E> rest() {
        throw new UnsupportedOperationException("rest() of an empty list");
    }
}

【为什么这样更好】 明确地把「前置条件被违反」这一事实立刻暴露出来：异常在错误发生的现场抛出，栈轨迹直接指向出错的那一行，调试成本极低（Reading 09、Reading 13）。同时 Empty 与 Cons 的分工变得清晰：Empty 只负责「空」这一 variant 的语义，其余全部拒绝。

【代码对比解说】 两种实现都「通过编译」、都能满足 size()、isEmpty() 这些不需要 first() 的操作；差别只在违反规格时的表现。这里体现了一条通用原则：对违反前置条件的输入，要么用未检查异常快速失败，要么用规格明确允许的默认行为；绝不要返回一个语义含糊的值。Empty.rest() 返回 this 看起来「友好」，实际上破坏了 first(rest(x)) 与 cons/first/rest 的基础等式所隐含的结构信息——它让空列表变成了一个「无限长的空列表」，与数据类型定义 ImList<E> = Empty + Cons(elt:E, rest:ImList<E>) 所刻画的有限结构不符。

【设计原则透视】 Empty 的 AF 是 AF() = the empty list []，RI 是 true：它没有任何字段，因此没有可违反的约束。抛出异常的实现完全遵守这两条；而返回 null 的实现在 AF 上已经说不通——Empty 的抽象值只能是空列表本身，不能是「没有首元素的某个值」。从抽象屏障看，客户端只需知道 first 要求非空，而不需要知道 Empty 的存在（Empty 应当被声明为包私有，并通过 ImList.empty() 这个静态工厂暴露），因此这里抛出的是标准库异常而不是自定义类型，以免泄漏 rep 细节。

场景 2：用 null 表示空列表——哨兵对象 Empty 才是正解

❌ 错误代码

public class ImListOps {
    /**
     * @param head first element, may be null to mean "no elements"
     * @param tail the rest of the list, may be null
     * @return the size of the list
     */
    public static int size(Node head, Node tail) {
        int n = 0;
        Node cur = head;
        // 错误：用 null 表示空列表，于是每处使用都要判空
        while (cur != null) {
            n = n + 1;
            cur = cur.next;   // next 为 null 表示结束
        }
        if (tail != null) {
            // 忘记处理 tail 的情况也时有发生
        }
        return n;
    }
}

【错误代码的问题】

1. 每一处使用都要写 != null 判断：代码被判空语句淹没，真正的含义（「求列表长度」）被掩盖，而且很容易漏写一处，漏写就是空指针异常。
2. null 的含义被重载：它既表示「列表结束」，又可能表示「调用者传了 null 参数」，两种语义无法区分，规格里只能写「may be null」，把不确定性推给所有调用者。
3. 无法在空列表上调用方法，因此所有操作都要么是静态工具方法、要么在入口处特判，无法真正做到「操作属于类型」（list.size() 这样的写法根本不可能实现）。

✅ 正确代码

public interface ImList<E> {
    // Datatype definition:
    //   ImList<E> = Empty + Cons(elt:E, rest:ImList<E>)

    /**
     * @return an empty list
     */
    public static <E> ImList<E> empty() {
        return new Empty<>();
    }

    /**
     * @param elt element to add
     * @return a new list with elt at the front of this list
     */
    public ImList<E> cons(E elt);

    /**
     * @return the first element; requires this list to be nonempty
     */
    public E first();

    /**
     * @return the list of all elements except the first;
     *         requires this list to be nonempty
     */
    public ImList<E> rest();

    /**
     * @return the number of elements in this list
     */
    public int size();
}

【为什么这样更好】 空列表是一个真实对象（Empty 的实例），因此可以像任何列表一样接收 size()、isEmpty()、cons() 等调用，客户端代码里彻底不需要判空分支：n = list.size(); 永远有效。null 从此退出这个数据类型的表示，E 的取值也不必再被 null 污染，AF/RI 得以简单清晰地陈述。

【代码对比解说】 这是「哨兵对象」模式的标准收益：把「没有元素」这一抽象概念用对象表达，而不是用语言的空引用表达。课程原文的论证很直接——若空列表用 null 表示，代码就会充满 if (list != null) n = list.size(); 这样的测试，它们扰乱代码、模糊含义、且容易忘记；有了哨兵对象就可以写 n = list.size();。同理，static 工具方法把列表操作变成了「外部函数」，违背了面向对象的封装；而把方法放进接口后，Empty 与 Cons 各自实现自己的那一份语义，动态派发替我们完成分派。

【设计原则透视】 这直接关系到 AF/RI：Empty 的 AF 是 AF() = the empty list []，它必须是一个对象才能成为 ImList<E> 的一个合法值；如果空列表是 null，那么 ImList 的抽象值集合中有一部分根本无法用合法对象表示，RI 也只能写成「this == null 或 …」，这是设计上的失败。从 Reading 10（抽象数据类型）的角度看，把 size 声明在接口上意味着它成为类型的操作而不是外部过程，客户端只依赖抽象；从 Reading 12（接口、泛型与枚举）的角度看，static <E> ImList<E> empty() 中的 E 是方法自己的类型参数（静态方法看不到实例的类型参数），读作「对任意 E，empty() 返回一个 ImList<E>」。

场景 3：last() 的实现——不要用 instanceof 窥探 variant

❌ 错误代码

public class Cons<E> implements ImList<E> {
    private final E elt;
    private final ImList<E> rest;

    public Cons(E elt, ImList<E> rest) {
        this.elt = elt;
        this.rest = rest;
    }
    public ImList<E> cons(E elt) { return new Cons<>(elt, this); }
    public E first() { return elt; }
    public ImList<E> rest() { return rest; }
    public int size() { return 1 + rest.size(); }

    /**
     * @return the last element; requires this list to be nonempty
     */
    public E last() {
        if (this.rest instanceof Empty) {   // 错误：运行期类型检查
            return this.first();
        }
        return this.rest.last();
    }
}

【错误代码的问题】

1. instanceof 是运行期类型检查，比静态类型检查既更不安全、也更难适应变化：只要有人新增第三个 variant（例如一个共享后缀的 Cons 或数组支撑的 Chunk），这里的分支就会静默失效，而编译器不会给出任何提示。
2. 它把 Cons 与 Empty 的具体表示焊死在一起，破坏了表示独立性与「两个类合作实现抽象类型」的设计：Cons 本应只依赖 ImList 的抽象操作，却开始关心 rest 的 rep。
3. 由于 last() 只声明在 Cons 上而接口中没有声明，客户端拿到 ImList<E> 类型时无法调用它，只能做向下转型，进一步引入运行期类型判断。

✅ 正确代码

public interface ImList<E> {
    // ... empty(), cons(), first(), rest(), size() ...

    /**
     * @param index index into the list, requires 0 <= index < size()
     * @return the element at that index
     */
    public E get(int index);

    /**
     * @return the last element; requires this list to be nonempty
     */
    public E last();
}

public class Empty<E> implements ImList<E> {
    // ...
    public E get(int index) {
        throw new IndexOutOfBoundsException("empty list has no elements");
    }
    public E last() {
        throw new UnsupportedOperationException("last() of an empty list");
    }
    public int size() { return 0; }
    public boolean isEmpty() { return true; }
}

public class Cons<E> implements ImList<E> {
    private final E elt;
    private final ImList<E> rest;
    // ...
    public E get(int index) {
        // get(Cons(elt, rest), n) = if n = 0 then elt else get(rest, n - 1)
        return (index == 0) ? elt : rest.get(index - 1);
    }
    public E last() {
        return get(size() - 1);   // 只用抽象操作，不看 variant
    }
    public int size() { return 1 + rest.size(); }
    public boolean isEmpty() { return false; }
}

【为什么这样更好】 last() 被实现在抽象层之上：它通过 size() 与 get() 这两个已经规定好的抽象操作表达「最后一个元素」的含义，完全不触及任何具体 variant。因此无论 rest 内部是 Empty、Cons 还是未来某种新 variant，这段代码都继续正确——这正是「规格写在接口、实现随 variant 分派」带来的可修改性。同时把 last/get 声明在接口上，客户端无需向下转型即可使用。

【代码对比解说】 两种写法的递归结构与数据的递归结构不同：instanceof 版本是「边递归边窥探表示」，抽象操作版本是「把递归下放到 get/size，last 只做组合」。课程原文的建议是：每当 instanceof 显得诱人时，就退一步重新思考——Cons 不关心 rest 的表示，只关心其抽象值；如果现有操作不足以表达需求，就给类型增加操作（这里增加了 size()、get()、isEmpty()、contains()、append()、reverse() 这类通用操作），而不是去检查运行期类型。代价是 last() 现在需要先算 size()（O(n)）再 get()（O(n)），如果不加缓存则是 O(n) 的两次遍历；若性能敏感，可以给 Cons 加 size 缓存（见场景 5），或者改用带累加器的递归实现——但绝不回到 instanceof。

【设计原则透视】 这一组对比精准地展示了 Reading 11（抽象函数与表示不变量）中的抽象屏障（abstraction barrier）：Cons 既是 ImList 的实现者，又是其（递归的）客户端，作为客户端它必须只使用接口承诺的操作。用 instanceof 等于越过屏障去看 rep，一旦 rep 改变（新增 variant、把 Empty 换成单例、把链式结构换成数组块），越过屏障的代码立刻失效；而站在抽象层之上的实现只依赖规格，规格不变则代码不变。这也是 isEmpty 的规格必须是抽象的（「不含元素」）而不能是「是 Empty 的实例」的原因。

场景 4：为让 append 变快而就地修改 rest——破坏共享的致命诱惑

❌ 错误代码

public class Cons<E> implements ImList<E> {
    private final E elt;
    private ImList<E> rest;      // 错误：不是 final，可以被就地改写

    public Cons(E elt, ImList<E> rest) {
        this.elt = elt;
        this.rest = rest;
    }
    public ImList<E> cons(E elt) { return new Cons<>(elt, this); }
    public E first() { return elt; }
    public ImList<E> rest() { return rest; }
    public int size() { return 1 + rest.size(); }

    /**
     * @param other list to append to this list
     * @return list with the elements of this followed by the elements of other
     */
    public ImList<E> append(ImList<E> other) {
        // 错误：为了「原地」拼接而改写自己的 rest 字段
        this.rest = this.rest.append(other);
        return this;
    }
}

【错误代码的问题】

1. 破坏不可变性，并污染所有共享者：ImList<Integer> x = nil.cons(2).cons(1).cons(0);（[0,1,2]）与 ImList<Integer> y = x.rest().cons(4);（[4,1,2]）共享子列表 [1,2]；若对 x 调用一次 append，y 的内容会追溯性地改变，此前创建的所有引用的含义全部失效——这类 bug 极难定位。
2. 使缓存字段（如 size）失效，违反 RI 中 size == 1 + rest.size() 的条款；一旦并发使用（Reading 21、Reading 23），rest 的读写还会产生数据竞争。
3. 违反 append 的规格语义：规格承诺返回「this 的元素后接 other 的元素」，并未允许修改 this；客户端合理地假设 x 不变，程序其余部分因此崩溃。

✅ 正确代码

public class Cons<E> implements ImList<E> {
    private final E elt;
    private final ImList<E> rest;   // 正确：final，永不改写

    // Abstraction function:
    //   AF(elt, rest) = the list whose first element is elt,
    //                   followed by all the elements of rest
    // Representation invariant:
    //   elt != null, rest != null
    // Safety from rep exposure:
    //   all fields are private and final; E and ImList<E> are immutable,
    //   so exposing this rep through rest() cannot threaten the invariant

    public Cons(E elt, ImList<E> rest) {
        this.elt = elt;
        this.rest = rest;
    }
    public ImList<E> cons(E elt) { return new Cons<>(elt, this); }
    public E first() { return elt; }
    public ImList<E> rest() { return rest; }
    public int size() { return 1 + rest.size(); }

    /**
     * @param other list to append to this list
     * @return a new list with the elements of this followed by those of other
     */
    public ImList<E> append(ImList<E> other) {
        // append(Cons(elt, rest), other) = cons(elt, append(rest, other))
        return new Cons<>(elt, rest.append(other));
        // 等价写法：return rest.append(other).cons(elt);
    }
}

public class Empty<E> implements ImList<E> {
    // ...
    public ImList<E> append(ImList<E> other) {
        // append(Empty, other) = other   —— 直接返回 other，实现完整共享
        return other;
    }
}

【为什么这样更好】 append 是非破坏性的：它复制左列表的「脊柱」（每一个 Cons 换成一个新 Cons），而把右列表 other 原封不动地接在末尾——Empty.append(other) 直接返回 other 这一行就是共享的证明。于是所有既有列表保持不变，共享结构继续安全，RI 与缓存都成立。注意 new Cons<>(elt, rest.append(other)) 与 rest.append(other).cons(elt) 是等价的正确写法，而 new Cons<>(other, rest.append(elt)) 把参数顺序弄反（既类型错误又语义错误：cons 是「把元素放在前端」，不是「把列表放在前端」）。

【代码对比解说】 这一组的核心是共享与可变的冲突：不可变列表的性能优势正是建立在结构共享之上，而就地修改会从根上摧毁这一前提。课程原文说得很清楚：共享意味着更少的内存与更少的复制时间；而共享之所以安全，完全依赖不可变性——「this aliasing is perfectly safe because the list is immutable」。一旦放弃不可变性，别名就从「优化」变成了「定时炸弹」。性能上也要算清楚账：append 的代价是 O(this 的长度)，无法靠就地修改变成 O(1)（除非引入 Seq/差分列表之类的结构，那属于另一层设计）。

【设计原则透视】 从 RI 的角度看，把 rest 改成非 final 并允许改写，等于放弃了「所有 Cons 的 rest 字段在其生命周期内恒定」这一条隐含不变量，而这条不变量正是 size 缓存正确、first/rest 等式成立的基础。从 Reading 08（不可变性）的角度看，这正是「不可变类型必须防御性地不泄漏可变 rep」的另一种表现：这里不是泄漏，而是自己内部破坏；结论相同——不可变类型的字段应当 private final。从 Reading 21/23 的角度看，可变 rep 还需要同步机制，而不可变 + 共享完全不需要，这也是课程把「回溯搜索用不可变列表」当作范例的原因。

场景 5：给 size() 加缓存——受益人式修改必须同步更新 RI

❌ 错误代码

public class Cons<E> implements ImList<E> {
    private final E elt;
    private final ImList<E> rest;
    public int size = 0;   // 错误：public 且可变，RI 没有任何说明

    public Cons(E elt, ImList<E> rest) {
        this.elt = elt;
        this.rest = rest;
    }
    public ImList<E> cons(E elt) { return new Cons<>(elt, this); }
    public E first() { return elt; }
    public ImList<E> rest() { return rest; }

    public int size() {
        if (size == 0) size = 1 + rest.size();
        return size;
    }
}

【错误代码的问题】

1. size 是 public 的可变字段，客户端可以写 cons.size = -5; 或直接读到一个尚未计算的 0，于是「size() 返回列表长度」这一抽象承诺被彻底破坏——典型的表现暴露。
2. 缓存的使用约定（0 表示「尚未计算」、size 要么为 0 要么等于 1 + rest.size()）只存在于作者脑中，RI 未文档化，后续维护者（哪怕是同一个人几个月后）无法判断哪些操作会更新它、哪些不变式必须保持。
3. 若有人把 Cons 的 size 传给外部代码或做序列化，就必须连同「缓存是否为 0」的内部状态一起解释，抽象与表示的边界变得模糊。

✅ 正确代码

public class Cons<E> implements ImList<E> {
    private final E elt;
    private final ImList<E> rest;

    private int size = 0;

    // Abstraction function:
    //   AF(elt, rest) = the list whose first element is elt,
    //                   followed by all the elements of rest
    // Representation invariant:
    //   elt != null, rest != null, size >= 0
    //   size > 0 implies size == 1 + rest.size()
    //   (size == 0 means "not yet computed"; a Cons is never empty)
    // Safety from rep exposure:
    //   all fields are private; elt and rest are final and immutable,
    //   and size is a primitive that is never exposed

    public Cons(E elt, ImList<E> rest) {
        this.elt = elt;
        this.rest = rest;
    }
    public ImList<E> cons(E elt) { return new Cons<>(elt, this); }
    public E first() { return elt; }
    public ImList<E> rest() { return rest; }

    public int size() {
        // 受益人式修改（beneficent mutation）：
        // 写 size 不改变本对象所表示的抽象值，因此类型仍然是不可变的
        if (size == 0) {
            size = 1 + rest.size();
        }
        return size;
    }
}

【为什么这样更好】 缓存被彻底私有化：客户端只能通过 size() 观察长度，无法破坏它；RI 明确写出了字段间的约束与哨兵值 0 的含义，任何人读到这段注释都能推理实现的正确性。缓存把重复查询从 O(n) 降到 O(1)（只在首次计算时付出 O(n)），而抽象值完全没变——这正是 beneficent mutation（受益人式修改）的定义：不改变对象所表示抽象值的状态变化，因此该类型仍然是不可变的。

【代码对比解说】 两种写法的算法完全一样，区别全在封装与文档上。课程原文特意点出这个例子的趣味之处：「this is an immutable datatype, and yet it has a mutable rep」——不可变类型的内部可以有可变状态，前提是变化对抽象值不可见、且不影响其他共享者。因此判断标准不是「字段是否 final」，而是「任何观察者能否区分变化前后」。要注意 sp22 的 TypeScript 版本用 number\|undefined 表示「尚未计算」，而 sp21 的 Java 版本用 0 这个哨兵值，因为 Cons 的长度永远大于 0；如果把同样的技巧用到 Empty 上就会出错（空列表的长度正是 0）。补充说明：这个技巧在 Java 内存模型下不是无锁安全的——并发调用 size() 构成数据竞争；这里之所以在实践中无害，是因为两个线程计算出的值必然相同且 int 写入是原子的。若确实要多线程共享，应按 Reading 23 的方式做同步，或干脆在读多写少的场景使用 volatile/AtomicInteger 并写清规格。

【设计原则透视】 这组对比把 AF/RI 的价值展示得最充分：AF 说明「这个对象代表哪个抽象列表」，因此只要 size 不影响 AF，改它就是受益人式修改；RI 说明「哪些 rep 是合法的」，因此新增字段必须同步新增约束条款。它也体现了 Reading 11 中「先写 AF/RI 再写实现」的配方价值：如果先写下 RI，size == 0 与「Cons 非空」的兼容性、以及缓存与 rest 的关系会立刻暴露出来，而不会成为一个隐藏的坑。

与其他设计原则的关联

本讲站在多条前置线索的交汇处。Reading 14（递归）提供了思维方式：递归数据类型与递归函数一样需要 base case（Empty）与 recursive step（Cons），「用归约步骤心算递归」的技巧直接来自那里。Reading 10（抽象数据类型）确立了「抽象类型 + 具体表示」的框架，而本讲第一次让两个具体类共同实现一个抽象类型，并强调这与 ArrayList/LinkedList 同实现 List 的情形有本质区别。Reading 11（抽象函数与表示不变量）是本讲的直接基础：AF/RI 必须按 variant 分别书写，表示独立性与表示暴露的讨论（隐藏构造器、rest() 返回不可变内部列表为何安全）都从这里来。

Reading 08（不可变性）解释了为什么 ImList 可以放心共享结构，也引出受益人式修改这一微妙话题；Reading 12（接口、泛型与枚举）提供了 ImList<E> 的泛型语法、接口静态方法 empty()，以及「用一组类表达一组 variant」这一手法的语言支持。Reading 06/07（规格说明与设计规格）规定了「规格不得谈论 rep」这条铁律，因此 isEmpty 不能写成「是否是 Empty 的实例」；first/rest 的「requires nonempty」前置条件与 UnsupportedOperationException/IndexOutOfBoundsException 的选择也属于规格设计。Reading 15（相等性）在实现 contains、equalValue 时立刻派上用场：判等要用 equals，而为递归类型定义 equalValue 时存在「用观察者操作判等」与「检查运行期类型」的取舍。

向后看，Reading 18（正则表达式与文法）与Reading 19（解析器）把文法产生的解析树建模为递归数据类型（Formula、语法树节点都是 variant 并集），本讲的「每个 variant 一个 case」正是遍历语法树的标准做法；Reading 26/27（小语言）会在更大规模上重复这一模式。Reading 21（并发）使用本讲的结论：不可变数据 + 纯函数天然可并行，回溯搜索因此可以直接并行化；Reading 23（互斥）则解释了为什么受益人式修改的缓存需要额外考虑。Reading 16（Map、Filter、Reduce）与 ImList 关系密切：对列表的 size/contains/append 的递归定义本质上就是 fold，理解「幺元 + 结合律」有助于看清 base case 的作用。最后，Reading 09/13（避免调试与调试）所倡导的 fail fast，正是场景 1 中「抛异常而非返回 null」的依据。

关键要点

• 先写数据类型定义，再写代码：在接口里用注释写下 ImList<E> = Empty + Cons(elt:E, rest:ImList<E>)，然后让接口、variant 类与操作一一对应；数学定义到实现几乎是机械翻译。
• 操作声明在接口、实现按 variant 分派，且绝不用 instanceof 窥探 variant：size/isEmpty/contains/get/append/last 都应在 ImList 上声明，在 Empty 与 Cons 中分别实现，客户端永远只看见抽象类型；需要新能力时给类型增加抽象操作，而不是检查 rest 的具体表示。
• 规格与 AF/RI 都不得提及 variant：isEmpty 的规格是「不含元素」，AF 是「第一个元素是 elt，其余是 rest 所代表的列表」，RI 是「字段非空」（加缓存时补上缓存条款）。
• 拒绝 null，使用哨兵对象：Empty 让空列表也能接收方法调用，避免遍地判空；first/rest 在空列表上必须快速失败而不是返回默认值。
• 共享依赖不可变：cons/first/rest 是 O(1)，append 是 O(this 的长度) 且完整共享右列表，reverse 的递归定义是 O(n²)；内部缓存属于受益人式修改，必须写进 RI。

常见陷阱与注意事项

• 在客户端直接 new Empty<>() 或 new Cons<>(...) → 表示独立性被破坏，客户端与具体 variant 耦合，日后替换实现会连带破坏所有调用点；应当只通过 ImList.empty() 与 cons() 构造，并把两个类设为包私有。
• 用 null 表示空列表或空尾部 → 每一处使用都要判空、极易漏写导致 NullPointerException，并且无法在空列表上调用方法；应当使用 Empty 哨兵对象。
• 用 instanceof 判断 variant 来分支 → 运行期类型检查比静态检查更不安全、更难适应变化；新增 variant 时静默失效。正确做法是增加抽象操作（如 size、get）或把分支下放到各 variant 的 accept 式方法里。
• 把 last()、reverse() 之类只写在某一个 variant 上 → 客户端拿到 ImList 类型时无法调用，被迫向下转型并再次引入运行期类型检查；所有公共操作都必须在接口上声明（在不适用的 variant 上抛异常即可）。
• AF/RI 写得含糊或写错 → 例如 AF(elt, rest) = a two-element list where the second element is rest（把列表当元素）、AF() = an empty list 写成 AF(first) = ...（不存在的字段）；这类文档错误会让后续维护者做出错误假设，进而写出真正违反不变量的代码。
• 给缓存加字段却不更新 RI、或把缓存字段设为 public → 缓存与 rest 的一致性无人保证，客户端可任意破坏抽象值；必须写成 private、在 RI 中写明 size > 0 implies size == 1 + rest.size()，并说明 0 的哨兵含义。反过来也别误以为「不可变类型的所有字段都必须 final」：受益人式修改允许不改变抽象值的字段变化，但在并发场景下这种缓存仍可能构成数据竞争（补充说明：需要共享时按 Reading 23 加同步）。

思考题（带答案）

问题 1：为下面这段 ImList 的片段写出合适的抽象函数与表示不变量，并说明 isEmpty 的实现为什么看起来「像」instanceof Empty 却并不等价。

public class Cons<E> implements ImList<E> {
    private final E elt;
    private final ImList<E> rest;
    public Cons(E elt, ImList<E> rest) { this.elt = elt; this.rest = rest; }
    public boolean isEmpty() { return false; }
    // ...
}

答案：抽象函数与表示不变量应写为：

// Abstraction function:
//   AF(elt, rest) = the list whose first element is elt,
//                   followed by all the elements of rest
// Representation invariant:
//   elt != null, rest != null
// Safety from rep exposure:
//   all fields are private and final; E and ImList<E> are immutable,
//   so rest() returning the internal list cannot threaten the invariant

注意 AF 不能写成「AF(elt, rest) = a non-empty list」（信息不足，没说明谁在前），也不能写成「AF(elt, rest) = 两元素列表，第二个元素是 rest」（错把列表当元素）。RI 至少要包含两个字段的非空约束——它们是「AF 是良定义的」的前提。

isEmpty 与 instanceof Empty 的区别在于层次：isEmpty 是抽象操作，其规格是「当且仅当本列表不含任何元素时返回 true」；instanceof Empty 是表示层的判断，它只对「用 Empty/Cons 表示列表」这一种实现成立。二者的外延在当前的实现下恰好一致，但这只是巧合的副产品：如果我们把 ImList 换成数组支撑的实现、或者引入一个表示「共享后缀的若干元素」的新 variant，isEmpty 的规格仍然成立，instanceof Empty 的代码却会失效。因此规格绝不能提及 variant——具体 variant 就是 rep。Cons.isEmpty() 返回 false 只是「某个 variant 对抽象操作的具体实现」，它与抽象操作的定义不是一回事。

问题 2：size() 的朴素实现在长度为 n 的列表上是 O(n)，加上缓存后首次仍是 O(n)、之后是 O(1)。请说明为什么这个缓存不违反不可变性，以及要让这段代码在多个线程中共享还需要做什么。

答案：缓存不违反不可变性，因为它是受益人式修改（beneficent mutation）：状态变化（把 size 从 0 改为 1 + rest.size()）不改变对象所表示的抽象值——AF(elt, rest) 只与 elt 和 rest 有关，size 完全不在 AF 中出现；因此任何客户端通过抽象操作观察到的行为，在修改前后完全一致。这也是「不可变类型可以有可变 rep」的标准含义（课程原文：this is an immutable datatype, and yet it has a mutable rep）。前提是缓存字段必须 private（否则客户端可以直接改它，抽象值就被破坏了），并且必须在 RI 中写下它与其他字段的关系：size >= 0，size > 0 implies size == 1 + rest.size()，以及 size == 0 表示「尚未计算」（这是因为 Cons 永远不空，长度不可能为 0；若把同样的哨兵技巧用在 Empty 上就会错，因为空列表的长度正是 0）。

至于线程安全：补充说明，上述缓存是普通的非 volatile 非同步字段，多线程并发调用 size() 按 Java 内存模型构成数据竞争。在这里它「碰巧」无害，因为两个线程计算出的值必然相同，而 int 的写入是原子的，所以最坏情况只是重复计算。但这依赖具体实现细节而非规格保证：如果缓存值可能是引用类型、可能是 64 位 long（非 volatile 时写入不是原子的），或者计算过程依赖其他可变状态，就必须按 Reading 23（互斥与同步）的方式加锁、使用 AtomicInteger/volatile，或者干脆放弃缓存——这正是「不可变数据天然线程安全」这一红利的边界：受益人式修改把一部分安全性让渡给了实现细节。

问题 3：为什么课程说 append 的递归实现是「非破坏性」的，而它为什么无法做到 O(1)？请结合共享结构解释 append(Empty, list2) = list2 这一条基例的意义。

答案：append 的递归定义是 append(Empty, list2) = list2 与 append(Cons(elt, rest), list2) = cons(elt, append(rest, list2))。翻译成 Java 时，Cons 的每一步都新建一个 Cons（return new Cons<>(elt, rest.append(other));），而 Empty 的基例直接返回 list2 本身。因此左列表的每一个 Cons 都被复制成新节点（「复制脊柱」），而右列表 list2 的节点一个也没有复制，被完整共享。这就是非破坏性：所有既有列表对象在操作前后完全不变，因此对共享同一子列表的多个引用都安全——这也回应了课程原文对共享的强调（「Only one copy of this sublist exists in memory, and both x and y point to it, but this aliasing is perfectly safe because the list is immutable」）。

无法做到 O(1) 的原因是表示的限制：每个 Cons 只有一个 rest 字段，指向唯一一个后继，而且要把新列表的「第一个元素」暴露给 first()。若想让 append 变成 O(1)，就必须改写某个既有 Cons 的 rest 字段（例如把左列表最后一个节点的 rest 指向右列表），而那会破坏不可变性，让所有共享该子列表的引用追溯性地改变含义——前面场景 4 已经展示过这种 bug 的破坏力。换句话说，O(1) 的 append 与「多引用安全共享」在同一表示下不可兼得；需要频繁拼接时应改用其它结构（如数组支撑的 List、ArrayList 的 addAll，或专门的 Seq/差分列表），并接受不同的性能画像。

append(Empty, list2) = list2 这一基例的意义有两重：其一，它定义了「空列表拼接任何列表」的语义，使 append 在左参数递减到 base case 时终止；其二，它是结构共享的入口——正因为基例原样返回右列表，append 才能在不复制右列表的前提下完成拼接。这与 size(Empty) = 0 作为「空乘积/空和的幺元」在 Reading 16 中扮演的角色异曲同工：base case 不只是终止条件，它还定义了运算的单位元语义。