精益中有根据的递归

Question

我正在尝试将精益中的斜堆形式化。我已经定义了简单的树类型：

inductive tree : Type
| leaf : tree
| node : tree -> nat -> tree -> tree

接下来，我想按以下方式定义融合操作：

def fusion : arbre × arbre -> arbre
| (t1, leaf) := t1
| (leaf, t2) := t2
| (node g1 x1 d1, node g2 x2 d2) :=
    if x1 <= x2
    then (node (fusion (d1, node g2 x2 d2)) x1 g1)
    else (node (fusion (d2, node g1 x1 d1)) x2 g2)

但是，当然，精益并不接受这个功能，因为它 "failed to prove recursive application is decreasing, well founded relation"。显然，它使用了树大小的字典序乘积……显然失败了。

如何告诉它使用大小的总和？

Answer 1

以下代码适用于我。

上有关于递归在精益中的工作原理的文档

https://github.com/leanprover-community/mathlib/blob/master/docs/extras/well_founded_recursion.md

def fusion : tree × tree -> tree
| (t1, leaf) := t1
| (leaf, t2) := t2
| (node g1 x1 d1, node g2 x2 d2) :=
    if x1 <= x2
    then (node (fusion (d1, node g2 x2 d2)) x1 g1)
    else (node (fusion (d2, node g1 x1 d1)) x2 g2)
using_well_founded 
  { rel_tac := λ _ _, 
    `[exact ⟨_, measure_wf (λ t, tree.sizeof t.1 + tree.sizeof t.2)⟩] }

这个想法是你必须给它一个新的关系，并证明这个关系是有根据的。这是元组 ⟨_, measure_wf (λ t, tree.sizeof t.1 + tree.sizeof t.2)⟩ 自然数的任何函数都给出了一个有根据的关系，证明是 measure_wf，而 _ 只是该关系的一个占位符，因为它可以从 measure_wf (λ t, tree.sizeof t.1 + tree.sizeof t.2).

的类型推断

精益中有根据的递归

Well-founded recursion in Lean

theorem-proving

lean