联合类型与和类型

# 联合类型 vs 和类型 来源: https://viralinstruction.com/posts/uniontypes/ *写于 2021-10-06* 联合类型与和类型是编程语言中存在数十年的概念，但我认为近年来它们正变得越来越流行。这两个概念紧密相关，但它们微妙的差异影响了各自的优势。本文旨在解释这些概念，并列出两者的优缺点。 ## 结构体是“乘积类型”(https://viralinstruction.com/posts/uniontypes/#structs_are_product_types) 联合类型、和类型与乘积类型都属于*代数数据类型*，这听起来非常复杂，但基本概念其实非常简单。让我们从一个熟悉的地方开始：一个普通的结构体。我工作使用的数据库包含“案例”，它们通过如下标识符进行标识： ``` struct CaseID_V2 { year: u16, number: u32 } ``` 这个定义创建了一个新类型 `CaseID_V2`。我们可以将结构体视为一个与（AND）运算符：`CaseID_V2` 是由一个 `u16` **与** 一个 `u32` 组成的新类型。 那么，*类型*究竟是什么？嗯，可以将类型看作是一组可能的值。这里以 `u16` 为例： `u16 = {0x0000, 0x0001, 0x0002 ... 0xffff}` `CaseID_V2` 有哪些值呢？如果一个 `CaseID_V2` 是由一个 `u16` **和** 一个 `u32` 组成，那么 `CaseID_V2` 的可能值集合就是这两个类型的笛卡尔积（即所有可能的组合，用 × 表示）： `CaseID_{V2} = u16 × u32` 这就是结构体被称为乘积类型的原因。事实就是如此简单。 ## 联合类型(https://viralinstruction.com/posts/uniontypes/#union_types) 但有时，我们想要的新类型不是由一个字段**与**另一个字段组成，而是一个字段**或**另一个字段。实际上，我工作中使用的同一个数据库出于某些原因在 2021 年更改了其 `CaseID`，因此在前面的例子中有 `_V2` 后缀。旧的定义如下： ``` struct CaseID_V1 { numbers: u32, letters: u32 // 以 36 进制编码 } ``` 现在，任何包含案例 ID 的数据类型都必须能够包含 `CaseID_V1` **或** `CaseID_V2`。我们称这种“或”类型为*联合类型*。用伪代码表示，它看起来像： ``` union type CaseID { CaseID_V1, CaseID_V2 } ``` 然后我们可以将其放入结构体中，如果我们想的话： ``` struct Case { id: CaseID, creation: Date, [ 等等 ] } ``` 为什么我们称它为联合类型？原因类似于我们将结构体称为乘积类型。新联合类型中的可能值是其成员的*联合*： `CaseID = CaseID_{V1} ∪ CaseID_{V2}` 由于它的值要么是 `CaseID_V1`，要么是 `CaseID_V2`，显然其可能值集合就是这两个集合中的所有值，或者等效地，是这两个集合的并集。 ## 联合类型擅长集合运算(https://viralinstruction.com/posts/uniontypes/#union_types_is_good_for_set_operations) 然而，这里有一个困境：如果我们这样做会怎样？ ``` union type MyType { bool, bool } ``` 这表示 `MyType` 是一个 `bool` **或**一个…… `bool`？这有多少个可能值？ `MyType = {false, true} ∪ {false, true} = {false, true} = bool` 它仍然是集合 `{false, true}`！换句话说，`MyType` 等价于 `bool`。甚至可以说它*就是* `bool`。这种简化非常巧妙，因为它允许我们将对类型的不确定性表示为联合类型，并对这些类型进行集合运算。 例如，假设你有函数 `f`，它返回联合类型 `f(x) = u16 ∪ i16`，以及函数 `g`，它返回 `g(x) = u16 ∪ u32`，总共涉及四种可能的类型。如果你现在调用 `f` **或** `g`，你可能的返回类型是什么？它只是 `f(x) ∪ g(x) = u16 ∪ i16 ∪ u32`，“去重”后只有三种类型。如果你联合的两个类型中，一个是另一个的超集，也会发生类似的简化。例如，假设你的语言有一个类型 `uint`，它表示“任何无符号整数”，无论其宽度。在这种情况下，`u16 ∪ uint = uint`——毕竟，`uint` 的值集*包含*了 `u16` 的集合。 ## 和类型(https://viralinstruction.com/posts/uniontypes/#sum_types) 有时在编程中，你并不一定想要这种去重。假设你想创建一个联合类型，它包含*要么*公历年份（存储为 `u16`），*要么*回历年份（也存储为 `u16`）。你不能用联合类型 `T = u16 ∪ u16 = u16` 来表达这一点，因为在这两个情况下，这两个 `u16` 是*不同的东西*，只是恰好有相同的表示，但不应混为一谈。 解决方案相当直接：你创建两个新类型来包装 `u16`，作为“类型标签”，以便程序知道如何解释数据。类似于： ``` struct Year_Gregorian { val: u16 } struct Year_Hijri { val: u16 } union type Year { Year_Gregorian, Year_Hijri } ``` 这种类型——每个成员都带有标签的联合类型——被称为*标签联合*。它也被称为*和类型*。现在你可以猜出为什么叫和类型了：类型 `Year` 的值数量正好是其成员数量之和：`|Year| = |Year_{Gregorian}| + |Year_{Hijri}|`。当你想要 100% 确定能够区分联合中的所有成员时，和类型非常有用。 ## Rust 中的和类型(https://viralinstruction.com/posts/uniontypes/#sum_types_in_rust) Rust 将和类型称为“枚举”（一个不太准确的名称）。你可以很容易地创建非常复杂的和类型： ``` enum ComplicatedEnum { IsEmpty, Color(u8, u8, u8), Name { given: String, sur: String } } ``` Rust 枚举的一个有趣之处在于：这三个“变体” `IsEmpty`、`Color` 和 `Name` 不是定义三个普通类型，它们只能作为 `ComplicatedEnum` 的一部分存在，而不能独立存在。这意味着没有值可以具有类型 `IsEmpty`：`ComplicatedEnum` 的所有值都只是类型 `ComplicatedEnum`。我认为在 Rust 中对和类型进行这种“强制包装”没有重大的理论原因，但它对 Rust 和类型的实际使用有重要影响，我稍后会提到。 ## Julia 中的联合类型(https://viralinstruction.com/posts/uniontypes/#union_types_in_julia) 在 Julia 中，类型与“类型即值的集合”的概念完美匹配： ``` julia> 5 isa Int # 检查 5 是否是 Int 的实例 true julia> 5 isa Union{Int, String} true julia> 5 isa Integer # Integer 是 Int 的超集 true julia> 5 isa Union{String, Set, Char} false julia> Union{Int, Integer, Char, UInt, Int} # 去重 Union{Char, Integer} ``` 简而言之，值 `5` 同时属于类型 `Int`、`Union{Int, String}`、`Integer` 以及无限多种其他类型。与 Rust 的另一个区别是 Julia 是动态语言。简而言之，在静态语言中，表达式（例如代码）有类型，但类型在运行时并不存在，因为它们被优化掉了，一切都只是二进制块。在动态语言中，值在运行时具有类型，而编译器在运行前推断出的任何类型都无关紧要：它对运行时实际产生的值或类型没有影响。这意味着，即使编译器将某些值 `x` 推断为类型 `Union{A, B, C}`，在运行时，`x` 的类型将只是 `A`、`B` 或 `C`。联合类型在运行时不存在。它们仅用于表达编译器对程序运行时将发生什么的不确定性。 ## Julia 联合类型相对于 Rust 和类型的优势(https://viralinstruction.com/posts/uniontypes/#advantages_of_julias_union_types_over_rusts_sum_types) Julia 和 Rust 类型之间的许多差异实际上源于 Rust 和类型的“强制包装”，而不一定是因为它们是和类型而不是联合类型。 #### 向后兼容的更改(https://viralinstruction.com/posts/uniontypes/#backwards_compatible_changes) 如果你有一个期望接收 `A` 的 API，你总是可以将其更改为接收 `Union{A, B}` 而不会破坏兼容性，因为所有类型为 `A` 的值也是类型 `Union{A, B}` 的值。类似地，如果你的函数返回 `Union{A, B}`，你可以将其更改为仅返回 `A` 而不会破坏兼容性。这在 Rust 中行不通：你不能在不破坏用户代码的情况下，将一个接受 `Option` 的函数更改为接受 `usize`，也不能在之前返回 `usize` 的地方返回 `usize`。 #### 无需包装和解包和类型(https://viralinstruction.com/posts/uniontypes/#no_need_to_wrap_and_unwrap_sum_types) 在 Rust 中，你不能直接访问和类型的变体，因为它们总是被包装的。这导致了*大量*样板代码：查看 `Option` ([https://doc.rust-lang.org/std/option/enum.Option.html](https://doc.rust-lang.org/std/option/enum.Option.html)) 和 `Result` ([https://doc.rust-lang.org/std/result/enum.Result.html](https://doc.rust-lang.org/std/result/enum.Result.html)) 的长长方法列表，这些方法仅用于在各种情况下解包和重新包装这些类型。使用 Julia 的系统要容易得多：你无需解包和重新包装，因为它根本没有被包装。如果 `x` 是 `Union{Int, UInt}`，你如何给它加 1？只需 `x + 1`，就像任何普通整数一样。 #### 编译器优化的更多可能性(https://viralinstruction.com/posts/uniontypes/#more_possibilities_for_compiler_optimization) 就像返回更窄的联合类型或接受更宽的类型不是破坏性更改一样，这也是一种允许的编译器更改。假设你编写了一个函数 `f`，它返回 `Union{A, B}`，并且你将其传递给期望该类型的函数 `g`。但现在，在某些代码中，你使用常量作为参数之一调用 `f`。编译器随后将检查该常量参数是否缩小了 `f` 的返回类型。假设通过常量折叠，参数 `f` 保证返回 `A`。如果是这样，编译器将知道 `g` 将获得一个 `A`，而不是一个 `Union{A, B}`——因此现在 `g` 可以被进一步优化，例如通过编译掉所有当输入是 `B` 时出现的分支。 ## Rust 和类型相对于 Julia 联合类型的优势(https://viralinstruction.com/posts/uniontypes/#advantages_of_rusts_sum_types_over_julias_union_types) #### 解包迫使你记住正在处理和类型(https://viralinstruction.com/posts/uniontypes/#unwrapping_forces_you_to_remember_youre_dealing_with_a_sum_type) Julia 的联合类型可能样板代码更少，因为你可以像使用具体类型一样使用它们——但这也是一个危险的陷阱。考虑 Julia 函数 `findfirst`，它返回 `Union{Int, Nothing}`，对比 Rust 的 `iter.position`，它返回 `Option`：很容易忘记 `findfirst` 可能返回 nothing 并且没有处理这种情况，从而引入 bug。但不可能将 `Option` 误认为 `usize`，因为它们是不兼容的类型，你*必须*解包和类型。 #### 包装类型更直接，因此更显式(https://viralinstruction.com/posts/uniontypes/#wrapped_types_are_more_straightforward_and_therefore_explicit) 当你只是想编码时，联合类型所能进行的复杂集合运算也可能相当烦人。例如，假设 `f` 是一个返回类型 `T` 的函数。下面这段 Rust 代码的返回类型是什么？ 是的，是 `Vec<T>`。 现在，这段 Julia 代码的返回类型是什么？ 显然是 `Vector{T}`！对吗？不，不一定： ``` julia> f() = rand(Bool) ? 1 : nothing; julia> g() = [f()]; julia> only(Core.Compiler.return_types(g, ())) Union{Vector{Int64}, Vector{Nothing}} ``` 它不是联合的向量，而是向量的联合。仔细想想这是必然的，但这只是联合类型可以“突然在你脚下做些聪明事”的例子之一。 #### 没有编译器优化意味着没有编译器成本(https://viralinstruction.com/posts/uniontypes/#no_compiler_optimizations_mean_no_compiler_costs) 上面提到的由联合类型自动限制实现的 Julia 编译器优化很巧妙。但如果你的联合类型由例如 10 个变体组成会怎样？如果你的语言为每种输入类型编译专门的函数（“单态化”），就像 Julia 和 Rust 那样，这可能导致组合爆炸，从而导致巨大的编译时间和膨胀的代码。事实上，在 Julia 中，情况变得如此糟糕，以至于如果编译器推断一个值是超过 4 个成员的联合，它就会放弃并发出在运行时检查类型的代码。在这种情况下，使用 if/else 语句简单地检查你拥有哪个变体比聪明的编译器技巧要有效得多。甚至比 if/else 语句更好…… #### 穷尽模式匹配(https://viralinstruction.com/posts/uniontypes/#exhaustive_pattern_matching) 正是因为 Rust 的和类型不做这些聪明的类型操作，用户可以确信具有变体 `A`、`B` 和 `C` 的和类型仍然是具有相同变体的相同类型。这实现了*穷尽模式匹配*：这种模式匹配将在编译时检测到你是否遗漏了任何边界情况。如果你使用 Rust 超过 5 分钟，你已经知道这是自切片面包以来最好的东西。如果还没有，我*强烈*建议你尝试一下，以便你知道在你*最喜爱的语言*中拥有它会有多好。 ## 结论(https://viralinstruction.com/posts/uniontypes/#conclusion) 联合类型与和类型各有优势。非常合适的是，联合类型发挥了 Julia 的优势：它们能够生成富有表现力（低样板）、通用且快速的代码。另一方面，Rust 的和类型支持具有可预测类型的代码，并通过强制检查边界情况实现更安全的代码。我并不相信联合类型与和类型之间的这种权衡是固有的。我认为可能实现鱼与熊掌兼得，但我还不确定这样的系统会是什么样子。希望将来这会是一篇博客文章——或者一个 Julia 包！