返回专栏
· 13 分钟阅读

代数数据类型(Algebraic Data Types,ADT)


一、什么是代数数据类型

代数数据类型(Algebraic Data Types,简称 ADT)是一种通过组合已有类型来构造新类型的类型系统机制。

它的核心思想是:复杂的数据类型可以由更简单的类型通过两种基本方式组合而成:

  1. 乘积类型(Product Type):一个值同时包含多个字段。
  2. 和类型(Sum Type):一个值可以是多个候选类型中的某一种。

例如,一个用户信息可能由姓名、年龄和邮箱组成,这是乘积类型;一个网络请求结果可能是成功、失败或加载中,这是和类型。

ADT 的核心不是某种具体的数据结构,而是一种类型建模方式。

从类型代数的角度看:

  • 乘积类型表示多个组成部分同时存在。
  • 和类型表示多个候选分支中选择一个。
  • 两者可以嵌套组合,构造复杂的数据模型。

二、代数数据类型的数学基础

ADT 中的“代数”来自类型可以按照类似算术的方式进行组合。

假设:

  • 类型 A 有 m 种可能的值。
  • 类型 B 有 n 种可能的值。

那么:

1. 乘积类型:类型的乘法

乘积类型表示一个值由多个部分共同组成。

|A \times B| = |A| \cdot |B|

例如:

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. 和类型:类型的加法

和类型表示一个值可以属于多个候选类型中的某一种。

|A + B| = |A| + |B|

例如:

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

其基数为:

|1| = 1

单位类型常用于表示没有额外数据的分支。

例如:

enum Status {
    Loading,
    Success(String),
    Failure(String),
}

其中 Loading 可以理解为不携带额外字段的构造分支。

从代数角度看,它类似于一个只包含单位值的分支。

4. 空类型:没有任何值的类型

空类型(Empty Type)没有任何合法值,其基数为:

|0| = 0

在 Rust 中,! 是 Never Type,表示不会正常产生一个值的类型。

fn terminate() -> ! {
    panic!("程序终止");
}

空类型在类型理论中具有重要意义:

  • 它无法被正常构造出一个值。
  • 可以用于表示不可能发生的状态。
  • 可以用于描述不返回的函数。
  • 在某些类型运算中充当和类型的零元。

需要区分:不同语言对空类型、底类型(Bottom Type)和 Never Type 的具体定义可能不同,不能简单认为它们在所有语言中完全等价。

三、乘积类型(Product Type)

乘积类型是多个字段的组合,所有字段共同构成一个完整值。

1. 基本结构

type Point = {
  x: number;
  y: number;
};

Point 同时包含两个坐标字段。

其类型结构可以表示为:

Point = Number \times Number

一个 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;
};

其结构可以理解为:

User = String \times Number \times Address

继续展开:

User = String \times Number \times (String \times String)

乘积类型具有结合性:

(A \times B) \times C \cong A \times (B \times C)

这里的 \cong 表示结构上的同构,并不意味着不同语言中的具体类型声明一定完全相同。

4. 乘积类型的工程意义

乘积类型适合表达必须同时成立的数据约束。

典型场景:

  • 用户信息。
  • 数据库记录。
  • 配置对象。
  • 网络请求参数。
  • 业务实体。
  • 函数的多个输入参数。

它可以将多个相关字段组合成一个具有明确结构的整体。

四、和类型(Sum Type)

和类型表示一个值只能从多个候选分支中选择一个。

它强调的是“多种可能状态”,而不是多个字段同时存在。

1. 基本结构

例如,支付方式可以是银行卡、支付宝或微信支付:

type PaymentMethod =
  | { type: "card"; cardNumber: string }
  | { type: "alipay"; account: string }
  | { type: "wechat"; openId: string };

一个 PaymentMethod 值只能属于其中一种分支。

其代数表达式为:

PaymentMethod = Card + Alipay + Wechat

每个分支本身也可以是乘积类型。

因此,和类型可以组合乘积类型,构造更复杂的数据结构。

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;
      };
    };

这个类型同时使用了两种结构:

  • 最外层是和类型:成功或失败。
  • 每个分支内部是乘积类型:状态字段与对应数据字段同时存在。

代数表达式:

ApiResult = (Success \times UserData) + (Failure \times ErrorData)

进一步展开:

ApiResult = (String \times UserData) + (String \times ErrorData)

这里的表达式是结构示意,实际类型中的标签通常是有限的字面量类型。

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(手动实现) 结构体、联合体与标签