第6章：递归类型（Recursive Types）Recursive Types — Self-Referential Types

一、导读

1.1 学习目标

递归类型允许类型引用自身，是定义链表、树等递归数据结构的基础。通过本章的学习，读者将达成以下目标：

• 理解递归类型的数学基础——不动点理论
• 掌握等式递归类型和同构递归类型的区别
• 熟练使用 fold/unfold 操作构造和解构递归数据
• 能用递归类型编码常见的数据结构（自然数、列表、树）
• 理解递归类型与模式匹配的关系
• 认识递归类型在面向对象语言中的应用

1.2 重要性

递归类型是编程语言中定义递归数据结构的理论基础。在 Haskell 中，data List a = Nil | Cons a (List a) 定义了递归的列表类型。在 Java 中，链表节点类引用自身类型。在 TypeScript 中，JSON 类型递归地包含自身。所有这些都需要递归类型来形式化。

递归类型的理论还揭示了代数数据结构的本质。每个递归数据类型都可以看作是一个函子（Functor）的不动点，这个观点统一了列表、树、自然数等看似不同的数据结构，为泛型编程和类型论研究提供了深刻的洞察。

1.3 核心问题

• 递归类型的数学含义是什么？类型方程 X = F(X) 的解是什么？
• 等式递归类型和同构递归类型有什么区别？各自适合什么场景？
• fold 和 unfold 操作的语义是什么？它们如何保证递归操作的安全性？
• 递归类型如何与子类型交互？面向对象语言中的自类型（self type）是什么？
• 递归类型和 System F 的多态类型如何结合？

二、核心概念详解

2.1 递归类型的直觉

递归类型是包含对自身引用的类型定义。最直观的例子是链表类型：

List = Int × List + 1

这个方程表示：一个 List 要么是一个 Int 和另一个 List 的序对（Cons 情况），要么是空（Nil 情况，用单位类型 1 表示）。这个方程的解就是链表类型。

在编程语言中，递归类型通常通过 data 声明或 type 定义来表达：

-- Haskell
data List = Nil | Cons Int List

-- TypeScript
type Tree = { value: number; left: Tree; right: Tree } | null

-- Java
class ListNode {
    int value;
    ListNode next;  // 递归引用自身类型
}

从数学角度看，递归类型是类型构造器（函子）的不动点。给定一个类型构造器 F，递归类型 μX. F(X) 是方程 X = F(X) 的解，满足 μX. F(X) = F(μX. F(X))。

2.2 不动点构造子 μ

不动点构造子 μ（mu）是递归类型的核心语法。μX. F(X) 表示类型构造器 F 的最小不动点——最小的类型 X 使得 X = F(X) 成立。

例如：

• μX. 1 + X 表示自然数类型（0 或 1 + 自然数）
• μX. 1 + Int × X 表示整数列表类型
• μX. 1 + X × X 表示二叉树类型

μ 构造子的语义可以从两个角度理解：

最小不动点（归纳类型）：μX. F(X) 是最小的类型 X 使得 X ⊇ F(X)。它只包含通过有限次应用 F 构造出来的值。这是大多数编程语言中递归类型的语义——列表是有限次的 Cons 和 Nil 构造出来的。

最大不动点（余归纳类型）：νX. F(X) 是最大的类型 X 使得 X ⊆ F(X)。它包含所有可能的值，包括无限的。余归纳类型用于描述无限数据结构（如无限流 stream）。

在大多数编程语言中，递归类型采用最小不动点语义。Haskell 是个例外，由于其惰性求值，它自然地支持最大不动点（可以构造无限数据结构）。

2.3 等式递归类型 vs 同构递归类型

递归类型有两种主要的形式化方式，它们对类型等式的处理不同：

等式递归类型（Equi-recursive Types）：将递归类型与其展开形式视为完全相同的类型。即 μX. F(X) 和 F(μX. F(X)) 是同一个类型，可以无条件互相替换。

-- 等式递归类型中，以下两个类型完全相同：
Nat = μX. 1 + X
    = 1 + μX. 1 + X
    = 1 + (1 + μX. 1 + X)
    = ...

等式递归类型的优点是灵活——不需要显式的 fold/unfold 操作，值可以自动在递归类型和展开形式之间转换。缺点是类型等价判定变得复杂（可能需要无限展开），类型检查器的实现更困难。

同构递归类型（Iso-recursive Types）：将递归类型 μX. F(X) 和展开形式 F(μX. F(X)) 视为不同但同构的类型。需要显式的 fold 和 unfold 操作在两者之间转换。

fold   : F(μX. F(X)) → μX. F(X)    -- 将展开形式折叠为递归类型
unfold : μX. F(X) → F(μX. F(X))    -- 将递归类型展开为展开形式

同构递归类型的优点是类型检查更简单（类型等价是语法等价），语义更清晰。缺点是需要显式的 fold/unfold 操作，代码更冗长。大多数编程语言（包括 Haskell、ML、Rust）采用同构递归类型的变体，但通过模式匹配和语法糖隐藏了 fold/unfold。

2.4 fold 与 unfold 操作

fold 和 unfold 是递归类型的构造和解构操作，它们提供了对递归数据类型的系统化操作方式。

fold（折叠/构造）：将一层 F 结构包装成递归类型。

fold : F(μX. F(X)) → μX. F(X)

-- 例子：构造列表
fold (Cons 1 (fold (Cons 2 (fold Nil)))) : List Int
-- 等价于：1 :: 2 :: []

unfold（展开/解构）：将递归类型展开为一层 F 结构。

unfold : μX. F(X) → F(μX. F(X))

-- 例子：解构列表
unfold (1 :: 2 :: []) = Cons 1 (2 :: [])

fold 和 unfold 满足互逆性质：

• unfold (fold x) = x（先折叠再展开，回到原点）
• fold (unfold x) = x（先展开再折叠，回到原点）

在等式递归类型中，fold 和 unfold 是隐式的（自动应用）。在同构递归类型中，它们需要显式写出。

2.5 数据结构编码

利用递归类型，可以系统地编码各种常见数据结构：

自然数（Peano 自然数）：

Nat = μX. 1 + X
-- zero = fold (inl ())       -- 0
-- succ n = fold (inr n)      -- n + 1

整数列表：

ListInt = μX. 1 + Int × X
-- nil = fold (inl ())
-- cons h t = fold (inr (h, t))

多态列表（结合 System F）：

List = Λα. μα. 1 + α × X
-- 或写为：List A = μX. 1 + A × X

二叉树：

Tree = μX. 1 + Int × X × X
-- leaf = fold (inl ())
-- node v l r = fold (inr (v, l, r))

lambda 项（用递归类型表示语法树）：

Term = μX. Var + X × X + X × X
-- 即：Term = Var + Term × Term + Term × Term
-- 分别对应变量、应用和抽象

这些编码展示了递归类型的统一表达能力——所有递归数据结构都可以表示为某个函子的不动点。

三、深入分析

3.1 递归类型与子类型的交互

递归类型与子类型的交互是类型理论中最复杂的问题之一。核心困难在于：如何判定两个递归类型之间的子类型关系？

考虑面向对象语言中的类层次：

class Animal { ... }
class Dog extends Animal { ... }

Dog 类型可以看作是递归类型的子类型的特例。Dog <: Animal 要求 Dog 的所有字段和方法都兼容 Animal 的定义。当类定义中包含自引用（如 Animal 有方法 clone(): Animal）时，子类型判定需要考虑递归结构的兼容性。

一个经典的难题是：如果 Dog <: Animal，那么 Dog → Dog <: Animal → Animal 吗？根据函数类型的方差规则，参数逆变要求 Animal <: Dog（不成立！），所以这个子类型关系不成立。这意味着不能将接受 Dog 的函数用于需要接受 Animal 的上下文——这是符合直觉的。

对于包含递归类型的子类型判定，通常需要计算不动点——子类型关系本身可能递归地依赖于自身。这可能导致判定过程不终止，使得子类型判定在某些系统中不可判定。

3.2 F-有界多态

F-有界多态（F-bounded Polymorphism）是递归类型和多态类型的结合，用于表达"返回自身类型"的模式。

-- 问题：如何表达 clone 方法返回"自身类型"？
interface Comparable<T> {
    compareTo(other: T): int;
}

-- F-有界多态：类型参数被约束为自身的子类型
interface Comparable<T extends Comparable<T>> {
    compareTo(other: T): int;
}

class Dog implements Comparable<Dog> { ... }
class Cat implements Comparable<Cat> { ... }

在 System F 的扩展中，F-有界多态的形式为：

∀α <: F(α). T

即类型变量 α 被约束为 F(α) 的子类型，其中 F 可能包含 α 的递归引用。这允许表达"对于所有是 F(α) 子类型的 α"这样的约束。

F-有界多态在面向对象语言中广泛使用：Java 的 Enum<E extends Enum<E>>、C# 的 CRTP（Curiously Recurring Template Pattern）都是 F-有界多态的实例。

3.3 递归类型作为函子的不动点

从范畴论的角度看，递归类型 μX. F(X) 是函子 F 的初始代数（initial algebra）。这个观点由 Lambek 提出，为递归数据类型提供了深刻的数学基础。

函子 F 描述了数据结构的"一层"结构。例如，列表的函子是 F(X) = 1 + A × X（要么是 Nil，要么是一个元素加一个递归位置）。

初始代数 是函子 F 的不动点 μX. F(X) 连同构造操作 in: F(μX. F(X)) → μX. F(X)（即 fold），满足初始性：对于任何其他 F-代数 (A, f: F(A) → A)，存在唯一的同态 h: μX. F(X) → A 使得 h ∘ in = f ∘ F(h)。

这个唯一的同态 h 就是 fold 操作——它是递归数据结构的通用遍历方式。所有对递归数据结构的递归处理（求和、映射、过滤等）都可以表示为 fold。

这个观点统一了各种递归操作：

• 列表的 foldr 是列表函子 F(X) = 1 + A × X 的初始代数的唯一同态
• 树的 fold 是树函子 F(X) = 1 + A × X × X 的初始代数的唯一同态
• 自然数的递归是自然数函子 F(X) = 1 + X 的初始代数的唯一同态

四、实践案例

4.1 案例一：Haskell 的递归数据类型

Haskell 的 data 声明是递归类型的最直接应用：

-- 递归列表
data List a = Nil | Cons a (List a)

-- 递归树
data Tree a = Leaf a | Branch (Tree a) (Tree a)

-- 递归表达式
data Expr = Num Int
          | Add Expr Expr
          | Mul Expr Expr
          | Neg Expr

-- 折叠操作（fold 的具体化）
foldList :: b -> (a -> b -> b) -> List a -> b
foldList nil cons Nil = nil
foldList nil cons (Cons x xs) = cons x (foldList nil cons xs)

-- 用 fold 定义常见操作
length :: List a -> Int
length = foldList 0 (\_ n -> n + 1)

sum :: List Int -> Int
sum = foldList 0 (+)

Haskell 的模式匹配本质上是 unfold 操作的语法糖——它将递归类型值展开为一层结构，然后根据构造子进行分支处理。

4.2 案例二：TypeScript 中的递归类型

TypeScript 支持多种形式的递归类型定义：

// 递归接口
interface TreeNode {
  value: number;
  left: TreeNode | null;
  right: TreeNode | null;
}

// 递归类型别名
type JSON = string | number | boolean | null | JSON[] | { [key: string]: JSON };

// 递归条件类型
type DeepReadonly<T> = {
  readonly [K in keyof T]: T[K] extends object ? DeepReadonly<T[K]> : T[K];
};

// 递归模式匹配（类型级别编程）
type Flatten<T> = T extends Array<infer U> ? Flatten<U> : T;
// Flatten<number[][][]> = number

TypeScript 的递归类型检查有深度限制（防止无限展开），这体现了递归类型在实践中的复杂性。

五、常见误区

5.1 误区一：递归类型就是自引用

递归类型不仅仅是"类型引用自身"。形式化地，递归类型是类型构造器的不动点。class Node { Node next; } 中的自引用是语法层面的递归，而 μX. 1 + Int × X 是语义层面的不动点构造。理解不动点观点有助于我们更系统地设计和分析递归数据结构。

5.2 误区二：所有递归定义都是合法的

不是所有类型方程都有有意义的解。例如 X = X → X（自指函数类型）在集合论中没有非平凡解（会导致基数矛盾）。在类型系统中，这样的方程要么被拒绝（STLC），要么需要特殊处理（如 Domain Theory 中的 lifting）。

5.3 误区三：fold 只能做简单的聚合

fold 是递归数据结构的通用操作模式，它可以表达任何对数据结构的递归遍历。不仅限于求和、计数等简单聚合，还可以表达映射、过滤、树变换、甚至类型检查器的实现。理解 fold 的通用性有助于写出更组合化的代码。

5.4 误区四：等式递归类型总是更好

等式递归类型虽然更灵活（不需要显式 fold/unfold），但类型检查更复杂，类型等价判定可能需要无限展开。同构递归类型虽然代码更冗长，但类型检查更简单、更可预测。大多数实际语言选择同构递归类型（或其变体）是有充分理由的。

六、本章小结

本章系统讲解了递归类型的理论基础和实践应用。递归类型是类型构造器的不动点，通过 μ 构造子定义自引用的类型。等式递归类型将递归类型与其展开形式视为等价，同构递归类型则需要显式的 fold/unfold 操作在两者之间转换。

fold 和 unfold 是递归数据结构的构造和解构操作。fold 将一层结构包装为递归类型（构造数据），unfold 将递归类型展开为一层结构（解构数据）。从范畴论角度看，递归类型是函子的初始代数，fold 是初始代数的唯一同态，统一了所有递归遍历操作。

递归类型与子类型的交互产生了 F-有界多态等重要概念，用于表达"返回自身类型"的模式。递归类型与多态类型的结合使得我们可以定义通用的递归数据结构（如多态列表、多态树）。

理解递归类型对于深入认识代数数据类型、模式匹配和函数式编程模式至关重要。它也是学习更高级类型系统（如 GADT、依赖类型）的必要基础。

七、思考题

请用 μ 构造子写出以下数据类型的类型表达式：

- 二叉搜索树（每个节点包含值和左右子树）

- 带有变量、lambda 抽象和应用的 lambda 项

- 嵌套列表（列表的元素也可以是嵌套列表）

比较等式递归类型和同构递归类型在类型检查方面的差异。为什么大多数实际语言选择同构递归类型？

请为列表类型 List A = μX. 1 + A × X 定义 fold 和 unfold 操作，并用 fold 实现 map、filter 和 reverse 函数。

解释为什么类型方程 X = X → X 在标准集合论中没有非平凡解。在什么语义框架下可以给这个方程赋予意义？

研究 Haskell 的 Fix 类型：newtype Fix f = Fix (f (Fix f))。它如何体现了"递归类型是函子的不动点"这一观点？请用 Fix 重新定义列表和树类型。