一、什么是代数数据类型
代数数据类型(Algebraic Data Types,简称 ADT)是一种通过组合已有类型来构造新类型的类型系统机制。
它的核心思想是:复杂的数据类型可以由更简单的类型通过两种基本方式组合而成:
- 乘积类型(Product Type):一个值同时包含多个字段。
- 和类型(Sum Type):一个值可以是多个候选类型中的某一种。
例如,一个用户信息可能由姓名、年龄和邮箱组成,这是乘积类型;一个网络请求结果可能是成功、失败或加载中,这是和类型。
ADT 的核心不是某种具体的数据结构,而是一种类型建模方式。
从类型代数的角度看:
- 乘积类型表示多个组成部分同时存在。
- 和类型表示多个候选分支中选择一个。
- 两者可以嵌套组合,构造复杂的数据模型。
二、代数数据类型的数学基础
ADT 中的“代数”来自类型可以按照类似算术的方式进行组合。
假设:
- 类型
A有 m 种可能的值。 - 类型
B有 n 种可能的值。
那么:
1. 乘积类型:类型的乘法
乘积类型表示一个值由多个部分共同组成。
例如:
type User = {
name: string;
age: number;
};
假设 string 有 m 种可能值,number 有 n 种可能值,那么理论上 User 的值空间由两者的组合构成。
每个 User 值都同时包含 name 和 age。
从结构上看:
User
├── name: string
└── age: number
这种结构也称为记录类型(Record Type)。
常见乘积类型包括:
- 元组(Tuple)
- 结构体(Struct)
- 记录类型(Record)
- 多字段数据类(Data Class)
2. 和类型:类型的加法
和类型表示一个值可以属于多个候选类型中的某一种。
例如:
type Result =
| { type: "success"; data: string }
| { type: "failure"; error: Error };
Result 表示两种可能:
- 成功结果。
- 失败结果。
一个 Result 值只能对应其中一个分支。
从结构上看:
Result
├── Success
│ └── data: string
└── Failure
└── error: Error
常见和类型包括:
- 枚举变体(Enum Variants)
- Tagged Union
- Discriminated Union
- Rust 的
enum - Haskell 的代数数据构造器
需要注意:和类型的具体实现可能包含标签、判别字段或运行时类型信息,但这些实现细节不改变其类型组合语义。
3. 单位类型:只有一个值的类型
单位类型(Unit Type)是一种只有一个可能值的类型。
例如:
- Rust:
() - Haskell:
() - Kotlin:
Unit
其基数为:
单位类型常用于表示没有额外数据的分支。
例如:
enum Status {
Loading,
Success(String),
Failure(String),
}
其中 Loading 可以理解为不携带额外字段的构造分支。
从代数角度看,它类似于一个只包含单位值的分支。
4. 空类型:没有任何值的类型
空类型(Empty Type)没有任何合法值,其基数为:
在 Rust 中,! 是 Never Type,表示不会正常产生一个值的类型。
fn terminate() -> ! {
panic!("程序终止");
}
空类型在类型理论中具有重要意义:
- 它无法被正常构造出一个值。
- 可以用于表示不可能发生的状态。
- 可以用于描述不返回的函数。
- 在某些类型运算中充当和类型的零元。
需要区分:不同语言对空类型、底类型(Bottom Type)和 Never Type 的具体定义可能不同,不能简单认为它们在所有语言中完全等价。
三、乘积类型(Product Type)
乘积类型是多个字段的组合,所有字段共同构成一个完整值。
1. 基本结构
type Point = {
x: number;
y: number;
};
Point 同时包含两个坐标字段。
其类型结构可以表示为:
一个 Point 值必须满足两个字段的结构要求。
2. 元组类型
元组也是典型的乘积类型。
type UserInfo = [string, number, boolean];
const user: UserInfo = ["Alice", 25, true];
它由三个位置固定、类型可以不同的元素组成。
元组和普通数组的区别:
| 对比维度 | 元组 | 数组 |
|---|---|---|
| 元素数量 | 通常固定或受类型约束 | 通常可变 |
| 元素类型 | 不同位置可以不同 | 通常共享元素类型 |
| 访问方式 | 通过固定位置访问 | 通过索引访问 |
| 类型表达 | 多个字段的组合 | 同类元素的集合 |
3. 乘积类型的组合
乘积类型可以嵌套:
type Address = {
city: string;
street: string;
};
type User = {
name: string;
age: number;
address: Address;
};
其结构可以理解为:
继续展开:
乘积类型具有结合性:
这里的 \cong 表示结构上的同构,并不意味着不同语言中的具体类型声明一定完全相同。
4. 乘积类型的工程意义
乘积类型适合表达必须同时成立的数据约束。
典型场景:
- 用户信息。
- 数据库记录。
- 配置对象。
- 网络请求参数。
- 业务实体。
- 函数的多个输入参数。
它可以将多个相关字段组合成一个具有明确结构的整体。
四、和类型(Sum Type)
和类型表示一个值只能从多个候选分支中选择一个。
它强调的是“多种可能状态”,而不是多个字段同时存在。
1. 基本结构
例如,支付方式可以是银行卡、支付宝或微信支付:
type PaymentMethod =
| { type: "card"; cardNumber: string }
| { type: "alipay"; account: string }
| { type: "wechat"; openId: string };
一个 PaymentMethod 值只能属于其中一种分支。
其代数表达式为:
每个分支本身也可以是乘积类型。
因此,和类型可以组合乘积类型,构造更复杂的数据结构。
2. Tagged Union:带标签的和类型
在工程实践中,和类型经常通过标签字段实现。
type Shape =
| {
kind: "circle";
radius: number;
}
| {
kind: "rectangle";
width: number;
height: number;
};
其中:
kind用于标识当前分支。radius只属于圆形分支。width和height只属于矩形分支。
kind 就是判别字段(Discriminant)。
使用判别字段可以让编译器识别当前值所属的分支,并在分支内部缩窄类型。
function getArea(shape: Shape): number {
switch (shape.kind) {
case "circle":
return Math.PI * shape.radius ** 2;
case "rectangle":
return shape.width * shape.height;
}
}
这里的类型缩窄依赖 TypeScript 的控制流分析。
如果新增一个 triangle 分支,严格的穷尽性检查可以帮助发现尚未处理的情况。
3. Rust 中的和类型
Rust 使用 enum 表达带数据的和类型:
enum Message {
Quit,
Move { x: i32, y: i32 },
Write(String),
ChangeColor(u8, u8, u8),
}
Message 包含四种可能的消息:
Quit:不携带数据。Move:携带两个坐标字段。Write:携带字符串。ChangeColor:携带三个颜色分量。
每个枚举值只对应一个变体。
Rust 的 enum 不只是传统意义上只存储整数常量的枚举,它可以携带不同结构的数据,是表达和类型的重要工具。
4. 和类型的工程意义
和类型适合表达互斥状态或有限分支。
典型场景:
- 请求成功或失败。
- 用户登录或未登录。
- 支付方式选择。
- 订单状态。
- 消息类型。
- 语法树节点。
- 业务操作结果。
和类型可以将状态空间显式编码到类型系统中,减少非法状态的表达空间。
五、乘积类型与和类型的组合
ADT 最重要的能力是将乘积类型和和类型嵌套组合。
例如,一个网络请求结果:
type ApiResult =
| {
status: "success";
data: {
id: number;
name: string;
};
}
| {
status: "failure";
error: {
code: number;
message: string;
};
};
这个类型同时使用了两种结构:
- 最外层是和类型:成功或失败。
- 每个分支内部是乘积类型:状态字段与对应数据字段同时存在。
代数表达式:
进一步展开:
这里的表达式是结构示意,实际类型中的标签通常是有限的字面量类型。
1. ADT 的组合结构
flowchart TB
A["代数数据类型 ADT"] --> B["乘积类型 Product"]
A --> C["和类型 Sum"]
B --> D["多个字段同时存在"]
B --> E["Struct / Record / Tuple"]
C --> F["多个分支选择其一"]
C --> G["Enum / Tagged Union"]
D --> H["组合复杂数据结构"]
F --> H
H --> I["嵌套 ADT"]
style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style B fill:#E5F4EC,stroke:#A3CBB5,color:#334155
style C fill:#F3EDFC,stroke:#C4B2E3,color:#334155
style D fill:#FFF5DE,stroke:#E8D29A,color:#334155
style E fill:#E8EDF2,stroke:#B8C3CE,color:#334155
style F fill:#FFF5DE,stroke:#E8D29A,color:#334155
style G fill:#E8EDF2,stroke:#B8C3CE,color:#334155
style H fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style I fill:#E5F4EC,stroke:#A3CBB5,color:#334155
linkStyle default stroke:#A3B8AC,stroke-width:1.5px
2. 通过 ADT 建模业务状态
以订单为例:
type Order =
| {
status: "pending";
createdAt: Date;
}
| {
status: "paid";
paidAt: Date;
transactionId: string;
}
| {
status: "shipped";
paidAt: Date;
shippedAt: Date;
trackingNumber: string;
}
| {
status: "cancelled";
reason: string;
};
传统设计可能使用一个包含大量可选字段的对象:
type WeakOrder = {
status: string;
createdAt?: Date;
paidAt?: Date;
shippedAt?: Date;
transactionId?: string;
trackingNumber?: string;
reason?: string;
};
第二种设计存在较大的非法状态空间:
- 订单状态是
paid,但没有支付时间。 - 订单状态是
shipped,但没有物流单号。 - 订单状态是
cancelled,却包含不相关的支付字段。 - 状态字符串可能出现拼写错误或未知值。
ADT 将不同状态所需的数据放入各自分支,使数据结构与业务状态保持一致。
这并不意味着所有业务约束都能由类型系统自动保证。例如,时间顺序、金额合法性、权限约束等仍然需要业务校验。
六、ADT 与模式匹配(Pattern Matching)
模式匹配是 ADT 最重要的使用方式之一。
它允许程序按照数据结构和具体分支执行不同逻辑。
1. 基本模式匹配
Rust 示例:
enum Result<T, E> {
Ok(T),
Err(E),
}
fn handle_result(result: Result<i32, String>) {
match result {
Result::Ok(value) => {
println!("成功:{}", value);
}
Result::Err(error) => {
println!("失败:{}", error);
}
}
}
match 根据枚举变体匹配当前值。
匹配成功后,还可以提取分支携带的数据。
2. 穷尽性检查(Exhaustiveness Checking)
模式匹配的一个关键特性是穷尽性检查。
假设某个类型有三个分支:
enum Status {
Pending,
Success,
Failed,
}
如果只处理两个分支:
fn process(status: Status) {
match status {
Status::Pending => println!("等待"),
Status::Success => println!("成功"),
}
}
Rust 编译器会报告未覆盖 Failed 分支。
穷尽性检查可以帮助开发者发现遗漏的状态处理逻辑。
其重要价值在于:当类型新增分支时,相关模式匹配代码可以在编译阶段暴露需要修改的位置。
3. 穷尽性检查与默认分支
部分语言允许使用默认分支:
function handleStatus(status: string) {
switch (status) {
case "pending":
return "等待";
case "success":
return "成功";
default:
return "其他状态";
}
}
默认分支可以处理未知值,但它可能掩盖新增分支未被显式处理的问题。
对于有限且受控的业务状态,通常更适合使用穷尽性检查。
TypeScript 可以借助 never 实现:
type Status =
| "pending"
| "success"
| "failed";
function assertNever(value: never): never {
throw new Error(`Unexpected value: ${value}`);
}
function handleStatus(status: Status): string {
switch (status) {
case "pending":
return "等待";
case "success":
return "成功";
case "failed":
return "失败";
default:
return assertNever(status);
}
}
当 Status 新增一个分支而 switch 未处理时,status 将无法被收窄为 never,从而触发类型错误。
需要注意,TypeScript 的类型检查主要发生在编译阶段,运行时外部输入仍然需要验证。
七、ADT 与常见语言的实现
不同语言采用不同语法和实现方式表达 ADT。
| 语言 | 乘积类型 | 和类型 | 典型机制 |
|---|---|---|---|
| Haskell | Record、Tuple | data 多构造器 |
代数数据类型原生支持 |
| Rust | Struct、Tuple Struct | Enum | 枚举变体携带数据 |
| TypeScript | Object、Tuple | Union Type | 联合类型与判别字段 |
| Kotlin | Data Class | Sealed Class / Sealed Interface | 密封层次结构 |
| Swift | Struct、Tuple | Enum | 枚举关联值 |
| OCaml | Record、Tuple | Variant | 变体类型 |
| Scala | Case Class | Sealed Trait / Enum | 密封类型层次 |
| C | Struct | Tagged Union(手动实现) | 结构体、联合体与标签 |