internlm/Lean-Github huggingface dataset:
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.get_as_eq_of_ge_stop
Proof state before:
case hjk
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ : Subarray α
k : Nat
x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
hr : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = false
hx : lt x[i] x[2 * i + 2] = true
a✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }) (2 * i + 2) y
IH :
  ∀ {hk : k < Array.size y.as},
    k ≥ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }).stop →
      y.as[k] = (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }).as[k]
hk : k < Array.size y.as
hge : k ≥ x.stop
h : ↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr }) = k
⊢ False
Tactic:
cases h
Proof state after:
case hjk.refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
hr : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = false
hx : lt x[i] x[2 * i + 2] = true
a✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }) (2 * i + 2) y
IH :
  ∀ {hk : ↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr }) < Array.size y.as},
    ↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr }) ≥
        (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }).stop →
      y.as[↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr })] =
        (Subarray.swap x { val := i, isLt := hi }
              { val := 2 * i + 2, isLt := hr }).as[↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr })]
hk : ↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr }) < Array.size y.as
hge : ↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr }) ≥ x.stop
⊢ False
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.get_as_eq_of_ge_stop
Proof state before:
case hjk.refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y✝ x : Subarray α
i : Nat
y : Subarray α
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
hr : 2 * i + 2 < Subarray.size x
hx' : lt x[2 * i + 2] x[2 * i + 1] = false
hx : lt x[i] x[2 * i + 2] = true
a✝ : heapifyDown.OpSpec lt (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }) (2 * i + 2) y
IH :
  ∀ {hk : ↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr }) < Array.size y.as},
    ↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr }) ≥
        (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 2, isLt := hr }).stop →
      y.as[↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr })] =
        (Subarray.swap x { val := i, isLt := hi }
              { val := 2 * i + 2, isLt := hr }).as[↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr })]
hk : ↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr }) < Array.size y.as
hge : ↑(Subarray.castIndex x { val := 2 * i + 2, isLt := hr }) ≥ x.stop
⊢ False
Tactic:
exact Nat.not_lt_of_le hge <| x.castIndex_lt_stop _
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.get_as_eq_of_ge_stop
Proof state before:
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y : Subarray α
k : Nat
x : Subarray α
i : Nat
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
a✝¹ : 2 * i + 2 ≥ Subarray.size x
a✝ : lt x[i] x[2 * i + 1] = true
hk : k < Array.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as
hge : k ≥ x.stop
⊢ (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as[k] = x.as[k]
Tactic:
apply Array.getElem_swap_ne <;> (dsimp; intro h; cases h)
Proof state after:
case hik.refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y x : Subarray α
i : Nat
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
a✝¹ : 2 * i + 2 ≥ Subarray.size x
a✝ : lt x[i] x[2 * i + 1] = true
hk :
  ↑(Subarray.castIndex x { val := i, isLt := hi }) <
    Array.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as
hge : ↑(Subarray.castIndex x { val := i, isLt := hi }) ≥ x.stop
⊢ False

case hjk.refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y x : Subarray α
i : Nat
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
a✝¹ : 2 * i + 2 ≥ Subarray.size x
a✝ : lt x[i] x[2 * i + 1] = true
hk :
  ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) <
    Array.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as
hge : ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) ≥ x.stop
⊢ False
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.get_as_eq_of_ge_stop
Proof state before:
case hik.refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y x : Subarray α
i : Nat
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
a✝¹ : 2 * i + 2 ≥ Subarray.size x
a✝ : lt x[i] x[2 * i + 1] = true
hk :
  ↑(Subarray.castIndex x { val := i, isLt := hi }) <
    Array.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as
hge : ↑(Subarray.castIndex x { val := i, isLt := hi }) ≥ x.stop
⊢ False

case hjk.refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y x : Subarray α
i : Nat
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
a✝¹ : 2 * i + 2 ≥ Subarray.size x
a✝ : lt x[i] x[2 * i + 1] = true
hk :
  ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) <
    Array.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as
hge : ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) ≥ x.stop
⊢ False
Tactic:
all_goals exact Nat.not_lt_of_le hge <| x.castIndex_lt_stop _
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.get_as_eq_of_ge_stop
Proof state before:
case hjk
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y : Subarray α
k : Nat
x : Subarray α
i : Nat
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
a✝¹ : 2 * i + 2 ≥ Subarray.size x
a✝ : lt x[i] x[2 * i + 1] = true
hk : k < Array.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as
hge : k ≥ x.stop
⊢ ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) ≠ k
Tactic:
dsimp
Proof state after:
case hjk
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y : Subarray α
k : Nat
x : Subarray α
i : Nat
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
a✝¹ : 2 * i + 2 ≥ Subarray.size x
a✝ : lt x[i] x[2 * i + 1] = true
hk : k < Array.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as
hge : k ≥ x.stop
⊢ ¬↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) = k
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.get_as_eq_of_ge_stop
Proof state before:
case hjk
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y : Subarray α
k : Nat
x : Subarray α
i : Nat
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
a✝¹ : 2 * i + 2 ≥ Subarray.size x
a✝ : lt x[i] x[2 * i + 1] = true
hk : k < Array.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as
hge : k ≥ x.stop
⊢ ¬↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) = k
Tactic:
intro h
Proof state after:
case hjk
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y : Subarray α
k : Nat
x : Subarray α
i : Nat
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
a✝¹ : 2 * i + 2 ≥ Subarray.size x
a✝ : lt x[i] x[2 * i + 1] = true
hk : k < Array.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as
hge : k ≥ x.stop
h : ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) = k
⊢ False
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.get_as_eq_of_ge_stop
Proof state before:
case hjk
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y : Subarray α
k : Nat
x : Subarray α
i : Nat
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
a✝¹ : 2 * i + 2 ≥ Subarray.size x
a✝ : lt x[i] x[2 * i + 1] = true
hk : k < Array.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as
hge : k ≥ x.stop
h : ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) = k
⊢ False
Tactic:
cases h
Proof state after:
case hjk.refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y x : Subarray α
i : Nat
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
a✝¹ : 2 * i + 2 ≥ Subarray.size x
a✝ : lt x[i] x[2 * i + 1] = true
hk :
  ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) <
    Array.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as
hge : ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) ≥ x.stop
⊢ False
Theorem: Algdata.BinaryHeap.heapifyDown.OpSpec.get_as_eq_of_ge_stop
Proof state before:
case hjk.refl
α : Type u
lt : α → α → Bool
x✝ : Subarray α
i✝ : Nat
y x : Subarray α
i : Nat
hi : i < Subarray.size x
hl : 2 * i + 1 < Subarray.size x
a✝¹ : 2 * i + 2 ≥ Subarray.size x
a✝ : lt x[i] x[2 * i + 1] = true
hk :
  ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) <
    Array.size (Subarray.swap x { val := i, isLt := hi } { val := 2 * i + 1, isLt := hl }).as
hge : ↑(Subarray.castIndex x { val := 2 * i + 1, isLt := hl }) ≥ x.stop
⊢ False
Tactic:
exact Nat.not_lt_of_le hge <| x.castIndex_lt_stop _
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.get_heapifyDown_lt
Proof state before:
α : Type u
lt : α → α → Bool
x : Subarray α
i k : Nat
hk : k < Subarray.size (heapifyDown lt x i)
hki : k < i
⊢ (heapifyDown lt x i)[k] = x[k]
Tactic:
refine get_heapifyDown_not_descendant lt x i k ?_
Proof state after:
α : Type u
lt : α → α → Bool
x : Subarray α
i k : Nat
hk : k < Subarray.size (heapifyDown lt x i)
hki : k < i
⊢ ¬Descendant i k
Theorem: Algdata.BinaryHeap.get_heapifyDown_lt
Proof state before:
α : Type u
lt : α → α → Bool
x : Subarray α
i k : Nat
hk : k < Subarray.size (heapifyDown lt x i)
hki : k < i
⊢ ¬Descendant i k
Tactic:
intro h
Proof state after:
α : Type u
lt : α → α → Bool
x : Subarray α
i k : Nat
hk : k < Subarray.size (heapifyDown lt x i)
hki : k < i
h : Descendant i k
⊢ False
Theorem: Algdata.BinaryHeap.get_heapifyDown_lt
Proof state before:
α : Type u
lt : α → α → Bool
x : Subarray α
i k : Nat
hk : k < Subarray.size (heapifyDown lt x i)
hki : k < i
h : Descendant i k
⊢ False
Tactic:
exact absurd h.le (Nat.not_le_of_gt hki)
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.mkHeap_eq_foldRev
Proof state before:
α : Type u
lt : α → α → Bool
x : Subarray α
⊢ mkHeap lt x = Nat.foldRev (fun n x => heapifyDown lt x n) (Subarray.size x / 2) x
Tactic:
unfold mkHeap
Proof state after:
α : Type u
lt : α → α → Bool
x : Subarray α
⊢ mkHeap.loop lt x (Subarray.size x / 2) = Nat.foldRev (fun n x => heapifyDown lt x n) (Subarray.size x / 2) x
Theorem: Algdata.BinaryHeap.mkHeap_eq_foldRev
Proof state before:
α : Type u
lt : α → α → Bool
x : Subarray α
⊢ mkHeap.loop lt x (Subarray.size x / 2) = Nat.foldRev (fun n x => heapifyDown lt x n) (Subarray.size x / 2) x
Tactic:
generalize x.size/2 = n
Proof state after:
α : Type u
lt : α → α → Bool
x : Subarray α
n : Nat
⊢ mkHeap.loop lt x n = Nat.foldRev (fun n x => heapifyDown lt x n) n x
Theorem: Algdata.BinaryHeap.mkHeap_eq_foldRev
Proof state before:
α : Type u
lt : α → α → Bool
x : Subarray α
n : Nat
⊢ mkHeap.loop lt x n = Nat.foldRev (fun n x => heapifyDown lt x n) n x
Tactic:
induction n generalizing x with
| zero => rfl
| succ n IH => exact IH (heapifyDown lt x n)
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.mkHeap_eq_foldRev
Proof state before:
case zero
α : Type u
lt : α → α → Bool
x : Subarray α
⊢ mkHeap.loop lt x Nat.zero = Nat.foldRev (fun n x => heapifyDown lt x n) Nat.zero x
Tactic:
rfl
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.mkHeap_eq_foldRev
Proof state before:
case succ
α : Type u
lt : α → α → Bool
n : Nat
IH : ∀ (x : Subarray α), mkHeap.loop lt x n = Nat.foldRev (fun n x => heapifyDown lt x n) n x
x : Subarray α
⊢ mkHeap.loop lt x (Nat.succ n) = Nat.foldRev (fun n x => heapifyDown lt x n) (Nat.succ n) x
Tactic:
exact IH (heapifyDown lt x n)
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.size_as_mkHeap_loop
Proof state before:
α : Type u
lt : α → α → Bool
x : Subarray α
n : Nat
⊢ Array.size (mkHeap.loop lt x n).as = Array.size x.as
Tactic:
induction n generalizing x with
| zero => rfl
| succ n IH => simp only [mkHeap.loop, IH, size_as_heapifyDown]
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.size_as_mkHeap_loop
Proof state before:
case zero
α : Type u
lt : α → α → Bool
x : Subarray α
⊢ Array.size (mkHeap.loop lt x Nat.zero).as = Array.size x.as
Tactic:
rfl
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.size_as_mkHeap_loop
Proof state before:
case succ
α : Type u
lt : α → α → Bool
n : Nat
IH : ∀ (x : Subarray α), Array.size (mkHeap.loop lt x n).as = Array.size x.as
x : Subarray α
⊢ Array.size (mkHeap.loop lt x (Nat.succ n)).as = Array.size x.as
Tactic:
simp only [mkHeap.loop, IH, size_as_heapifyDown]
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.start_mkHeap_loop
Proof state before:
α : Type u
lt : α → α → Bool
x : Subarray α
n : Nat
⊢ (mkHeap.loop lt x n).start = x.start
Tactic:
induction n generalizing x with
| zero => rfl
| succ n IH => dsimp [mkHeap.loop]; rw [IH, start_heapifyDown]
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.start_mkHeap_loop
Proof state before:
case zero
α : Type u
lt : α → α → Bool
x : Subarray α
⊢ (mkHeap.loop lt x Nat.zero).start = x.start
Tactic:
rfl
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.start_mkHeap_loop
Proof state before:
case succ
α : Type u
lt : α → α → Bool
n : Nat
IH : ∀ (x : Subarray α), (mkHeap.loop lt x n).start = x.start
x : Subarray α
⊢ (mkHeap.loop lt x (Nat.succ n)).start = x.start
Tactic:
dsimp [mkHeap.loop]
Proof state after:
case succ
α : Type u
lt : α → α → Bool
n : Nat
IH : ∀ (x : Subarray α), (mkHeap.loop lt x n).start = x.start
x : Subarray α
⊢ (mkHeap.loop lt (heapifyDown lt x n) n).start = x.start
Theorem: Algdata.BinaryHeap.start_mkHeap_loop
Proof state before:
case succ
α : Type u
lt : α → α → Bool
n : Nat
IH : ∀ (x : Subarray α), (mkHeap.loop lt x n).start = x.start
x : Subarray α
⊢ (mkHeap.loop lt (heapifyDown lt x n) n).start = x.start
Tactic:
rw [IH, start_heapifyDown]
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.stop_mkHeap_loop
Proof state before:
α : Type u
lt : α → α → Bool
x : Subarray α
n : Nat
⊢ (mkHeap.loop lt x n).stop = x.stop
Tactic:
induction n generalizing x with
| zero => rfl
| succ n IH => dsimp [mkHeap.loop]; rw [IH, stop_heapifyDown]
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.stop_mkHeap_loop
Proof state before:
case zero
α : Type u
lt : α → α → Bool
x : Subarray α
⊢ (mkHeap.loop lt x Nat.zero).stop = x.stop
Tactic:
rfl
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.stop_mkHeap_loop
Proof state before:
case succ
α : Type u
lt : α → α → Bool
n : Nat
IH : ∀ (x : Subarray α), (mkHeap.loop lt x n).stop = x.stop
x : Subarray α
⊢ (mkHeap.loop lt x (Nat.succ n)).stop = x.stop
Tactic:
dsimp [mkHeap.loop]
Proof state after:
case succ
α : Type u
lt : α → α → Bool
n : Nat
IH : ∀ (x : Subarray α), (mkHeap.loop lt x n).stop = x.stop
x : Subarray α
⊢ (mkHeap.loop lt (heapifyDown lt x n) n).stop = x.stop
Theorem: Algdata.BinaryHeap.stop_mkHeap_loop
Proof state before:
case succ
α : Type u
lt : α → α → Bool
n : Nat
IH : ∀ (x : Subarray α), (mkHeap.loop lt x n).stop = x.stop
x : Subarray α
⊢ (mkHeap.loop lt (heapifyDown lt x n) n).stop = x.stop
Tactic:
rw [IH, stop_heapifyDown]
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.size_mkHeap_loop
Proof state before:
α : Type u
lt : α → α → Bool
x : Subarray α
n : Nat
⊢ Subarray.size (mkHeap.loop lt x n) = Subarray.size x
Tactic:
dsimp [Subarray.size]
Proof state after:
α : Type u
lt : α → α → Bool
x : Subarray α
n : Nat
⊢ (mkHeap.loop lt x n).stop - (mkHeap.loop lt x n).start = x.stop - x.start
Theorem: Algdata.BinaryHeap.size_mkHeap_loop
Proof state before:
α : Type u
lt : α → α → Bool
x : Subarray α
n : Nat
⊢ (mkHeap.loop lt x n).stop - (mkHeap.loop lt x n).start = x.stop - x.start
Tactic:
rw [start_mkHeap_loop, stop_mkHeap_loop]
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.get_as_mkHeap_loop_of_lt_start
Proof state before:
α : Type u
lt : α → α → Bool
x : Subarray α
n k : Nat
hk : k < Array.size (mkHeap.loop lt x n).as
hlt : k < x.start
⊢ (mkHeap.loop lt x n).as[k] = x.as[k]
Tactic:
induction n generalizing x with
| zero => rfl
| succ n IH =>
  dsimp [mkHeap.loop] at hk ⊢
  conv at hk => rw [size_as_mkHeap_loop, size_as_heapifyDown]
  specialize @IH (heapifyDown lt x n)
    ((size_as_mkHeap_loop lt _ n).symm ▸ size_as_heapifyDown lt x n ▸ hk)
    (start_heapifyDown lt x n ▸ hlt)
  rw [IH, get_as_heapifyDown_of_lt_start lt x n k hlt]
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.get_as_mkHeap_loop_of_lt_start
Proof state before:
case zero
α : Type u
lt : α → α → Bool
k : Nat
x : Subarray α
hk : k < Array.size (mkHeap.loop lt x Nat.zero).as
hlt : k < x.start
⊢ (mkHeap.loop lt x Nat.zero).as[k] = x.as[k]
Tactic:
rfl
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.get_as_mkHeap_loop_of_lt_start
Proof state before:
case succ
α : Type u
lt : α → α → Bool
k n : Nat
IH :
  ∀ (x : Subarray α) {hk : k < Array.size (mkHeap.loop lt x n).as}, k < x.start → (mkHeap.loop lt x n).as[k] = x.as[k]
x : Subarray α
hk : k < Array.size (mkHeap.loop lt x (Nat.succ n)).as
hlt : k < x.start
⊢ (mkHeap.loop lt x (Nat.succ n)).as[k] = x.as[k]
Tactic:
dsimp [mkHeap.loop] at hk ⊢
Proof state after:
case succ
α : Type u
lt : α → α → Bool
k n : Nat
IH :
  ∀ (x : Subarray α) {hk : k < Array.size (mkHeap.loop lt x n).as}, k < x.start → (mkHeap.loop lt x n).as[k] = x.as[k]
x : Subarray α
hk : k < Array.size (mkHeap.loop lt (heapifyDown lt x n) n).as
hlt : k < x.start
⊢ (mkHeap.loop lt (heapifyDown lt x n) n).as[k] = x.as[k]
Theorem: Algdata.BinaryHeap.get_as_mkHeap_loop_of_lt_start
Proof state before:
case succ
α : Type u
lt : α → α → Bool
k n : Nat
IH :
  ∀ (x : Subarray α) {hk : k < Array.size (mkHeap.loop lt x n).as}, k < x.start → (mkHeap.loop lt x n).as[k] = x.as[k]
x : Subarray α
hk : k < Array.size (mkHeap.loop lt (heapifyDown lt x n) n).as
hlt : k < x.start
⊢ (mkHeap.loop lt (heapifyDown lt x n) n).as[k] = x.as[k]
Tactic:
conv at hk => rw [size_as_mkHeap_loop, size_as_heapifyDown]
Proof state after:
case succ
α : Type u
lt : α → α → Bool
k n : Nat
IH :
  ∀ (x : Subarray α) {hk : k < Array.size (mkHeap.loop lt x n).as}, k < x.start → (mkHeap.loop lt x n).as[k] = x.as[k]
x : Subarray α
hk✝ : k < Array.size (mkHeap.loop lt (heapifyDown lt x n) n).as
hk : k < Array.size x.as
hlt : k < x.start
⊢ (mkHeap.loop lt (heapifyDown lt x n) n).as[k] = x.as[k]
Theorem: Algdata.BinaryHeap.get_as_mkHeap_loop_of_lt_start
Proof state before:
case succ
α : Type u
lt : α → α → Bool
k n : Nat
IH :
  ∀ (x : Subarray α) {hk : k < Array.size (mkHeap.loop lt x n).as}, k < x.start → (mkHeap.loop lt x n).as[k] = x.as[k]
x : Subarray α
hk✝ : k < Array.size (mkHeap.loop lt (heapifyDown lt x n) n).as
hk : k < Array.size x.as
hlt : k < x.start
⊢ (mkHeap.loop lt (heapifyDown lt x n) n).as[k] = x.as[k]
Tactic:
specialize @IH (heapifyDown lt x n)
  ((size_as_mkHeap_loop lt _ n).symm ▸ size_as_heapifyDown lt x n ▸ hk)
  (start_heapifyDown lt x n ▸ hlt)
Proof state after:
case succ
α : Type u
lt : α → α → Bool
k n : Nat
x : Subarray α
hk✝ : k < Array.size (mkHeap.loop lt (heapifyDown lt x n) n).as
hk : k < Array.size x.as
hlt : k < x.start
IH : (mkHeap.loop lt (heapifyDown lt x n) n).as[k] = (heapifyDown lt x n).as[k]
⊢ (mkHeap.loop lt (heapifyDown lt x n) n).as[k] = x.as[k]
Theorem: Algdata.BinaryHeap.get_as_mkHeap_loop_of_lt_start
Proof state before:
case succ
α : Type u
lt : α → α → Bool
k n : Nat
x : Subarray α
hk✝ : k < Array.size (mkHeap.loop lt (heapifyDown lt x n) n).as
hk : k < Array.size x.as
hlt : k < x.start
IH : (mkHeap.loop lt (heapifyDown lt x n) n).as[k] = (heapifyDown lt x n).as[k]
⊢ (mkHeap.loop lt (heapifyDown lt x n) n).as[k] = x.as[k]
Tactic:
rw [IH, get_as_heapifyDown_of_lt_start lt x n k hlt]
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.get_as_mkHeap_loop_of_ge_stop
Proof state before:
α : Type u
lt : α → α → Bool
x : Subarray α
n k : Nat
hk : k < Array.size (mkHeap.loop lt x n).as
hge : k ≥ x.stop
⊢ (mkHeap.loop lt x n).as[k] = x.as[k]
Tactic:
induction n generalizing x with
| zero => rfl
| succ n IH =>
  dsimp [mkHeap.loop] at hk ⊢
  conv at hk => rw [size_as_mkHeap_loop, size_as_heapifyDown]
  specialize @IH (heapifyDown lt x n)
    ((size_as_mkHeap_loop lt _ n).symm ▸ size_as_heapifyDown lt x n ▸ hk)
    (stop_heapifyDown lt x n ▸ hge)
  rw [IH, get_as_heapifyDown_of_ge_stop lt x n k hge]
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.get_as_mkHeap_loop_of_ge_stop
Proof state before:
case zero
α : Type u
lt : α → α → Bool
k : Nat
x : Subarray α
hk : k < Array.size (mkHeap.loop lt x Nat.zero).as
hge : k ≥ x.stop
⊢ (mkHeap.loop lt x Nat.zero).as[k] = x.as[k]
Tactic:
rfl
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.get_as_mkHeap_loop_of_ge_stop
Proof state before:
case succ
α : Type u
lt : α → α → Bool
k n : Nat
IH : ∀ (x : Subarray α) {hk : k < Array.size (mkHeap.loop lt x n).as}, k ≥ x.stop → (mkHeap.loop lt x n).as[k] = x.as[k]
x : Subarray α
hk : k < Array.size (mkHeap.loop lt x (Nat.succ n)).as
hge : k ≥ x.stop
⊢ (mkHeap.loop lt x (Nat.succ n)).as[k] = x.as[k]
Tactic:
dsimp [mkHeap.loop] at hk ⊢
Proof state after:
case succ
α : Type u
lt : α → α → Bool
k n : Nat
IH : ∀ (x : Subarray α) {hk : k < Array.size (mkHeap.loop lt x n).as}, k ≥ x.stop → (mkHeap.loop lt x n).as[k] = x.as[k]
x : Subarray α
hk : k < Array.size (mkHeap.loop lt (heapifyDown lt x n) n).as
hge : k ≥ x.stop
⊢ (mkHeap.loop lt (heapifyDown lt x n) n).as[k] = x.as[k]
Theorem: Algdata.BinaryHeap.get_as_mkHeap_loop_of_ge_stop
Proof state before:
case succ
α : Type u
lt : α → α → Bool
k n : Nat
IH : ∀ (x : Subarray α) {hk : k < Array.size (mkHeap.loop lt x n).as}, k ≥ x.stop → (mkHeap.loop lt x n).as[k] = x.as[k]
x : Subarray α
hk : k < Array.size (mkHeap.loop lt (heapifyDown lt x n) n).as
hge : k ≥ x.stop
⊢ (mkHeap.loop lt (heapifyDown lt x n) n).as[k] = x.as[k]
Tactic:
conv at hk => rw [size_as_mkHeap_loop, size_as_heapifyDown]
Proof state after:
case succ
α : Type u
lt : α → α → Bool
k n : Nat
IH : ∀ (x : Subarray α) {hk : k < Array.size (mkHeap.loop lt x n).as}, k ≥ x.stop → (mkHeap.loop lt x n).as[k] = x.as[k]
x : Subarray α
hk✝ : k < Array.size (mkHeap.loop lt (heapifyDown lt x n) n).as
hk : k < Array.size x.as
hge : k ≥ x.stop
⊢ (mkHeap.loop lt (heapifyDown lt x n) n).as[k] = x.as[k]
Theorem: Algdata.BinaryHeap.get_as_mkHeap_loop_of_ge_stop
Proof state before:
case succ
α : Type u
lt : α → α → Bool
k n : Nat
IH : ∀ (x : Subarray α) {hk : k < Array.size (mkHeap.loop lt x n).as}, k ≥ x.stop → (mkHeap.loop lt x n).as[k] = x.as[k]
x : Subarray α
hk✝ : k < Array.size (mkHeap.loop lt (heapifyDown lt x n) n).as
hk : k < Array.size x.as
hge : k ≥ x.stop
⊢ (mkHeap.loop lt (heapifyDown lt x n) n).as[k] = x.as[k]
Tactic:
specialize @IH (heapifyDown lt x n)
  ((size_as_mkHeap_loop lt _ n).symm ▸ size_as_heapifyDown lt x n ▸ hk)
  (stop_heapifyDown lt x n ▸ hge)
Proof state after:
case succ
α : Type u
lt : α → α → Bool
k n : Nat
x : Subarray α
hk✝ : k < Array.size (mkHeap.loop lt (heapifyDown lt x n) n).as
hk : k < Array.size x.as
hge : k ≥ x.stop
IH : (mkHeap.loop lt (heapifyDown lt x n) n).as[k] = (heapifyDown lt x n).as[k]
⊢ (mkHeap.loop lt (heapifyDown lt x n) n).as[k] = x.as[k]
Theorem: Algdata.BinaryHeap.get_as_mkHeap_loop_of_ge_stop
Proof state before:
case succ
α : Type u
lt : α → α → Bool
k n : Nat
x : Subarray α
hk✝ : k < Array.size (mkHeap.loop lt (heapifyDown lt x n) n).as
hk : k < Array.size x.as
hge : k ≥ x.stop
IH : (mkHeap.loop lt (heapifyDown lt x n) n).as[k] = (heapifyDown lt x n).as[k]
⊢ (mkHeap.loop lt (heapifyDown lt x n) n).as[k] = x.as[k]
Tactic:
rw [IH, get_as_heapifyDown_of_ge_stop lt x n k hge]
Proof state after:
no goals
Theorem: Algdata.BinaryHeap.exists_get_mkHeap_loop
Proof state before:
α : Type u
lt : α → α → Bool
x : Subarray α
n k : Nat
hk : k < Subarray.size x
⊢ ∃ l hl, (mkHeap.loop lt x n)[k] = x[l]
Tactic:
induction n generalizing x with
| zero => exact ⟨k,hk,rfl⟩
| succ n IH =>
  dsimp [mkHeap.loop]
  have ⟨l',hl',IH⟩ := IH (heapifyDown lt x n) (size_heapifyDown lt x n ▸ hk)
  simp only [IH]
  exact exists_get_heapifyDown lt x n l' (size_heapifyDown lt x n ▸ hl')
Proof state after:
no goals