Lean 语言参考手册

20.14. 和类型🔗

和类型表示两种类型之间的选择:和类型的一个元素是这两种类型之一的元素,并配有指示其来源类型的标记。 和类型也称为不相交并集、可辨识联合或标记联合。 和类型的构造子也称为单射;在数学上,它们可以被视为从每个被加数到和类型的单射函数。

和类型有两种变体:

  • Sum多态的,覆盖所有 Type 宇宙,并且永远不是命题

  • PSum 允许被加数为命题或类型。与 Or 不同,两个命题的 PSum 仍然是一个类型,并且非命题代码可以检查用于构造给定值的是哪个单射。

手动编写的 Lean 代码几乎总是只使用 Sum,而 PSum 则作为证明自动化实现的一部分使用。 这是因为它施加了宇宙层级合一无法解决的棘手约束。 特别地,该类型位于宇宙 Sort (max 1 u v) 中,这可能会给宇宙层级合一带来问题,因为等式 max 1 u v = ?u + 1 在层级算术中无解。 PSum 通常仅用于构造任意类型之和的自动化中。

🔗归纳类型
Sum.{u, v} (α : Type u) (β : Type v) : Type (max u v)
Sum.{u, v} (α : Type u) (β : Type v) : Type (max u v)

类型 αβ 的不交并,通常写作 α β

α β 的元素要么是由 a : αSum.inl 包装得到的值,要么是由 b : βSum.inr 包装得到的值。α β 不等价于 αβ 的集合论并集,因为其值还包含从两种类型中选择了哪一种的信息。单元素集合与自身的并集只有一个元素,而 Unit Unit 包含不同的值 inl ()inr ()

Sum.inl.{u, v} {α : Type u} {β : Type v} (val : α) : α  β

到和类型 α β 的左注入。

Sum.inr.{u, v} {α : Type u} {β : Type v} (val : β) : α  β

到和类型 α β 的右注入。

🔗归纳类型
PSum.{u, v} (α : Sort u) (β : Sort v) : Sort (max (max 1 u) v)
PSum.{u, v} (α : Sort u) (β : Sort v) : Sort (max (max 1 u) v)

任意排序 α βα ⊕' β 的不相交并集。

它与 α β 的不同之处在于,它允许 αβ 具有任意排序 Sort uSort v,而不是将它们限制为 Type uType v。这意味着它可以用在一侧是命题的情况下,例如 True ⊕' Nat。然而,由此产生的宇宙级约束通常比 Sum 产生的约束更难解决。

PSum.inl.{u, v} {α : Sort u} {β : Sort v} (val : α) : α ⊕' β

到和类型 α ⊕' β 的左注入。

PSum.inr.{u, v} {α : Sort u} {β : Sort v} (val : β) : α ⊕' β

到和类型 α ⊕' β 的右注入。

20.14.1. 语法🔗

名称 SumPSum 很少被显式写出。 大多数代码使用相应的插缀运算符。

语法和类型
term ::= ...
    | term  term

α βSum α β 的记号。

语法潜在命题和类型
term ::= ...
    | term ⊕' term

α ⊕' βPSum α β 的记号。

20.14.2. API 参考🔗

和类型主要与模式匹配一起使用,而不是来自 API 的显式函数调用。 因此,它们的主要 API 是构造子 inlinr

20.14.2.1. 分情况讨论🔗

🔗定义
Sum.isLeft.{u_1, u_2} {α : Type u_1} {β : Type u_2} : α β Bool
Sum.isLeft.{u_1, u_2} {α : Type u_1} {β : Type u_2} : α β Bool

检查总和是否为左注入inl

🔗定义
Sum.isRight.{u_1, u_2} {α : Type u_1} {β : Type u_2} : α β Bool
Sum.isRight.{u_1, u_2} {α : Type u_1} {β : Type u_2} : α β Bool

检查总和是否是正确的注入 inr

20.14.2.2. 提取值🔗

🔗定义
Sum.elim.{u_1, u_2, u_3} {α : Type u_1} {β : Type u_2} {γ : Sort u_3} (f : α γ) (g : β γ) : α β γ
Sum.elim.{u_1, u_2, u_3} {α : Type u_1} {β : Type u_2} {γ : Sort u_3} (f : α γ) (g : β γ) : α β γ

在检查存在哪个构造函数后,对应用适当函数 fg 的求和进行案例分析。

🔗定义
Sum.getLeft.{u_1, u_2} {α : Type u_1} {β : Type u_2} (ab : α β) : ab.isLeft = true α
Sum.getLeft.{u_1, u_2} {α : Type u_1} {β : Type u_2} (ab : α β) : ab.isLeft = true α

从已知为 inl 的总和中检索内容。

🔗定义
Sum.getLeft?.{u_1, u_2} {α : Type u_1} {β : Type u_2} : α β Option α
Sum.getLeft?.{u_1, u_2} {α : Type u_1} {β : Type u_2} : α β Option α

检查总和是否为左注入 inl,如果是,则检索其内容。

🔗定义
Sum.getRight.{u_1, u_2} {α : Type u_1} {β : Type u_2} (ab : α β) : ab.isRight = true β
Sum.getRight.{u_1, u_2} {α : Type u_1} {β : Type u_2} (ab : α β) : ab.isRight = true β

从已知为 inr 的总和中检索内容。

🔗定义
Sum.getRight?.{u_1, u_2} {α : Type u_1} {β : Type u_2} : α β Option β
Sum.getRight?.{u_1, u_2} {α : Type u_1} {β : Type u_2} : α β Option β

检查总和是否是正确的注入 inr,如果是,则检索其内容。

20.14.2.3. 转换🔗

🔗定义
Sum.map.{u_1, u_2, u_3, u_4} {α : Type u_1} {α' : Type u_2} {β : Type u_3} {β' : Type u_4} (f : α α') (g : β β') : α β α' β'
Sum.map.{u_1, u_2, u_3, u_4} {α : Type u_1} {α' : Type u_2} {β : Type u_3} {β' : Type u_4} (f : α α') (g : β β') : α β α' β'

根据每种类型的函数转换总和。

该函数将 α β 映射到 α' β',将 α 发送到 α',将 β 发送到 β'

🔗定义
Sum.swap.{u_1, u_2} {α : Type u_1} {β : Type u_2} : α β β α
Sum.swap.{u_1, u_2} {α : Type u_1} {β : Type u_2} : α β β α

交换和类型的因子。

构造函数 Sum.inl 替换为 Sum.inr,反之亦然。

20.14.2.4. 居留性🔗

InhabitedSumPSum 的定义没有被注册为实例。 这是因为有两种不同的方法来构造默认值(通过 inlinr),而实例合成可能会导致任一选择。 结果可能是两种写法完全相同的项却精译出不同的结果,并且它们不是定义等价的。

这两种类型都有 Nonempty 实例,由于证明无关性,选择 inl 还是 inr 并不重要。 这足以启用 partial 函数。 对于需要 Inhabited 实例的情况,例如使用 panic! 的程序,可以通过 Lean.Parser.Term.have : termhaveLean.Parser.Term.let : termlet 将其添加到局部上下文中来显式使用该实例。

具有居留性的和类型

在 Lean 的逻辑中,Lean.Parser.Term.panic : termpanic! 等同于在其类型的 Inhabited 实例中指定的默认值。 这意味着该类型必须具有这样的实例——Nonempty 实例结合选择公理会使程序变得不可计算。

积类型具有合适的实例:

example : Nat × String := panic! "Can't find it"

和类型默认情况下没有:

example : Nat String := failed to synthesize instance of type class Inhabited (Nat String) Hint: Type class instance resolution failures can be inspected with the `set_option trace.Meta.synthInstance true` command.panic! "Can't find it"
failed to synthesize instance of type class
  Inhabited (Nat  String)

Hint: Type class instance resolution failures can be inspected with the `set_option trace.Meta.synthInstance true` command.

可以使用 Lean.Parser.Term.have : termhave 使所需的实例对实例合成可用:

example : Nat String := have : Inhabited (Nat String) := Sum.inhabitedLeft panic! "Can't find it"
🔗定义
Sum.inhabitedLeft.{u, v} {α : Type u} {β : Type v} [Inhabited α] : Inhabited (α β)
Sum.inhabitedLeft.{u, v} {α : Type u} {β : Type v} [Inhabited α] : Inhabited (α β)

如果总和中的左侧类型被占据,则总和被占据。

当左类型和右类型都存在时,这不是避免非规范实例的实例。

🔗定义
Sum.inhabitedRight.{u, v} {α : Type u} {β : Type v} [Inhabited β] : Inhabited (α β)
Sum.inhabitedRight.{u, v} {α : Type u} {β : Type v} [Inhabited β] : Inhabited (α β)

如果总和中存在正确的类型,那么总和就存在。

当左类型和右类型都存在时,这不是避免非规范实例的实例。

🔗定义
PSum.inhabitedLeft.{u_1, u_2} {α : Sort u_1} {β : Sort u_2} [Inhabited α] : Inhabited (α ⊕' β)
PSum.inhabitedLeft.{u_1, u_2} {α : Sort u_1} {β : Sort u_2} [Inhabited α] : Inhabited (α ⊕' β)

如果总和中的左侧类型被占据,则总和被占据。

当左类型和右类型都存在时,这不是避免非规范实例的实例。

🔗定义
PSum.inhabitedRight.{u_1, u_2} {α : Sort u_1} {β : Sort u_2} [Inhabited β] : Inhabited (α ⊕' β)
PSum.inhabitedRight.{u_1, u_2} {α : Sort u_1} {β : Sort u_2} [Inhabited β] : Inhabited (α ⊕' β)

如果总和中存在正确的类型,那么总和就存在。

当左类型和右类型都存在时,这不是避免非规范实例的实例。