Lean 中简单的基于 refl 的证明问题（但不是 Agda）

Question

为了在精益中定义倾斜堆并证明一些结果，我定义了树的类型和融合操作：

inductive tree : Type
| lf : tree
| nd : tree -> nat -> tree -> tree

def fusion : tree -> tree -> tree
| lf t2 := t2
| t1 lf := t1
| (nd l1 x1 r1) (nd l2 x2 r2) :=
    if x1 <= x2
    then nd (fusion r1 (nd l2 x2 r2)) x1 l1
    else nd (fusion (nd l1 x1 l1) r2) x2 l2

那么，即使是一个极其简单的结果，比如

theorem fusion_lf : ∀ (t : tree), fusion lf t = t := sorry

我卡住了。我真的不知道要开始写这个证明。如果我这样开始：

begin
  intro t,
  induction t with g x d,
  refl,
end

如果 t 是 lf，我可以使用 refl，但如果它是 nd。

我有点迷茫，因为在 Agda 中，这真的很容易。如果我这样定义：

data tree : Set where
  lf : tree
  nd : tree -> ℕ -> tree -> tree

fusion : tree -> tree -> tree
fusion lf t2 = t2
fusion t1 lf = t1
fusion (nd l1 x1 r1) (nd l2 x2 r2) with x1 ≤? x2
... | yes _ = nd (fusion r1 (nd l2 x2 r2)) x1 l1
... | no  _ = nd (fusion (nd l1 x1 r1) r2) x2 l2

那么前面的结果直接用一个refl:

fusion_lf : ∀ t -> fusion lf t ≡ t
fusion_lf t = refl

我错过了什么？

Answer 1

这个证明有效。

theorem fusion_lf : ∀ (t : tree), fusion lf t = t := 
λ t, by cases t; simp [fusion]

如果您尝试 #print fusion.equations._eqn_1 或 #print fusion.equations._eqn_2 等，您可以看到 simp [fusion] 将使用的引理。 case splits与模式匹配中的case splits并不完全相同，因为模式匹配中的case splits实际上重复了case lf lf。这就是为什么我需要做 cases t。通常方程引理是定义等式，但这次不是，老实说我不知道为什么。

Lean 中简单的基于 refl 的证明问题（但不是 Agda）

Simple refl-based proof problem in Lean (but not in Agda)

theorem-proving

agda

lean