internlm/Lean-Github huggingface dataset:
Theorem: project.deleteMin_non_empty
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
h₂ : IsMinHeap le (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
x✝⁴ : List (BinTree α)
x✝³ : ℕ
x✝² : BinTree α × ℕ
bt : BinTree α
ts : List (BinTree α)
h'✝ : BinTree α
idx'✝ : ℕ
heq✝ : (t₁, 0) = (h'✝, idx'✝)
hne₂ : bt :: ts = [] → False
h✝ : ¬le h'✝.val bt.val = true
left✝ : (findMin le ts (1 + 1) (bt, 1)).fst.val = y
x✝¹ x✝ : Heap α
ts₂ ts₃ : List (HeapNodeAux α (Heap α))
heq₃ : Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd) = Heap.heap ts₂
heq₄ : (findMin le ts (1 + 1) (bt, 1)).fst.children = Heap.heap ts₃
heq : Heap.heap (mergeNodes le ts₂ ts₃) = ys
heqh : h = t₁ ∧ hs = bt :: ts
⊢ IsMinHeap le (Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd))
Tactic:
apply IsMinHeap_eraseIdx
Proof state after:
case a
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
h₂ : IsMinHeap le (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
x✝⁴ : List (BinTree α)
x✝³ : ℕ
x✝² : BinTree α × ℕ
bt : BinTree α
ts : List (BinTree α)
h'✝ : BinTree α
idx'✝ : ℕ
heq✝ : (t₁, 0) = (h'✝, idx'✝)
hne₂ : bt :: ts = [] → False
h✝ : ¬le h'✝.val bt.val = true
left✝ : (findMin le ts (1 + 1) (bt, 1)).fst.val = y
x✝¹ x✝ : Heap α
ts₂ ts₃ : List (HeapNodeAux α (Heap α))
heq₃ : Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd) = Heap.heap ts₂
heq₄ : (findMin le ts (1 + 1) (bt, 1)).fst.children = Heap.heap ts₃
heq : Heap.heap (mergeNodes le ts₂ ts₃) = ys
heqh : h = t₁ ∧ hs = bt :: ts
⊢ IsMinHeap le (Heap.heap (t₁ :: bt :: ts))
Theorem: project.deleteMin_non_empty
Proof state before:
case a
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
h₂ : IsMinHeap le (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
x✝⁴ : List (BinTree α)
x✝³ : ℕ
x✝² : BinTree α × ℕ
bt : BinTree α
ts : List (BinTree α)
h'✝ : BinTree α
idx'✝ : ℕ
heq✝ : (t₁, 0) = (h'✝, idx'✝)
hne₂ : bt :: ts = [] → False
h✝ : ¬le h'✝.val bt.val = true
left✝ : (findMin le ts (1 + 1) (bt, 1)).fst.val = y
x✝¹ x✝ : Heap α
ts₂ ts₃ : List (HeapNodeAux α (Heap α))
heq₃ : Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd) = Heap.heap ts₂
heq₄ : (findMin le ts (1 + 1) (bt, 1)).fst.children = Heap.heap ts₃
heq : Heap.heap (mergeNodes le ts₂ ts₃) = ys
heqh : h = t₁ ∧ hs = bt :: ts
⊢ IsMinHeap le (Heap.heap (t₁ :: bt :: ts))
Tactic:
rw[← heqh.left, ← heqh.right]
Proof state after:
case a
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
h₂ : IsMinHeap le (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
x✝⁴ : List (BinTree α)
x✝³ : ℕ
x✝² : BinTree α × ℕ
bt : BinTree α
ts : List (BinTree α)
h'✝ : BinTree α
idx'✝ : ℕ
heq✝ : (t₁, 0) = (h'✝, idx'✝)
hne₂ : bt :: ts = [] → False
h✝ : ¬le h'✝.val bt.val = true
left✝ : (findMin le ts (1 + 1) (bt, 1)).fst.val = y
x✝¹ x✝ : Heap α
ts₂ ts₃ : List (HeapNodeAux α (Heap α))
heq₃ : Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd) = Heap.heap ts₂
heq₄ : (findMin le ts (1 + 1) (bt, 1)).fst.children = Heap.heap ts₃
heq : Heap.heap (mergeNodes le ts₂ ts₃) = ys
heqh : h = t₁ ∧ hs = bt :: ts
⊢ IsMinHeap le (Heap.heap (h :: hs))
Theorem: project.deleteMin_non_empty
Proof state before:
case a
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
h₂ : IsMinHeap le (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
x✝⁴ : List (BinTree α)
x✝³ : ℕ
x✝² : BinTree α × ℕ
bt : BinTree α
ts : List (BinTree α)
h'✝ : BinTree α
idx'✝ : ℕ
heq✝ : (t₁, 0) = (h'✝, idx'✝)
hne₂ : bt :: ts = [] → False
h✝ : ¬le h'✝.val bt.val = true
left✝ : (findMin le ts (1 + 1) (bt, 1)).fst.val = y
x✝¹ x✝ : Heap α
ts₂ ts₃ : List (HeapNodeAux α (Heap α))
heq₃ : Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd) = Heap.heap ts₂
heq₄ : (findMin le ts (1 + 1) (bt, 1)).fst.children = Heap.heap ts₃
heq : Heap.heap (mergeNodes le ts₂ ts₃) = ys
heqh : h = t₁ ∧ hs = bt :: ts
⊢ IsMinHeap le (Heap.heap (h :: hs))
Tactic:
assumption
Proof state after:
no goals
Theorem: project.deleteMin_non_empty
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
h₂ : IsMinHeap le (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
x✝⁴ : List (BinTree α)
x✝³ : ℕ
x✝² : BinTree α × ℕ
bt : BinTree α
ts : List (BinTree α)
h'✝ : BinTree α
idx'✝ : ℕ
heq✝ : (t₁, 0) = (h'✝, idx'✝)
hne₂ : bt :: ts = [] → False
h✝ : ¬le h'✝.val bt.val = true
left✝ : (findMin le ts (1 + 1) (bt, 1)).fst.val = y
x✝¹ x✝ : Heap α
ts₂ ts₃ : List (HeapNodeAux α (Heap α))
heq₃ : Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd) = Heap.heap ts₂
heq₄ : (findMin le ts (1 + 1) (bt, 1)).fst.children = Heap.heap ts₃
heq : Heap.heap (mergeNodes le ts₂ ts₃) = ys
heqh : h = t₁ ∧ hs = bt :: ts
imhts₂ : IsMinHeap le (Heap.heap ts₂)
⊢ IsMinHeap le (Heap.heap ts₃)
Tactic:
rw[← heq₄]
Proof state after:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
h₂ : IsMinHeap le (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
x✝⁴ : List (BinTree α)
x✝³ : ℕ
x✝² : BinTree α × ℕ
bt : BinTree α
ts : List (BinTree α)
h'✝ : BinTree α
idx'✝ : ℕ
heq✝ : (t₁, 0) = (h'✝, idx'✝)
hne₂ : bt :: ts = [] → False
h✝ : ¬le h'✝.val bt.val = true
left✝ : (findMin le ts (1 + 1) (bt, 1)).fst.val = y
x✝¹ x✝ : Heap α
ts₂ ts₃ : List (HeapNodeAux α (Heap α))
heq₃ : Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd) = Heap.heap ts₂
heq₄ : (findMin le ts (1 + 1) (bt, 1)).fst.children = Heap.heap ts₃
heq : Heap.heap (mergeNodes le ts₂ ts₃) = ys
heqh : h = t₁ ∧ hs = bt :: ts
imhts₂ : IsMinHeap le (Heap.heap ts₂)
⊢ IsMinHeap le (findMin le ts (1 + 1) (bt, 1)).fst.children
Theorem: project.deleteMin_non_empty
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
h₂ : IsMinHeap le (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
x✝⁴ : List (BinTree α)
x✝³ : ℕ
x✝² : BinTree α × ℕ
bt : BinTree α
ts : List (BinTree α)
h'✝ : BinTree α
idx'✝ : ℕ
heq✝ : (t₁, 0) = (h'✝, idx'✝)
hne₂ : bt :: ts = [] → False
h✝ : ¬le h'✝.val bt.val = true
left✝ : (findMin le ts (1 + 1) (bt, 1)).fst.val = y
x✝¹ x✝ : Heap α
ts₂ ts₃ : List (HeapNodeAux α (Heap α))
heq₃ : Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd) = Heap.heap ts₂
heq₄ : (findMin le ts (1 + 1) (bt, 1)).fst.children = Heap.heap ts₃
heq : Heap.heap (mergeNodes le ts₂ ts₃) = ys
heqh : h = t₁ ∧ hs = bt :: ts
imhts₂ : IsMinHeap le (Heap.heap ts₂)
⊢ IsMinHeap le (findMin le ts (1 + 1) (bt, 1)).fst.children
Tactic:
apply children_IsMinHeap
Proof state after:
case a
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
h₂ : IsMinHeap le (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
x✝⁴ : List (BinTree α)
x✝³ : ℕ
x✝² : BinTree α × ℕ
bt : BinTree α
ts : List (BinTree α)
h'✝ : BinTree α
idx'✝ : ℕ
heq✝ : (t₁, 0) = (h'✝, idx'✝)
hne₂ : bt :: ts = [] → False
h✝ : ¬le h'✝.val bt.val = true
left✝ : (findMin le ts (1 + 1) (bt, 1)).fst.val = y
x✝¹ x✝ : Heap α
ts₂ ts₃ : List (HeapNodeAux α (Heap α))
heq₃ : Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd) = Heap.heap ts₂
heq₄ : (findMin le ts (1 + 1) (bt, 1)).fst.children = Heap.heap ts₃
heq : Heap.heap (mergeNodes le ts₂ ts₃) = ys
heqh : h = t₁ ∧ hs = bt :: ts
imhts₂ : IsMinHeap le (Heap.heap ts₂)
⊢ IsMinHeap le (Heap.heap [(findMin le ts (1 + 1) (bt, 1)).fst])
Theorem: project.deleteMin_non_empty
Proof state before:
case a.a
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
h₂ : IsMinHeap le (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
x✝⁴ : List (BinTree α)
x✝³ : ℕ
x✝² : BinTree α × ℕ
bt : BinTree α
ts : List (BinTree α)
h'✝ : BinTree α
idx'✝ : ℕ
heq✝ : (t₁, 0) = (h'✝, idx'✝)
hne₂ : bt :: ts = [] → False
h✝ : ¬le h'✝.val bt.val = true
left✝ : (findMin le ts (1 + 1) (bt, 1)).fst.val = y
x✝¹ x✝ : Heap α
ts₂ ts₃ : List (HeapNodeAux α (Heap α))
heq₃ : Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd) = Heap.heap ts₂
heq₄ : (findMin le ts (1 + 1) (bt, 1)).fst.children = Heap.heap ts₃
heq : Heap.heap (mergeNodes le ts₂ ts₃) = ys
heqh : h = t₁ ∧ hs = bt :: ts
imhts₂ : IsMinHeap le (Heap.heap ts₂)
⊢ IsMinHeap le (Heap.heap [])
Tactic:
. constructor
Proof state after:
no goals
Theorem: project.deleteMin_non_empty
Proof state before:
case a.a.a.cons
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
x✝⁴ : List (BinTree α)
x✝³ : ℕ
x✝² : BinTree α × ℕ
bt : BinTree α
ts : List (BinTree α)
h'✝ : BinTree α
idx'✝ : ℕ
heq✝ : (t₁, 0) = (h'✝, idx'✝)
hne₂ : bt :: ts = [] → False
h✝ : ¬le h'✝.val bt.val = true
left✝ : (findMin le ts (1 + 1) (bt, 1)).fst.val = y
x✝¹ x✝ : Heap α
ts₂ ts₃ : List (HeapNodeAux α (Heap α))
heq₃ : Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd) = Heap.heap ts₂
heq₄ : (findMin le ts (1 + 1) (bt, 1)).fst.children = Heap.heap ts₃
heq : Heap.heap (mergeNodes le ts₂ ts₃) = ys
heqh : h = t₁ ∧ hs = bt :: ts
imhts₂ : IsMinHeap le (Heap.heap ts₂)
a✝ : IsSearchTree le h
mh : IsMinHeap le (Heap.heap (bt :: ts))
⊢ IsSearchTree le bt
Tactic:
cases mh
Proof state after:
case a.a.a.cons.cons
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
x✝⁴ : List (BinTree α)
x✝³ : ℕ
x✝² : BinTree α × ℕ
bt : BinTree α
ts : List (BinTree α)
h'✝ : BinTree α
idx'✝ : ℕ
heq✝ : (t₁, 0) = (h'✝, idx'✝)
hne₂ : bt :: ts = [] → False
h✝ : ¬le h'✝.val bt.val = true
left✝ : (findMin le ts (1 + 1) (bt, 1)).fst.val = y
x✝¹ x✝ : Heap α
ts₂ ts₃ : List (HeapNodeAux α (Heap α))
heq₃ : Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd) = Heap.heap ts₂
heq₄ : (findMin le ts (1 + 1) (bt, 1)).fst.children = Heap.heap ts₃
heq : Heap.heap (mergeNodes le ts₂ ts₃) = ys
heqh : h = t₁ ∧ hs = bt :: ts
imhts₂ : IsMinHeap le (Heap.heap ts₂)
a✝² : IsSearchTree le h
a✝¹ : IsSearchTree le bt
a✝ : IsMinHeap le (Heap.heap ts)
⊢ IsSearchTree le bt
Theorem: project.deleteMin_non_empty
Proof state before:
case a.a.a.cons.cons
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
le_trans : ∀ (x y z : α), le x y = true → le y z = true → le x z = true
le_rfl : ∀ (z : α), le z z = true
xs : Heap α
y : α
ys : Heap α
h : HeapNodeAux α (Heap α)
hs : List (HeapNodeAux α (Heap α))
h₁ : IsHeap (Heap.heap (h :: hs))
xs₂ : Heap α
t₁ : HeapNodeAux α (Heap α)
x✝⁴ : List (BinTree α)
x✝³ : ℕ
x✝² : BinTree α × ℕ
bt : BinTree α
ts : List (BinTree α)
h'✝ : BinTree α
idx'✝ : ℕ
heq✝ : (t₁, 0) = (h'✝, idx'✝)
hne₂ : bt :: ts = [] → False
h✝ : ¬le h'✝.val bt.val = true
left✝ : (findMin le ts (1 + 1) (bt, 1)).fst.val = y
x✝¹ x✝ : Heap α
ts₂ ts₃ : List (HeapNodeAux α (Heap α))
heq₃ : Heap.heap (List.eraseIdx (t₁ :: bt :: ts) (findMin le ts (1 + 1) (bt, 1)).snd) = Heap.heap ts₂
heq₄ : (findMin le ts (1 + 1) (bt, 1)).fst.children = Heap.heap ts₃
heq : Heap.heap (mergeNodes le ts₂ ts₃) = ys
heqh : h = t₁ ∧ hs = bt :: ts
imhts₂ : IsMinHeap le (Heap.heap ts₂)
a✝² : IsSearchTree le h
a✝¹ : IsSearchTree le bt
a✝ : IsMinHeap le (Heap.heap ts)
⊢ IsSearchTree le bt
Tactic:
assumption
Proof state after:
no goals
Theorem: project.empty_heap_merge_left
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
h : List (BinTree α)
⊢ mergeNodes le [] h = h
Tactic:
unfold mergeNodes
Proof state after:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
h : List (BinTree α)
⊢ (match [], h with
    | [], h => h
    | h, [] => h
    | f@h:(h₁ :: t₁), s@h_1:(h₂ :: t₂) =>
      if h₁.rank < h₂.rank then h₁ :: mergeNodes le t₁ s
      else
        if h₂.rank < h₁.rank then h₂ :: mergeNodes le t₂ f
        else
          let merged := combine le h₁ h₂;
          let r := merged.rank;
          if (r != hRank t₁) = true then
            if (r != hRank t₂) = true then merged :: mergeNodes le t₁ t₂ else mergeNodes le (merged :: t₁) t₂
          else if (r != hRank t₂) = true then mergeNodes le t₁ (merged :: t₂) else merged :: mergeNodes le t₁ t₂) =
    h
Theorem: project.empty_heap_merge_left
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
h : List (BinTree α)
⊢ (match [], h with
    | [], h => h
    | h, [] => h
    | f@h:(h₁ :: t₁), s@h_1:(h₂ :: t₂) =>
      if h₁.rank < h₂.rank then h₁ :: mergeNodes le t₁ s
      else
        if h₂.rank < h₁.rank then h₂ :: mergeNodes le t₂ f
        else
          let merged := combine le h₁ h₂;
          let r := merged.rank;
          if (r != hRank t₁) = true then
            if (r != hRank t₂) = true then merged :: mergeNodes le t₁ t₂ else mergeNodes le (merged :: t₁) t₂
          else if (r != hRank t₂) = true then mergeNodes le t₁ (merged :: t₂) else merged :: mergeNodes le t₁ t₂) =
    h
Tactic:
split
Proof state after:
case h_1
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
x✝² x✝¹ x✝ : List (BinTree α)
heq✝ : [] = []
⊢ x✝² = x✝²

case h_2
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
x✝² x✝¹ : List (BinTree α)
x✝ : [] = [] → False
⊢ [] = []

case h_3
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
x✝¹ x✝ : List (BinTree α)
h₁✝ : BinTree α
t₁✝ : List (BinTree α)
h₂✝ : BinTree α
t₂✝ : List (BinTree α)
heq✝ : [] = h₁✝ :: t₁✝
⊢ (if h₁✝.rank < h₂✝.rank then h₁✝ :: mergeNodes le t₁✝ (h₂✝ :: t₂✝)
    else
      if h₂✝.rank < h₁✝.rank then h₂✝ :: mergeNodes le t₂✝ (h₁✝ :: t₁✝)
      else
        let merged := combine le h₁✝ h₂✝;
        let r := merged.rank;
        if (r != hRank t₁✝) = true then
          if (r != hRank t₂✝) = true then merged :: mergeNodes le t₁✝ t₂✝ else mergeNodes le (merged :: t₁✝) t₂✝
        else if (r != hRank t₂✝) = true then mergeNodes le t₁✝ (merged :: t₂✝) else merged :: mergeNodes le t₁✝ t₂✝) =
    h₂✝ :: t₂✝
Theorem: project.empty_heap_merge_left
Proof state before:
case h_1
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
x✝² x✝¹ x✝ : List (BinTree α)
heq✝ : [] = []
⊢ x✝² = x✝²

case h_2
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
x✝² x✝¹ : List (BinTree α)
x✝ : [] = [] → False
⊢ [] = []

case h_3
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
x✝¹ x✝ : List (BinTree α)
h₁✝ : BinTree α
t₁✝ : List (BinTree α)
h₂✝ : BinTree α
t₂✝ : List (BinTree α)
heq✝ : [] = h₁✝ :: t₁✝
⊢ (if h₁✝.rank < h₂✝.rank then h₁✝ :: mergeNodes le t₁✝ (h₂✝ :: t₂✝)
    else
      if h₂✝.rank < h₁✝.rank then h₂✝ :: mergeNodes le t₂✝ (h₁✝ :: t₁✝)
      else
        let merged := combine le h₁✝ h₂✝;
        let r := merged.rank;
        if (r != hRank t₁✝) = true then
          if (r != hRank t₂✝) = true then merged :: mergeNodes le t₁✝ t₂✝ else mergeNodes le (merged :: t₁✝) t₂✝
        else if (r != hRank t₂✝) = true then mergeNodes le t₁✝ (merged :: t₂✝) else merged :: mergeNodes le t₁✝ t₂✝) =
    h₂✝ :: t₂✝
Tactic:
. rfl
Proof state after:
case h_2
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
x✝² x✝¹ : List (BinTree α)
x✝ : [] = [] → False
⊢ [] = []

case h_3
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
x✝¹ x✝ : List (BinTree α)
h₁✝ : BinTree α
t₁✝ : List (BinTree α)
h₂✝ : BinTree α
t₂✝ : List (BinTree α)
heq✝ : [] = h₁✝ :: t₁✝
⊢ (if h₁✝.rank < h₂✝.rank then h₁✝ :: mergeNodes le t₁✝ (h₂✝ :: t₂✝)
    else
      if h₂✝.rank < h₁✝.rank then h₂✝ :: mergeNodes le t₂✝ (h₁✝ :: t₁✝)
      else
        let merged := combine le h₁✝ h₂✝;
        let r := merged.rank;
        if (r != hRank t₁✝) = true then
          if (r != hRank t₂✝) = true then merged :: mergeNodes le t₁✝ t₂✝ else mergeNodes le (merged :: t₁✝) t₂✝
        else if (r != hRank t₂✝) = true then mergeNodes le t₁✝ (merged :: t₂✝) else merged :: mergeNodes le t₁✝ t₂✝) =
    h₂✝ :: t₂✝
Theorem: project.empty_heap_merge_left
Proof state before:
case h_2
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
x✝² x✝¹ : List (BinTree α)
x✝ : [] = [] → False
⊢ [] = []

case h_3
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
x✝¹ x✝ : List (BinTree α)
h₁✝ : BinTree α
t₁✝ : List (BinTree α)
h₂✝ : BinTree α
t₂✝ : List (BinTree α)
heq✝ : [] = h₁✝ :: t₁✝
⊢ (if h₁✝.rank < h₂✝.rank then h₁✝ :: mergeNodes le t₁✝ (h₂✝ :: t₂✝)
    else
      if h₂✝.rank < h₁✝.rank then h₂✝ :: mergeNodes le t₂✝ (h₁✝ :: t₁✝)
      else
        let merged := combine le h₁✝ h₂✝;
        let r := merged.rank;
        if (r != hRank t₁✝) = true then
          if (r != hRank t₂✝) = true then merged :: mergeNodes le t₁✝ t₂✝ else mergeNodes le (merged :: t₁✝) t₂✝
        else if (r != hRank t₂✝) = true then mergeNodes le t₁✝ (merged :: t₂✝) else merged :: mergeNodes le t₁✝ t₂✝) =
    h₂✝ :: t₂✝
Tactic:
. rfl
Proof state after:
case h_3
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
x✝¹ x✝ : List (BinTree α)
h₁✝ : BinTree α
t₁✝ : List (BinTree α)
h₂✝ : BinTree α
t₂✝ : List (BinTree α)
heq✝ : [] = h₁✝ :: t₁✝
⊢ (if h₁✝.rank < h₂✝.rank then h₁✝ :: mergeNodes le t₁✝ (h₂✝ :: t₂✝)
    else
      if h₂✝.rank < h₁✝.rank then h₂✝ :: mergeNodes le t₂✝ (h₁✝ :: t₁✝)
      else
        let merged := combine le h₁✝ h₂✝;
        let r := merged.rank;
        if (r != hRank t₁✝) = true then
          if (r != hRank t₂✝) = true then merged :: mergeNodes le t₁✝ t₂✝ else mergeNodes le (merged :: t₁✝) t₂✝
        else if (r != hRank t₂✝) = true then mergeNodes le t₁✝ (merged :: t₂✝) else merged :: mergeNodes le t₁✝ t₂✝) =
    h₂✝ :: t₂✝
Theorem: project.empty_heap_merge_left
Proof state before:
case h_3
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
x✝¹ x✝ : List (BinTree α)
h₁✝ : BinTree α
t₁✝ : List (BinTree α)
h₂✝ : BinTree α
t₂✝ : List (BinTree α)
heq✝ : [] = h₁✝ :: t₁✝
⊢ (if h₁✝.rank < h₂✝.rank then h₁✝ :: mergeNodes le t₁✝ (h₂✝ :: t₂✝)
    else
      if h₂✝.rank < h₁✝.rank then h₂✝ :: mergeNodes le t₂✝ (h₁✝ :: t₁✝)
      else
        let merged := combine le h₁✝ h₂✝;
        let r := merged.rank;
        if (r != hRank t₁✝) = true then
          if (r != hRank t₂✝) = true then merged :: mergeNodes le t₁✝ t₂✝ else mergeNodes le (merged :: t₁✝) t₂✝
        else if (r != hRank t₂✝) = true then mergeNodes le t₁✝ (merged :: t₂✝) else merged :: mergeNodes le t₁✝ t₂✝) =
    h₂✝ :: t₂✝
Tactic:
. rename_i heq
  cases heq
Proof state after:
no goals
Theorem: project.empty_heap_merge_right
Proof state before:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
h : List (BinTree α)
⊢ mergeNodes le h [] = h
Tactic:
unfold mergeNodes
Proof state after:
α : Type u_1
le : α → α → Bool
not_le_le : ∀ (x y : α), ¬le x y = true → le y x = true
h : List (BinTree α)
⊢ (match h, [] with
    | [], h => h
    | h, [] => h
    | f@h:(h₁ :: t₁), s@h_1:(h₂ :: t₂) =>
      if h₁.rank < h₂.rank then h₁ :: mergeNodes le t₁ s
      else
        if h₂.rank < h₁.rank then h₂ :: mergeNodes le t₂ f
        else
          let merged := combine le h₁ h₂;
          let r := merged.rank;
          if (r != hRank t₁) = true then
            if (r != hRank t₂) = true then merged :: mergeNodes le t₁ t₂ else mergeNodes le (merged :: t₁) t₂
          else if (r != hRank t₂) = true then mergeNodes le t₁ (merged :: t₂) else merged :: mergeNodes le t₁ t₂) =
    h