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]_ 定义，右侧由一个或多个构造器组成。

.. code-block:: text

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

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


- ADT 是封闭类型，所有构造器必须在定义处列出
- 外部模块不得为已有 ADT 追加构造器
- 构造器名称在所属模块内可见
- 构造器可以使用限定名访问

.. code-block:: text

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

3. 构造器字段
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


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

.. code-block:: text

   type Ordering =
       Less
     | Equal
     | Greater

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


- 零字段构造器表示枚举分支
- 位置字段按声明顺序参与构造和匹配
- ADT 构造器不定义命名字段
- ADT 字段默认不可变

4. 泛型 ADT
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


ADT 可以声明类型参数。

.. code-block:: text

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


- 类型参数在 ADT 定义体内可作为普通类型使用
- 构造器使用时必须能确定全部类型参数
- 无法推导类型参数时报错
- ``where`` 约束不属于 ADT 核心语法

5. 递归 ADT
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


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

.. code-block:: text

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


- 递归 ADT 的运行时表示必须避免无限大小值
- 编译器必须能区分递归类型定义和非法循环别名
- 递归值仍遵循不可变语义

6. 构造表达式
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


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

.. code-block:: text

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


- 构造器实参与字段声明必须匹配
- 实参数量不匹配是编译错误
- 构造器本身不是可变对象

7. 模式匹配
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


ADT 通过 ``match`` 解构。

.. code-block:: text

   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 值，除非字段类型显式可空。

.. code-block:: text

   type Box =
       Box(text?)


- ``Option<T>`` 可由标准库定义为 ADT
- ``T?`` 与 ``Option<T>`` 不自动互转
- 需要互转时必须通过显式标准库函数完成

10. 引用
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

.. [1] :doc:`LSR-000 - Lamina 核心语言规范（草案） <LSR-000>` - 提供 ``type``、``match``、泛型与可空类型的基础语义
.. [2] :doc:`LSR-012 - 元组类型规范 <LSR-012>` - 定义元组；ADT 构造器的位置字段可包含元组值
.. [3] :doc:`LSR-013 - 集合类型规范 <LSR-013>` - 集合元素可以是可相等的 ADT 值