LSR 011 - 代数数据类型规范

基本信息

  • LSR 编号 011

  • 标题 代数数据类型规范

  • 作者 Ziyang-Bai

  • 状态 草案

  • 类型 标准规范

  • 创建日期 08-09-2026

  • 归属项目 编译器、标准库、CAS

摘要

定义 Lamina 代数数据类型（Algebraic Data Type, ADT）。ADT 是由若干构造器组成的封闭 tagged union；值创建后不可变，可携带泛型参数，并允许递归定义。

技术规范

1. 范围

本规范只定义封闭 ADT。开放 variant、trait 约束、派生排序和运行期追加构造器不由 ADT 核心语义定义。

ADT 用于表达有固定分支的数据，例如 Option、Result 和 AST 节点。元组仍是匿名积类型，集合仍是无序去重容器；三者不是同一种类型的语法糖。

2. ADT 定义

ADT 使用 type [1] 定义，右侧由一个或多个构造器组成。

type Option<T> =
    Some(T)
  | None

type Result<T, E> =
    Ok(T)
  | Err(E)

  • ADT 是封闭类型，所有构造器必须在定义处列出

  • 外部模块不得为已有 ADT 追加构造器

  • 构造器名称在所属模块内可见

  • 构造器可以使用限定名访问

let a Option<int> = Some(1)
let b Option<int> = Option.None

3. 构造器字段

构造器可以没有字段，或使用位置字段 [2]。

type Ordering =
    Less
  | Equal
  | Greater

type Expr =
    Number(frac)
  | Symbol(text)
  | Add(Expr, Expr)

  • 零字段构造器表示枚举分支

  • 位置字段按声明顺序参与构造和匹配

  • ADT 构造器不定义命名字段

  • ADT 字段默认不可变

4. 泛型 ADT

ADT 可以声明类型参数。

type List<T> =
    Nil
  | Cons(T, List<T>)

  • 类型参数在 ADT 定义体内可作为普通类型使用

  • 构造器使用时必须能确定全部类型参数

  • 无法推导类型参数时报错

  • where 约束不属于 ADT 核心语法

5. 递归 ADT

ADT 可以直接或间接递归引用自身。

type Tree<T> =
    Empty
  | Node(Tree<T>, T, Tree<T>)

  • 递归 ADT 的运行时表示必须避免无限大小值

  • 编译器必须能区分递归类型定义和非法循环别名

  • 递归值仍遵循不可变语义

6. 构造表达式

构造器调用产生对应 ADT 值。

let ok = Ok(1)
let expr = Add(Symbol("x"), Number(1/2))

  • 构造器实参与字段声明必须匹配

  • 实参数量不匹配是编译错误

  • 构造器本身不是可变对象

7. 模式匹配

ADT 通过 match 解构。

match value {
    Some(x) => x
    None => 0
}

match expr {
    Add(lhs, rhs) => lhs + rhs
    Number(n) => n
    _ => 0
}

  • 对封闭 ADT 的 match 必须穷尽

  • 非穷尽匹配是编译错误，除非存在 _ 分支

  • 不可达分支应产生诊断

  • 构造器模式的字段数量必须匹配构造器定义

8. 相等性与哈希

ADT 的结构相等按构造器和字段递归比较。

  • 两个 ADT 值构造器不同，则 == 为 false

  • 构造器相同且所有字段相等，则 == 为 true

  • 只有所有字段可比较时，ADT 才支持 ==

  • 只有所有字段可哈希时，ADT 才可作为哈希键

  • ADT 不自动获得排序关系；可相等 ADT 值可作为集合元素 [3]

9. 与 null 和可空类型的关系

null 不属于 ADT 值，除非字段类型显式可空。

type Box =
    Box(text?)

  • Option<T> 可由标准库定义为 ADT

  • T? 与 Option<T> 不自动互转

  • 需要互转时必须通过显式标准库函数完成

10. 引用