LSR 013 - 集合类型规范
================================================================================


基本信息
--------------------------------------------------------------------------------


- LSR 编号 013
- 标题 集合类型规范
- 作者 Ziyang-Bai
- 状态 草案
- 类型 标准规范
- 创建日期 08-09-2026
- 归属项目 编译器、标准库、CAS

摘要
--------------------------------------------------------------------------------


定义 Lamina 集合类型。集合表示有限、无序、去重、同构的值集合；可用于数学表达、CAS 多结果返回和标准库容器。

技术规范
--------------------------------------------------------------------------------


1. 范围
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


本规范只定义有限集合。无限集合、区间、条件集、全集和带重数集合不由 ``set<T>`` 表示。

集合与元组、ADT 的边界固定：集合无序且同构；元组有序且可异构；ADT [3]_ 是带构造器标签的分支类型。

2. 集合类型
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


集合类型写作 ``set<T>`` [1]_。

.. code-block:: text

   let a set<int> = {1, 2, 3}
   let b set<Expr> = {x, x + 1}


- ``set<T>`` 表示元素类型为 ``T`` 的集合
- 集合元素必须可比较相等
- 集合不保证迭代顺序
- 集合中不存在重复元素
- 集合值默认不可变

3. 集合字面量
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


集合字面量使用花括号。

.. code-block:: text

   let ints = {1, 2, 3}
   let nums = {1, 1/2, 3}
   let empty set<int> = {}


- 非空集合按元素类型统一推导 ``set<T>``
- 空集合必须由上下文推出元素类型，否则需要显式类型标注
- 无法统一元素类型时报错
- 集合字面量中的重复元素只保留一个

4. 元素类型统一
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


集合元素必须统一为单一元素类型。

- 数值元素按 LSR-000 [1]_ 数值塔统一
- ``Expr`` 与可提升为 ``Expr`` 的元素混合时，整体可提升为 ``set<Expr>``
- 不可比较相等的类型不得作为集合元素
- 若元素类型没有明确相等语义，必须报错

5. 集合运算
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


.. list-table::
   :header-rows: 1

   * - 运算
     - 说明
     - 示例
   * - ``in`` / ``not in``
     - 元素从属
     - ``2 in {1,2,3}``
   * - ``subset``
     - 子集判断
     - ``{1,2} subset {1,2,3}``
   * - ``|``
     - 并集
     - ``{1,2} | {2,3}``
   * - ``&``
     - 交集
     - ``{1,2} & {2,3}``
   * - ``-``
     - 差集
     - ``{1,2} - {2}``
   * - ``xor``
     - 对称差
     - ``{1,2} xor {2,3}``


- 二元集合运算的两个操作数必须是集合
- 两个集合的元素类型必须相同或可统一
- 运算结果类型为统一后的 ``set<T>``
- ``in`` 左侧元素类型必须可与右侧集合元素类型统一
- ``subset`` 返回 ``bool``

6. 集合相等
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


集合相等忽略元素顺序。

.. code-block:: text

   {1, 2, 3} == {3, 2, 1}   # true


- 两个集合元素类型必须相同或可统一
- 两个集合包含相同元素时相等
- 元素比较使用元素类型的相等性语义
- 集合相等不得依赖迭代顺序

7. 集合推导式
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


集合推导式产生集合值。

.. code-block:: text

   let squares = { x^2 for x in {1, 2, 3} }


- 推导式结果元素按表达式类型统一
- 推导式输入必须可迭代
- 推导式结果自动去重
- 集合推导式不得产生无限集合

8. 多结果返回
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


Lamina 不定义语言级多值返回。函数仍然只有一个返回值；当结果是多个同类、无序值时，返回 ``set<T>``。

.. code-block:: text

   func roots(expr Expr, var Expr) -> set<Expr>
   func solve(eq Expr, var Expr) -> set<Expr>


- 无解返回空集合，不是错误
- 多个同类数学结果返回集合 [2]_
- 多个不同类型结果返回元组
- 需要携带成功/失败状态时使用 ADT [3]_，例如 ``Result<set<T>, E>``

9. 有限性
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


``set<T>`` 表示有限集合；可相等元组可作为集合元素 [4]_。

- 无限集合不由 ``set<T>`` 表示
- 区间、条件集、全集等数学对象应由 CAS 或标准库定义专门类型
- CAS 不能证明有限枚举结果时，不得伪造 ``set<T>`` 成功结果

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

.. [1] :doc:`LSR-000 - Lamina 核心语言规范（草案） <LSR-000>` - 提供集合字面量、集合运算符和基础类型规则
.. [2] :doc:`LSR-009 - 集合与多结果返回规范 <LSR-009>` - 本规范细化集合类型；LSR-009 中多结果返回约定仍适用
.. [3] :doc:`LSR-011 - 代数数据类型规范 <LSR-011>` - 定义 ADT；集合元素可以是可相等 ADT 值
.. [4] :doc:`LSR-012 - 元组类型规范 <LSR-012>` - 集合元素可以是可相等元组值