泛型编程

有三个函数：

def find_max_int(items: list[int]) -> int:
    result = items[0]
    for x in items:
        if x > result:
            result = x
    return result
 
def find_max_float(items: list[float]) -> float:
    result = items[0]
    for x in items:
        if x > result:
            result = x
    return result
 
def find_max_str(items: list[str]) -> str:
    result = items[0]
    for x in items:
        if x > result:
            result = x
    return result

算法完全相同。变化的只有一件事：类型。

这是一个认知问题：我们建立了类型系统这套秩序，但现在发现这套秩序阻碍了我们表达一个更普遍的真理——排序算法不依赖于你在排什么，只依赖于元素之间可以比较大小。

泛型的起点就是这个问题：什么东西不随类型变化？

答案：算法的结构不变。变化的只是”元素之间如何比较”这一件事。泛型让你把这个不变的部分抽出来，命名它，一次写成，对所有满足条件的类型同时成立。

这不是抹除类型系统，是发现类型系统的共性结构——秩序的共性。

一、程序是参数化的算法

两个层次的认知

类型系统建立了第一层认知：值有类型。x 是整数，name 是字符串，account 是 BankAccount——每个值都有一个身份，类型系统是对值的分类体系。

泛型建立了第二层认知：算法对类型有要求。不是”这个函数操作整数”，而是”这个函数操作任何可以比较大小的类型”。基本单元不再是”操作某种具体类型的函数”，而是”声明对类型的最低要求，在这个要求内推理”的函数。

// 第一层：具体类型
fn find_max_int(items: &[i32]) -> i32 { ... }
 
// 第二层：类型要求
fn find_max<T: PartialOrd>(items: &[T]) -> &T { ... }
//                 ↑
//          不是"T 是什么"，而是"T 能做什么"

T: PartialOrd 不是说 T 是某种类型，而是说 T 满足某种约束——它的元素之间可以用 < > 比较。算法只关心这一点，不关心 T 究竟是整数、浮点数、字符串还是自定义类型。

System F：类型成为参数

这个思路的数学基础来自 1972 年（Girard 和 Reynolds 独立发现）的 System F，又称多态 Lambda 演算。

简单类型 Lambda 演算（STLC）只允许对值抽象：λx. x 接受一个值 x，返回 x。System F 在此之上增加了类型抽象：

Λα. e          ← 对类型参数 α 抽象表达式 e
e [τ]          ← 将具体类型 τ 应用于表达式 e

恒等函数在 System F 中的完整形态：

id : ∀α. α → α
id = Λα. λ(x:α). x
 
id [Int] 42      → 42
id [String] "hi" → "hi"

∀α 的意思是”对所有类型 α”。类型从标签变成了参数——这是从值的抽象到类型的抽象的跃迁。

两种多态，两种意图

泛型的”参数多态”只是多态的一种，理解它需要和另一种多态对比：

维度	参数多态（Parametric）	特设多态（Ad-hoc）
实现数量	一个实现，适用所有类型	同一接口名，不同类型有不同实现
类型信息	实现完全不依赖类型具体信息	实现依赖类型的具体行为
典型例子	identity<T>(x: T) -> T	+（整数加法 vs 字符串拼接）
机制	泛型类型参数	重载、trait、typeclass

排序算法（参数多态）：一份实现，适用所有可比较类型，因为它只用到了比较操作，不关心类型细节。

Display（特设多态）：每种类型有自己的实现——整数格式化为 42，浮点数格式化为 3.14，自定义结构体格式化为你指定的形式。

两者不是对立的，是互补的：参数多态表达算法的普遍性，特设多态表达类型的个性。

二、类型签名即证明

免费定理：从签名推导行为

泛型最反直觉的力量：一个函数的类型签名，有时足以证明它的行为，不需要看实现。

1989 年，Philip Wadler 发表了论文 “Theorems for Free!”，证明了参数多态函数的类型签名蕴含了关于其行为的数学定理。

最简单的例子：

f : ∀T. T → T

不看实现，你能证明：f 只能原样返回输入。

推理过程：f 对类型 T 一无所知——它无法构造一个 T（因为不知道 T 的构造方式），无法修改一个 T（因为不知道 T 的内部结构），无法从外部引入一个 T（没有其他 T 类型的输入）。唯一合法的操作是把收到的那个 T 原样返回。

再一个：

f : ∀T. [T] → [T]

这个函数接受一个 T 的列表，返回一个 T 的列表。你能证明：输出列表中的每个元素都来自输入列表。f 不能凭空创造一个 T，所以它只能移动、复制或丢弃元素。

这与你在 FP 中学到的引用透明性有深层联系：参数多态提供了一种更强的约束——不只是”同样输入产生同样输出”，而是”连行为的结构都被类型签名约束了”。

Haskell 社区说”类型是文档”，正是因为这一点：类型签名不只告诉你输入输出的形状，还告诉你函数能做什么、不能做什么。

最低知识要求

泛型提供了一个强大的认知工具：

面对一个算法，问”我最少需要知道关于类型的什么”。

这个问题的答案就是类型约束（trait bound / type bound），也是泛型设计的核心。

fn sort<T: Ord>(items: &mut [T]) {
    // 只需要知道 T 可以全序比较，不需要知道 T 是什么
}
 
fn deduplicate<T: Eq + Hash>(items: Vec<T>) -> Vec<T> {
    // 只需要知道 T 可以判等和哈希，不需要知道 T 是什么
}
 
fn log<T: Display>(value: T) {
    // 只需要知道 T 可以格式化输出，不需要知道 T 是什么
}

“最低知识要求”迫使你想清楚算法真正依赖的是什么。一旦想清楚，这个约束就成了算法适用范围的精确声明——任何满足这个约束的类型，这个算法都对它成立。

这是与鸭子类型的根本区别：

# 鸭子类型：隐式约定，运行时发现
def find_max(items):
    # 假设元素可以用 > 比较——但这只是假设，不是声明
    result = items[0]
    for x in items:
        if x > result:
            result = x
    return result

鸭子类型是隐式约定，泛型约束是显式声明。前者灵活但脆弱，后者严格但可证明。

三、抽象何时变为具体

泛型与状态和时间没有直接关系——它横切所有其他范式，不关心可变性。但它有自己的时态问题：类型参数什么时候被确定？

三种时机，三种哲学

策略	时机	结果	代表语言
单态化	编译时	每种具体类型生成一份独立代码	Rust、C++
类型擦除	编译后丢弃	运行时只有裸对象，类型参数消失	Java、TypeScript
虚分派	运行时查找	通过 vtable 间接调用具体方法	Go（部分）、Java（部分）

单态化：泛型是给程序员用的认知工具，机器不需要知道它存在。find_max<i32> 和 find_max<String> 在编译后是两份完全独立的机器码，各自针对具体类型优化，没有任何间接层。代价是编译时间和二进制体积——每多一种具体类型，就多一份代码。

类型擦除：Java 选择了向后兼容，List<String> 和 List<Integer> 在运行时都只是 ArrayList，类型参数被擦除。这让泛型成为纯编译期概念，但代价是运行时无法检查泛型类型参数——instanceof List<String> 是无效的，只能 instanceof List。

Rust 的 dyn Trait：Rust 也提供运行时多态，通过 trait 对象（Box<dyn Display>）实现虚分派——这时类型信息被存入 vtable，运行时动态查找。但这是显式选择，不是默认行为。

// 静态分派：编译时确定类型，零运行时开销
fn print_static<T: Display>(value: T) {
    println!("{}", value);
}
 
// 动态分派：运行时通过 vtable 查找，有间接层
fn print_dynamic(value: &dyn Display) {
    println!("{}", value);
}

两种选择的差异，是”把类型当工具还是当档案”的哲学分野：

• 单态化：类型是编译器的工具，生成最优代码后不再需要
• 类型擦除：类型是人类的工具，运行时不需要知道
• 虚分派：类型是运行时的工具，需要保留以支持动态行为

泛型是正交横切面

泛型与其他范式的关系独特：它不关心状态（OOP 关心）、不关心时间（FP 关心）、不关心执行顺序（过程式关心）——它横切所有范式，是独立的抽象维度。

你可以有泛型的纯函数（FP + 泛型），泛型的可变对象（OOP + 泛型），泛型的声明式查询（声明式 + 泛型）。泛型不改变范式的状态观和时态观，只扩大了算法的适用范围。

这也是为什么标准库几乎全由泛型构成：Vec<T>、Option<T>、Result<T, E> 的算法逻辑与具体类型无关，但能安全地用于任何类型。

四、约束如何叠加

约束叠加的方向

类型约束是泛型的组合机制。多个约束叠加，精确描述算法需要的能力集合：

fn process<T>(item: T)
where
    T: Display    // 可以格式化输出
     + Clone      // 可以复制
     + Send       // 可以跨线程传递
     + 'static    // 没有短命的引用
{
    // 在这个函数体内，T 拥有上面所有能力
}

约束叠加有一个内在张力：

约束越少 → 函数越通用，能做的操作越少
    ∀T. T → T        什么约束都没有，只能原样返回
    T: Clone          能复制，但不能比较
    T: Clone + Ord    能复制和比较
 
约束越多 → 函数越专用，能做的操作越多
    T: Ord + Hash + Clone + Display + Send + 'static
    → 能排序、哈希、复制、显示、跨线程，但适用类型变少

泛型设计的核心问题：这个算法真正需要哪些能力，不多也不少。

协变与逆变：秩序如何传播

当类型之间有子类型关系，泛型容器如何传播这个关系？这是 **variance（型变）**问题。

假设 Dog 是 Animal 的子类型：

协变（Covariant）：
    Dog <: Animal  →  Container<Dog> <: Container<Animal>
    适合只读容器（读出来的 Dog 可以当 Animal 用）
 
逆变（Contravariant）：
    Dog <: Animal  →  Handler<Animal> <: Handler<Dog>
    适合函数参数（能处理 Animal 的函数，也能处理 Dog）
 
不变（Invariant）：
    Dog <: Animal  →  MutableRef<Dog> 和 MutableRef<Animal> 无关系
    适合可写容器（写入的类型必须精确匹配）

Java 数组协变是一个经典的设计错误：

String[] strings = new String[]{"hello"};
Object[] objects = strings;  // 编译通过：数组是协变的
objects[0] = 42;             // 编译通过：Object[] 可以放 Integer
// 运行时抛出 ArrayStoreException——类型安全在运行时才被发现

Rust 通过生命周期和所有权在编译时解决这个问题：&'a T 对 T 是协变的，&'a mut T 对 T 是不变的（因为可变引用允许写入，写入必须类型精确）。

型变是类型系统保证秩序跨越泛型边界时不被破坏的机制。

高阶类型：对类型构造器的推理

泛型的第三层：当类型构造器本身成为参数。

List 不是一个类型（*），而是一个类型构造器（* → *）——它接受一个类型，产生一个新类型：List<Int>、List<String>。

高阶类型（HKT）允许对类型构造器抽象：

-- Functor：任何"装东西的容器"，都可以对里面的元素做变换
class Functor f where
    fmap :: (a -> b) -> f a -> f b
--                      ↑
--              f 是类型构造器，不是具体类型
 
instance Functor []     where fmap = map
instance Functor Maybe  where fmap f (Just x) = Just (f x)
                               fmap _ Nothing  = Nothing
instance Functor Either where fmap f (Right x) = Right (f x)
                               fmap _ (Left e)  = Left e

List、Maybe、Either 是完全不同的类型构造器，但都满足 Functor 约束：都可以对内部元素做变换，且变换不改变容器的结构。

这是第三层认知：

第一层（类型系统）：值有类型           int, string, BankAccount
第二层（泛型）：算法对类型有要求    T: Comparable, T: Clone
第三层（高阶类型）：类型构造器有约束    Functor, Monad, Traversable

每一层都在对下一层做推理。Haskell 原生支持 HKT；Rust 用 GAT（Generic Associated Types）部分模拟；TypeScript、Python 没有原生支持。

五、多语对照：三种工程权衡

泛型机制对比

维度	Python	TypeScript	Rust
参数多态	TypeVar / [T]（静态检查）	<T>（编译时）	<T>（编译时）
约束机制	TypeVar(bound=...) / Protocol	extends	T: Trait + Trait
多态实现	鸭子类型（运行时）	类型擦除（编译后消失）	单态化（零开销）
型变	运行时无概念	协变数组、逆变函数参数	编译时通过生命周期控制
高阶类型	不支持	模拟（HKT<F, A> 模式）	GAT 部分支持
运行时开销	无（无编译时检查）	无（类型擦除）	无（单态化展开）

三语言的哲学立场

Python：鸭子类型是隐式的泛型。不声明约束，假设调用方传入的类型有你需要的方法——如果没有，运行时报错。这是信任优先、安全靠后的哲学：同样的代码对任何”形状合适”的类型都成立，但你需要自己保证形状确实合适。

from typing import TypeVar, Protocol
 
class Comparable(Protocol):
    def __lt__(self, other: Any) -> bool: ...
 
T = TypeVar("T", bound=Comparable)
 
def find_max(items: list[T]) -> T:
    # 类型检查器（mypy/pyright）会在静态分析时验证约束
    # 运行时仍然是鸭子类型
    ...

TypeScript：类型体操是声明式泛型的极致。TypeScript 的类型系统是图灵完备的——你可以在类型层面做任意复杂的计算：

// 类型层面的编程：从对象类型推导出所有可选键的联合
type OptionalKeys<T> = {
  [K in keyof T]-?: undefined extends T[K] ? K : never
}[keyof T];
 
// 类型体操让 API 使用者获得完整的类型安全和自动补全
type ComponentProps<T extends keyof JSX.IntrinsicElements> =
  JSX.IntrinsicElements[T];

类型系统本身成为一个可编程的声明式层。类型体操不是奇技淫巧，是 TypeScript 哲学的自然延伸。

Rust：单态化 + trait bound 是零成本抽象的核心。泛型代码在编译后完全消失，留下的是针对每种具体类型优化过的机器码：

// 编译时，编译器生成 find_max_i32、find_max_f64、find_max_str 各自的实现
// 运行时没有任何泛型层的开销
fn find_max<T: PartialOrd>(items: &[T]) -> Option<&T> {
    items.iter().reduce(|a, b| if a >= b { a } else { b })
}

Rust 的立场：抽象是给程序员的礼物，不是给机器的负担。所有的泛型、trait、生命周期，都在编译时完全解析，运行时零痕迹。

---

延伸阅读

• Wadler, Philip. “Theorems for Free!” (1989) — 参数化定理原始论文
• Pierce《Types and Programming Languages》Ch23-25 — System F 与参数多态
• Stepanov & McJones《Elements of Programming》— 泛型编程的数学基础
• Rust Book Ch10 — trait 与泛型实践

---

关联 meta 维度

• meta: 类型系统 — 泛型是类型系统的第二层，类型参数化的理论基础
• 02 函数式编程 — Functor、Monad 等抽象依赖高阶类型；引用透明性与参数化定理的联系
• 01 面向对象编程 — 子类型多态 vs 参数多态；继承与泛型的不同抽象路径
• 03 过程式与声明式 — TypeScript 类型体操是类型层面的声明式编程