Theorem: KVChain.mergeWith_cons_flip (Algdata/Data/KVChain/MergeWith.lean)

State before:
α : Type u
r : α → α → Prop
inst✝¹ : StrictLinearOrder r
inst✝ : DecidableRel r
β : α → Type v
f : (a : α) → β a → β a → Option (β a)
⊢ ∀ {xs : KVChain r β} {a : α} {b : β a} {ys : KVChain r β} {hays : boundLeft a ys} (haxs : boundLeft a xs),
    mergeWith f xs (KVChain.cons a b ys hays) =
      KVChain.cons a b (mergeWith f xs ys) (_ : boundLeft a (mergeWith f xs ys))
Tactic:
intro xs a b ys hays haxs
State after:
α : Type u
r : α → α → Prop
inst✝¹ : StrictLinearOrder r
inst✝ : DecidableRel r
β : α → Type v
f : (a : α) → β a → β a → Option (β a)
xs : KVChain r β
a : α
b : β a
ys : KVChain r β
hays : boundLeft a ys
haxs : boundLeft a xs
⊢ mergeWith f xs (KVChain.cons a b ys hays) = KVChain.cons a b (mergeWith f xs ys) (_ : boundLeft a (mergeWith f xs ys))

State before:
α : Type u
r : α → α → Prop
inst✝¹ : StrictLinearOrder r
inst✝ : DecidableRel r
β : α → Type v
f : (a : α) → β a → β a → Option (β a)
xs : KVChain r β
a : α
b : β a
ys : KVChain r β
hays : boundLeft a ys
haxs : boundLeft a xs
⊢ mergeWith f xs (KVChain.cons a b ys hays) = KVChain.cons a b (mergeWith f xs ys) (_ : boundLeft a (mergeWith f xs ys))
Tactic:
apply KVChain.eq_of_toList_eq
State after:
case a
α : Type u
r : α → α → Prop
inst✝¹ : StrictLinearOrder r
inst✝ : DecidableRel r
β : α → Type v
f : (a : α) → β a → β a → Option (β a)
xs : KVChain r β
a : α
b : β a
ys : KVChain r β
hays : boundLeft a ys
haxs : boundLeft a xs
⊢ (mergeWith f xs (KVChain.cons a b ys hays)).toList =
    (KVChain.cons a b (mergeWith f xs ys) (_ : boundLeft a (mergeWith f xs ys))).toList

State before:
case a
α : Type u
r : α → α → Prop
inst✝¹ : StrictLinearOrder r
inst✝ : DecidableRel r
β : α → Type v
f : (a : α) → β a → β a → Option (β a)
xs : KVChain r β
a : α
b : β a
ys : KVChain r β
hays : boundLeft a ys
haxs : boundLeft a xs
⊢ (mergeWith f xs (KVChain.cons a b ys hays)).toList =
    (KVChain.cons a b (mergeWith f xs ys) (_ : boundLeft a (mergeWith f xs ys))).toList
Tactic:
rw [toList_mergeWith_cons_right]
State after:
case a
α : Type u
r : α → α → Prop
inst✝¹ : StrictLinearOrder r
inst✝ : DecidableRel r
β : α → Type v
f : (a : α) → β a → β a → Option (β a)
xs : KVChain r β
a : α
b : β a
ys : KVChain r β
hays : boundLeft a ys
haxs : boundLeft a xs
⊢ List.reverseAux (insertWithAux f KVChain.nil xs True.intro a b True.intro).val.fst.toList
      (mergeWith f (insertWithAux f KVChain.nil xs True.intro a b True.intro).val.snd ys).toList =
    (KVChain.cons a b (mergeWith f xs ys) (_ : boundLeft a (mergeWith f xs ys))).toList

State before:
case a
α : Type u
r : α → α → Prop
inst✝¹ : StrictLinearOrder r
inst✝ : DecidableRel r
β : α → Type v
f : (a : α) → β a → β a → Option (β a)
xs : KVChain r β
a : α
b : β a
ys : KVChain r β
hays : boundLeft a ys
haxs : boundLeft a xs
⊢ List.reverseAux (insertWithAux f KVChain.nil xs True.intro a b True.intro).val.fst.toList
      (mergeWith f (insertWithAux f KVChain.nil xs True.intro a b True.intro).val.snd ys).toList =
    (KVChain.cons a b (mergeWith f xs ys) (_ : boundLeft a (mergeWith f xs ys))).toList
Tactic:
suffices (insertWithAux f KVChain.nil xs True.intro a b True.intro).val = (⟨[⟨a,b⟩],List.Ascending.singleton _⟩,xs) by
  rw [this]; rfl
State after:
case a
α : Type u
r : α → α → Prop
inst✝¹ : StrictLinearOrder r
inst✝ : DecidableRel r
β : α → Type v
f : (a : α) → β a → β a → Option (β a)
xs : KVChain r β
a : α
b : β a
ys : KVChain r β
hays : boundLeft a ys
haxs : boundLeft a xs
⊢ (insertWithAux f KVChain.nil xs True.intro a b True.intro).val =
    ({ toList := [{ fst := a, snd := b }],
        ascend := (_ : List.Ascending (Sigma.relOnFst (flip r)) [{ fst := a, snd := b }]) },
      xs)

State before:
case a
α : Type u
r : α → α → Prop
inst✝¹ : StrictLinearOrder r
inst✝ : DecidableRel r
β : α → Type v
f : (a : α) → β a → β a → Option (β a)
xs : KVChain r β
a : α
b : β a
ys : KVChain r β
hays : boundLeft a ys
haxs : boundLeft a xs
⊢ (insertWithAux f KVChain.nil xs True.intro a b True.intro).val =
    ({ toList := [{ fst := a, snd := b }],
        ascend := (_ : List.Ascending (Sigma.relOnFst (flip r)) [{ fst := a, snd := b }]) },
      xs)
Tactic:
revert haxs
State after:
case a
α : Type u
r : α → α → Prop
inst✝¹ : StrictLinearOrder r
inst✝ : DecidableRel r
β : α → Type v
f : (a : α) → β a → β a → Option (β a)
xs : KVChain r β
a : α
b : β a
ys : KVChain r β
hays : boundLeft a ys
⊢ boundLeft a xs →
    (insertWithAux f KVChain.nil xs True.intro a b True.intro).val =
      ({ toList := [{ fst := a, snd := b }],
          ascend := (_ : List.Ascending (Sigma.relOnFst (flip r)) [{ fst := a, snd := b }]) },
        xs)

State before:
case a
α : Type u
r : α → α → Prop
inst✝¹ : StrictLinearOrder r
inst✝ : DecidableRel r
β : α → Type v
f : (a : α) → β a → β a → Option (β a)
xs : KVChain r β
a : α
b : β a
ys : KVChain r β
hays : boundLeft a ys
⊢ boundLeft a xs →
    (insertWithAux f KVChain.nil xs True.intro a b True.intro).val =
      ({ toList := [{ fst := a, snd := b }],
          ascend := (_ : List.Ascending (Sigma.relOnFst (flip r)) [{ fst := a, snd := b }]) },
        xs)
Tactic:
apply xs.recOnList (motive:=λ xs=> xs.boundLeft a → (insertWithAux f KVChain.nil xs _ _ _ _).val=_)
State after:
case a.nil
α : Type u
r : α → α → Prop
inst✝¹ : StrictLinearOrder r
inst✝ : DecidableRel r
β : α → Type v
f : (a : α) → β a → β a → Option (β a)
xs : KVChain r β
a : α
b : β a
ys : KVChain r β
hays : boundLeft a ys
⊢ boundLeft a KVChain.nil →
    (insertWithAux f KVChain.nil KVChain.nil True.intro a b True.intro).val =
      ({ toList := [{ fst := a, snd := b }],
          ascend := (_ : List.Ascending (Sigma.relOnFst (flip r)) [{ fst := a, snd := b }]) },
        KVChain.nil)

case a.cons
α : Type u
r : α → α → Prop
inst✝¹ : StrictLinearOrder r
inst✝ : DecidableRel r
β : α → Type v
f : (a : α) → β a → β a → Option (β a)
xs : KVChain r β
a : α
b : β a
ys : KVChain r β
hays : boundLeft a ys
⊢ ∀ (a_1 : α) (b_1 : β a_1) (xs : KVChain r fun a => β a) (haxs : boundLeft a_1 xs),
    (fun xs =>
          boundLeft a xs →
            (insertWithAux f KVChain.nil xs True.intro a b True.intro).val =
              ({ toList := [{ fst := a, snd := b }],
                  ascend := (_ : List.Ascending (Sigma.relOnFst (flip r)) [{ fst := a, snd := b }]) },
                xs))
        xs →
      (fun xs =>
          boundLeft a xs →
            (insertWithAux f KVChain.nil xs True.intro a b True.intro).val =
              ({ toList := [{ fst := a, snd := b }],
                  ascend := (_ : List.Ascending (Sigma.relOnFst (flip r)) [{ fst := a, snd := b }]) },
                xs))
        (KVChain.cons a_1 b_1 xs haxs)

State before:
α : Type u
r : α → α → Prop
inst✝¹ : StrictLinearOrder r
inst✝ : DecidableRel r
β : α → Type v
f : (a : α) → β a → β a → Option (β a)
xs : KVChain r β
a : α
b : β a
ys : KVChain r β
hays : boundLeft a ys
⊢ boundLeft a KVChain.nil →
    (insertWithAux f KVChain.nil KVChain.nil True.intro a b True.intro).val =
      ({ toList := [{ fst := a, snd := b }],
          ascend := (_ : List.Ascending (Sigma.relOnFst (flip r)) [{ fst := a, snd := b }]) },
        KVChain.nil)
Tactic:
case a.nil => intros; rfl
State after:
no goals

State before:
α : Type u
r : α → α → Prop
inst✝¹ : StrictLinearOrder r
inst✝ : DecidableRel r
β : α → Type v
f : (a : α) → β a → β a → Option (β a)
xs : KVChain r β
a : α
b : β a
ys : KVChain r β
hays : boundLeft a ys
⊢ ∀ (a_1 : α) (b_1 : β a_1) (xs : KVChain r fun a => β a) (haxs : boundLeft a_1 xs),
    (fun xs =>
          boundLeft a xs →
            (insertWithAux f KVChain.nil xs True.intro a b True.intro).val =
              ({ toList := [{ fst := a, snd := b }],
                  ascend := (_ : List.Ascending (Sigma.relOnFst (flip r)) [{ fst := a, snd := b }]) },
                xs))
        xs →
      (fun xs =>
          boundLeft a xs →
            (insertWithAux f KVChain.nil xs True.intro a b True.intro).val =
              ({ toList := [{ fst := a, snd := b }],
                  ascend := (_ : List.Ascending (Sigma.relOnFst (flip r)) [{ fst := a, snd := b }]) },
                xs))
        (KVChain.cons a_1 b_1 xs haxs)
Tactic:
case a.cons =>
  intro a₁ b₁ xs ha₁xs _ haa₁
  dsimp [boundLeft, List.predHead] at haa₁
  rw [insertWithAux_cons_flip haa₁]
State after:
no goals

State before:
α : Type u
r : α → α → Prop
inst✝¹ : StrictLinearOrder r
inst✝ : DecidableRel r
β : α → Type v
f : (a : α) → β a → β a → Option (β a)
xs : KVChain r β
a : α
b : β a
ys : KVChain r β
hays : boundLeft a ys
haxs : boundLeft a xs
this :
  (insertWithAux f KVChain.nil xs True.intro a b True.intro).val =
    ({ toList := [{ fst := a, snd := b }],
        ascend := (_ : List.Ascending (Sigma.relOnFst (flip r)) [{ fst := a, snd := b }]) },
      xs)
⊢ List.reverseAux (insertWithAux f KVChain.nil xs True.intro a b True.intro).val.fst.toList
      (mergeWith f (insertWithAux f KVChain.nil xs True.intro a b True.intro).val.snd ys).toList =
    (KVChain.cons a b (mergeWith f xs ys) (_ : boundLeft a (mergeWith f xs ys))).toList
Tactic:
rw [this]
State after:
α : Type u
r : α → α → Prop
inst✝¹ : StrictLinearOrder r
inst✝ : DecidableRel r
β : α → Type v
f : (a : α) → β a → β a → Option (β a)
xs : KVChain r β
a : α
b : β a
ys : KVChain r β
hays : boundLeft a ys
haxs : boundLeft a xs
this :
  (insertWithAux f KVChain.nil xs True.intro a b True.intro).val =
    ({ toList := [{ fst := a, snd := b }],
        ascend := (_ : List.Ascending (Sigma.relOnFst (flip r)) [{ fst := a, snd := b }]) },
      xs)
⊢ List.reverseAux
      ({ toList := [{ fst := a, snd := b }],
              ascend := (_ : List.Ascending (Sigma.relOnFst (flip r)) [{ fst := a, snd := b }]) },
            xs).fst.toList
      (mergeWith f
          ({ toList := [{ fst := a, snd := b }],
                ascend := (_ : List.Ascending (Sigma.relOnFst (flip r)) [{ fst := a, snd := b }]) },
              xs).snd
          ys).toList =
    (KVChain.cons a b (mergeWith f xs ys) (_ : boundLeft a (mergeWith f xs ys))).toList

State before:
α : Type u
r : α → α → Prop
inst✝¹ : StrictLinearOrder r
inst✝ : DecidableRel r
β : α → Type v
f : (a : α) → β a → β a → Option (β a)
xs : KVChain r β
a : α
b : β a
ys : KVChain r β
hays : boundLeft a ys
haxs : boundLeft a xs
this :
  (insertWithAux f KVChain.nil xs True.intro a b True.intro).val =
    ({ toList := [{ fst := a, snd := b }],
        ascend := (_ : List.Ascending (Sigma.relOnFst (flip r)) [{ fst := a, snd := b }]) },
      xs)
⊢ List.reverseAux
      ({ toList := [{ fst := a, snd := b }],
              ascend := (_ : List.Ascending (Sigma.relOnFst (flip r)) [{ fst := a, snd := b }]) },
            xs).fst.toList
      (mergeWith f
          ({ toList := [{ fst := a, snd := b }],
                ascend := (_ : List.Ascending (Sigma.relOnFst (flip r)) [{ fst := a, snd := b }]) },
              xs).snd
          ys).toList =
    (KVChain.cons a b (mergeWith f xs ys) (_ : boundLeft a (mergeWith f xs ys))).toList
Tactic:
rfl
State after:
no goals

State before:
α : Type u
r : α → α → Prop
inst✝¹ : StrictLinearOrder r
inst✝ : DecidableRel r
β : α → Type v
f : (a : α) → β a → β a → Option (β a)
xs : KVChain r β
a : α
b : β a
ys : KVChain r β
hays : boundLeft a ys
⊢ boundLeft a KVChain.nil →
    (insertWithAux f KVChain.nil KVChain.nil True.intro a b True.intro).val =
      ({ toList := [{ fst := a, snd := b }],
          ascend := (_ : List.Ascending (Sigma.relOnFst (flip r)) [{ fst := a, snd := b }]) },
        KVChain.nil)
Tactic:
intros
State after:
α : Type u
r : α → α → Prop
inst✝¹ : StrictLinearOrder r
inst✝ : DecidableRel r
β : α → Type v
f : (a : α) → β a → β a → Option (β a)
xs : KVChain r β
a : α
b : β a
ys : KVChain r β
hays : boundLeft a ys
a✝ : boundLeft a KVChain.nil
⊢ (insertWithAux f KVChain.nil KVChain.nil True.intro a b True.intro).val =
    ({ toList := [{ fst := a, snd := b }],
        ascend := (_ : List.Ascending (Sigma.relOnFst (flip r)) [{ fst := a, snd := b }]) },
      KVChain.nil)

State before:
α : Type u
r : α → α → Prop
inst✝¹ : StrictLinearOrder r
inst✝ : DecidableRel r
β : α → Type v
f : (a : α) → β a → β a → Option (β a)
xs : KVChain r β
a : α
b : β a
ys : KVChain r β
hays : boundLeft a ys
a✝ : boundLeft a KVChain.nil
⊢ (insertWithAux f KVChain.nil KVChain.nil True.intro a b True.intro).val =
    ({ toList := [{ fst := a, snd := b }],
        ascend := (_ : List.Ascending (Sigma.relOnFst (flip r)) [{ fst := a, snd := b }]) },
      KVChain.nil)
Tactic:
rfl
State after:
no goals

State before:
α : Type u
r : α → α → Prop
inst✝¹ : StrictLinearOrder r
inst✝ : DecidableRel r
β : α → Type v
f : (a : α) → β a → β a → Option (β a)
xs : KVChain r β
a : α
b : β a
ys : KVChain r β
hays : boundLeft a ys
⊢ ∀ (a_1 : α) (b_1 : β a_1) (xs : KVChain r fun a => β a) (haxs : boundLeft a_1 xs),
    (fun xs =>
          boundLeft a xs →
            (insertWithAux f KVChain.nil xs True.intro a b True.intro).val =
              ({ toList := [{ fst := a, snd := b }],
                  ascend := (_ : List.Ascending (Sigma.relOnFst (flip r)) [{ fst := a, snd := b }]) },
                xs))
        xs →
      (fun xs =>
          boundLeft a xs →
            (insertWithAux f KVChain.nil xs True.intro a b True.intro).val =
              ({ toList := [{ fst := a, snd := b }],
                  ascend := (_ : List.Ascending (Sigma.relOnFst (flip r)) [{ fst := a, snd := b }]) },
                xs))
        (KVChain.cons a_1 b_1 xs haxs)
Tactic:
intro a₁ b₁ xs ha₁xs _ haa₁
State after:
α : Type u
r : α → α → Prop
inst✝¹ : StrictLinearOrder r
inst✝ : DecidableRel r
β : α → Type v
f : (a : α) → β a → β a → Option (β a)
xs✝ : KVChain r β
a : α
b : β a
ys : KVChain r β
hays : boundLeft a ys
a₁ : α
b₁ : β a₁
xs : KVChain r fun a => β a
ha₁xs : boundLeft a₁ xs
a✝ :
  boundLeft a xs →
    (insertWithAux f KVChain.nil xs True.intro a b True.intro).val =
      ({ toList := [{ fst := a, snd := b }],
          ascend := (_ : List.Ascending (Sigma.relOnFst (flip r)) [{ fst := a, snd := b }]) },
        xs)
haa₁ : boundLeft a (KVChain.cons a₁ b₁ xs ha₁xs)
⊢ (insertWithAux f KVChain.nil (KVChain.cons a₁ b₁ xs ha₁xs) True.intro a b True.intro).val =
    ({ toList := [{ fst := a, snd := b }],
        ascend := (_ : List.Ascending (Sigma.relOnFst (flip r)) [{ fst := a, snd := b }]) },
      KVChain.cons a₁ b₁ xs ha₁xs)

State before:
α : Type u
r : α → α → Prop
inst✝¹ : StrictLinearOrder r
inst✝ : DecidableRel r
β : α → Type v
f : (a : α) → β a → β a → Option (β a)
xs✝ : KVChain r β
a : α
b : β a
ys : KVChain r β
hays : boundLeft a ys
a₁ : α
b₁ : β a₁
xs : KVChain r fun a => β a
ha₁xs : boundLeft a₁ xs
a✝ :
  boundLeft a xs →
    (insertWithAux f KVChain.nil xs True.intro a b True.intro).val =
      ({ toList := [{ fst := a, snd := b }],
          ascend := (_ : List.Ascending (Sigma.relOnFst (flip r)) [{ fst := a, snd := b }]) },
        xs)
haa₁ : boundLeft a (KVChain.cons a₁ b₁ xs ha₁xs)
⊢ (insertWithAux f KVChain.nil (KVChain.cons a₁ b₁ xs ha₁xs) True.intro a b True.intro).val =
    ({ toList := [{ fst := a, snd := b }],
        ascend := (_ : List.Ascending (Sigma.relOnFst (flip r)) [{ fst := a, snd := b }]) },
      KVChain.cons a₁ b₁ xs ha₁xs)
Tactic:
dsimp [boundLeft, List.predHead] at haa₁
State after:
α : Type u
r : α → α → Prop
inst✝¹ : StrictLinearOrder r
inst✝ : DecidableRel r
β : α → Type v
f : (a : α) → β a → β a → Option (β a)
xs✝ : KVChain r β
a : α
b : β a
ys : KVChain r β
hays : boundLeft a ys
a₁ : α
b₁ : β a₁
xs : KVChain r fun a => β a
ha₁xs : boundLeft a₁ xs
a✝ :
  boundLeft a xs →
    (insertWithAux f KVChain.nil xs True.intro a b True.intro).val =
      ({ toList := [{ fst := a, snd := b }],
          ascend := (_ : List.Ascending (Sigma.relOnFst (flip r)) [{ fst := a, snd := b }]) },
        xs)
haa₁ : r a a₁
⊢ (insertWithAux f KVChain.nil (KVChain.cons a₁ b₁ xs ha₁xs) True.intro a b True.intro).val =
    ({ toList := [{ fst := a, snd := b }],
        ascend := (_ : List.Ascending (Sigma.relOnFst (flip r)) [{ fst := a, snd := b }]) },
      KVChain.cons a₁ b₁ xs ha₁xs)

State before:
α : Type u
r : α → α → Prop
inst✝¹ : StrictLinearOrder r
inst✝ : DecidableRel r
β : α → Type v
f : (a : α) → β a → β a → Option (β a)
xs✝ : KVChain r β
a : α
b : β a
ys : KVChain r β
hays : boundLeft a ys
a₁ : α
b₁ : β a₁
xs : KVChain r fun a => β a
ha₁xs : boundLeft a₁ xs
a✝ :
  boundLeft a xs →
    (insertWithAux f KVChain.nil xs True.intro a b True.intro).val =
      ({ toList := [{ fst := a, snd := b }],
          ascend := (_ : List.Ascending (Sigma.relOnFst (flip r)) [{ fst := a, snd := b }]) },
        xs)
haa₁ : r a a₁
⊢ (insertWithAux f KVChain.nil (KVChain.cons a₁ b₁ xs ha₁xs) True.intro a b True.intro).val =
    ({ toList := [{ fst := a, snd := b }],
        ascend := (_ : List.Ascending (Sigma.relOnFst (flip r)) [{ fst := a, snd := b }]) },
      KVChain.cons a₁ b₁ xs ha₁xs)
Tactic:
rw [insertWithAux_cons_flip haa₁]
State after:
no goals