| /- | |
| Copyright (c) 2024 Lean FRO, LLC. All rights reserved. | |
| Released under Apache 2.0 license as described in the file LICENSE. | |
| Authors: Markus Himmel | |
| -/ | |
| prelude | |
| import Std.Data.DHashMap.Basic | |
| import Std.Data.DHashMap.Internal.Model | |
| import Std.Data.DHashMap.Internal.AssocList.Lemmas | |
| /-! | |
| This is an internal implementation file of the hash map. Users of the hash map should not rely on | |
| the contents of this file. | |
| File contents: proof that all hash map operations preserve `WFImp` to show `WF.out : WF → WFImp` | |
| -/ | |
| open Std.DHashMap.Internal.List | |
| set_option linter.missingDocs true | |
| set_option autoImplicit false | |
| universe u v w | |
| variable {α : Type u} {β : α → Type v} {γ : Type w} {δ : α → Type w} | |
| open List | |
| namespace Std.DHashMap.Internal | |
| @[simp] | |
| theorem toListModel_mkArray_nil {c} : | |
| toListModel (mkArray c (AssocList.nil : AssocList α β)) = [] := by | |
| suffices ∀ d, (List.replicate d AssocList.nil).bind AssocList.toList = [] from this _ | |
| intro d | |
| induction d <;> simp_all [List.replicate] | |
| @[simp] | |
| theorem computeSize_eq {buckets : Array (AssocList α β)} : | |
| computeSize buckets = (toListModel buckets).length := by | |
| rw [computeSize, toListModel, List.bind_eq_foldl, Array.foldl_eq_foldl_toList] | |
| suffices ∀ (l : List (AssocList α β)) (l' : List ((a : α) × β a)), | |
| l.foldl (fun d b => d + b.toList.length) l'.length = | |
| (l.foldl (fun acc a => acc ++ a.toList) l').length | |
| by simpa using this buckets.toList [] | |
| intro l l' | |
| induction l generalizing l' | |
| · simp | |
| · next l₂ t ih => rw [foldl_cons, ← List.length_append, ih, foldl_cons] | |
| namespace Raw | |
| theorem size_eq_length [BEq α] [Hashable α] {m : Raw α β} (h : Raw.WFImp m) : | |
| m.size = (toListModel m.buckets).length := | |
| h.size_eq | |
| theorem isEmpty_eq_isEmpty [BEq α] [Hashable α] {m : Raw α β} (h : Raw.WFImp m) : | |
| m.isEmpty = (toListModel m.buckets).isEmpty := by | |
| rw [Raw.isEmpty, Bool.eq_iff_iff, List.isEmpty_iff_length_eq_zero, size_eq_length h, | |
| Nat.beq_eq_true_eq] | |
| end Raw | |
| namespace Raw₀ | |
| /-! # Raw₀.empty -/ | |
| @[simp] | |
| theorem toListModel_buckets_empty {c} : toListModel (empty c : Raw₀ α β).1.buckets = [] := | |
| toListModel_mkArray_nil | |
| theorem wfImp_empty [BEq α] [Hashable α] {c} : Raw.WFImp (empty c : Raw₀ α β).1 where | |
| buckets_hash_self := by simp [Raw.empty, Raw₀.empty] | |
| size_eq := by simp [Raw.empty, Raw₀.empty] | |
| distinct := by simp | |
| theorem isHashSelf_reinsertAux [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] | |
| (data : {d : Array (AssocList α β) // 0 < d.size}) (a : α) (b : β a) (h : IsHashSelf data.1) : | |
| IsHashSelf (reinsertAux hash data a b).1 := by | |
| rw [reinsertAux_eq] | |
| refine h.updateBucket (fun l p hp => ?_) | |
| simp only [AssocList.toList_cons, mem_cons] at hp | |
| rcases hp with (rfl|hp) | |
| · exact Or.inr rfl | |
| · exact Or.inl (containsKey_of_mem hp) | |
| /-! # expandIfNecessary -/ | |
| theorem toListModel_reinsertAux [BEq α] [Hashable α] [PartialEquivBEq α] | |
| (data : {d : Array (AssocList α β) // 0 < d.size}) (a : α) (b : β a) : | |
| Perm (toListModel (reinsertAux hash data a b).1) (⟨a, b⟩ :: toListModel data.1) := by | |
| rw [reinsertAux_eq] | |
| obtain ⟨l, h₁, h₂, -⟩ := exists_bucket_of_update data.1 data.2 a (fun l => l.cons a b) | |
| exact h₂.trans (Perm.cons _ (Perm.symm h₁)) | |
| theorem isHashSelf_foldl_reinsertAux [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] | |
| (l : List ((a : α) × β a)) (target : { d : Array (AssocList α β) // 0 < d.size }) : | |
| IsHashSelf target.1 → | |
| IsHashSelf (l.foldl (fun acc p => reinsertAux hash acc p.1 p.2) target).1 := by | |
| induction l generalizing target | |
| · simp [Id.run] | |
| · next k v _ ih => exact fun h => ih _ (isHashSelf_reinsertAux _ _ _ h) | |
| theorem toListModel_foldl_reinsertAux [BEq α] [Hashable α] [PartialEquivBEq α] | |
| (l : List ((a : α) × β a)) (target : { d : Array (AssocList α β) // 0 < d.size }) : | |
| Perm (toListModel (l.foldl (fun acc p => reinsertAux hash acc p.1 p.2) target).1) | |
| (l ++ toListModel target.1) := by | |
| induction l generalizing target | |
| · simp | |
| · next k v t ih => | |
| simp only [foldl_cons, cons_append] | |
| refine (ih _).trans ?_ | |
| refine ((toListModel_reinsertAux _ _ _).append_left _).trans perm_middle | |
| theorem expand.go_pos [Hashable α] {i : Nat} {source : Array (AssocList α β)} | |
| {target : { d : Array (AssocList α β) // 0 < d.size }} (h : i < source.size) : | |
| expand.go i source target = go (i + 1) | |
| (source.set ⟨i, h⟩ .nil) ((source.get ⟨i, h⟩).foldl (reinsertAux hash) target) := by | |
| rw [expand.go] | |
| simp only [h, dite_true] | |
| theorem expand.go_neg [Hashable α] {i : Nat} {source : Array (AssocList α β)} | |
| {target : { d : Array (AssocList α β) // 0 < d.size}} (h : ¬i < source.size) : | |
| expand.go i source target = target := by | |
| rw [expand.go] | |
| simp only [h, dite_false] | |
| theorem expand.go_eq [BEq α] [Hashable α] [PartialEquivBEq α] (source : Array (AssocList α β)) | |
| (target : {d : Array (AssocList α β) // 0 < d.size}) : expand.go 0 source target = | |
| (toListModel source).foldl (fun acc p => reinsertAux hash acc p.1 p.2) target := by | |
| suffices ∀ i, expand.go i source target = | |
| ((source.toList.drop i).bind AssocList.toList).foldl | |
| (fun acc p => reinsertAux hash acc p.1 p.2) target by | |
| simpa using this 0 | |
| intro i | |
| induction i, source, target using expand.go.induct | |
| · next i source target hi _ es newSource newTarget ih => | |
| simp only [newSource, newTarget, es] at * | |
| rw [expand.go_pos hi] | |
| refine ih.trans ?_ | |
| simp only [Array.get_eq_getElem, AssocList.foldl_eq, Array.toList_set] | |
| rw [List.drop_eq_getElem_cons hi, List.bind_cons, List.foldl_append, | |
| List.drop_set_of_lt _ _ (by omega), Array.getElem_eq_getElem_toList] | |
| · next i source target hi => | |
| rw [expand.go_neg hi, List.drop_eq_nil_of_le, bind_nil, foldl_nil] | |
| rwa [Array.size_eq_length_toList, Nat.not_lt] at hi | |
| theorem isHashSelf_expand [BEq α] [Hashable α] [LawfulHashable α] [EquivBEq α] | |
| {buckets : {d : Array (AssocList α β) // 0 < d.size}} : IsHashSelf (expand buckets).1 := by | |
| simpa [expand, expand.go_eq] using isHashSelf_foldl_reinsertAux _ _ (by simp) | |
| theorem toListModel_expand [BEq α] [Hashable α] [PartialEquivBEq α] | |
| {buckets : {d : Array (AssocList α β) // 0 < d.size}} : | |
| Perm (toListModel (expand buckets).1) (toListModel buckets.1) := by | |
| simpa [expand, expand.go_eq] using toListModel_foldl_reinsertAux (toListModel buckets.1) | |
| ⟨mkArray (buckets.1.size * 2) .nil, by simpa using Nat.mul_pos buckets.2 Nat.two_pos⟩ | |
| theorem toListModel_expandIfNecessary [BEq α] [Hashable α] [PartialEquivBEq α] (m : Raw₀ α β) : | |
| Perm (toListModel (expandIfNecessary m).1.2) (toListModel m.1.2) := by | |
| rw [expandIfNecessary] | |
| dsimp | |
| split | |
| · exact Perm.refl _ | |
| · dsimp | |
| exact toListModel_expand | |
| theorem wfImp_expandIfNecessary [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (m : Raw₀ α β) | |
| (h : Raw.WFImp m.1) : Raw.WFImp (expandIfNecessary m).1 := by | |
| rw [Raw₀.expandIfNecessary] | |
| dsimp | |
| split | |
| · exact h | |
| · let ⟨⟨size, buckets⟩, hm⟩ := m | |
| have := toListModel_expand (buckets := ⟨buckets, hm⟩) | |
| dsimp at this | |
| refine ⟨?_, ?_, ?_⟩ | |
| · simpa using isHashSelf_expand | |
| · refine h.size_eq.trans ?_ | |
| simpa using this.symm.length_eq | |
| · simpa using h.distinct.perm this | |
| /-! # Access operations -/ | |
| theorem containsₘ_eq_containsKey [BEq α] [Hashable α] [PartialEquivBEq α] [LawfulHashable α] | |
| {m : Raw₀ α β} (hm : Raw.WFImp m.1) {a : α} : | |
| m.containsₘ a = containsKey a (toListModel m.1.buckets) := | |
| apply_bucket hm AssocList.contains_eq (fun _ => List.containsKey_of_perm) | |
| List.containsKey_append_of_not_contains_right | |
| theorem contains_eq_containsKey [BEq α] [Hashable α] [PartialEquivBEq α] [LawfulHashable α] | |
| {m : Raw₀ α β} (hm : Raw.WFImp m.1) {a : α} : | |
| m.contains a = containsKey a (toListModel m.1.buckets) := by | |
| rw [contains_eq_containsₘ, containsₘ_eq_containsKey hm] | |
| theorem get?ₘ_eq_getValueCast? [BEq α] [Hashable α] [LawfulBEq α] | |
| {m : Raw₀ α β} (hm : Raw.WFImp m.1) {a : α} : | |
| m.get?ₘ a = getValueCast? a (toListModel m.1.buckets) := | |
| apply_bucket hm AssocList.getCast?_eq List.getValueCast?_of_perm | |
| List.getValueCast?_append_of_containsKey_eq_false | |
| theorem get?_eq_getValueCast? [BEq α] [Hashable α] [LawfulBEq α] | |
| {m : Raw₀ α β} (hm : Raw.WFImp m.1) {a : α} : | |
| m.get? a = getValueCast? a (toListModel m.1.buckets) := by | |
| rw [get?_eq_get?ₘ, get?ₘ_eq_getValueCast? hm] | |
| theorem getₘ_eq_getValue [BEq α] [Hashable α] [LawfulBEq α] {m : Raw₀ α β} (hm : Raw.WFImp m.1) | |
| {a : α} {h : m.containsₘ a} : | |
| m.getₘ a h = getValueCast a (toListModel m.1.buckets) (containsₘ_eq_containsKey hm ▸ h) := | |
| apply_bucket_with_proof hm a AssocList.getCast List.getValueCast AssocList.getCast_eq | |
| List.getValueCast_of_perm List.getValueCast_append_of_containsKey_eq_false | |
| theorem get_eq_getValueCast [BEq α] [Hashable α] [LawfulBEq α] {m : Raw₀ α β} (hm : Raw.WFImp m.1) | |
| {a : α} {h : m.contains a} : | |
| m.get a h = getValueCast a (toListModel m.1.buckets) (contains_eq_containsKey hm ▸ h) := by | |
| rw [get_eq_getₘ, getₘ_eq_getValue hm] | |
| theorem get!ₘ_eq_getValueCast! [BEq α] [Hashable α] [LawfulBEq α] {m : Raw₀ α β} | |
| (hm : Raw.WFImp m.1) {a : α} [Inhabited (β a)] : | |
| m.get!ₘ a = getValueCast! a (toListModel m.1.buckets) := by | |
| rw [get!ₘ, get?ₘ_eq_getValueCast? hm, List.getValueCast!_eq_getValueCast?] | |
| theorem get!_eq_getValueCast! [BEq α] [Hashable α] [LawfulBEq α] {m : Raw₀ α β} (hm : Raw.WFImp m.1) | |
| {a : α} [Inhabited (β a)] : m.get! a = getValueCast! a (toListModel m.1.buckets) := by | |
| rw [get!_eq_get!ₘ, get!ₘ_eq_getValueCast! hm] | |
| theorem getDₘ_eq_getValueCastD [BEq α] [Hashable α] [LawfulBEq α] {m : Raw₀ α β} | |
| (hm : Raw.WFImp m.1) {a : α} {fallback : β a} : | |
| m.getDₘ a fallback = getValueCastD a (toListModel m.1.buckets) fallback := by | |
| rw [getDₘ, get?ₘ_eq_getValueCast? hm, List.getValueCastD_eq_getValueCast?] | |
| theorem getD_eq_getValueCastD [BEq α] [Hashable α] [LawfulBEq α] {m : Raw₀ α β} (hm : Raw.WFImp m.1) | |
| {a : α} {fallback : β a} : | |
| m.getD a fallback = getValueCastD a (toListModel m.1.buckets) fallback := by | |
| rw [getD_eq_getDₘ, getDₘ_eq_getValueCastD hm] | |
| theorem getKey?ₘ_eq_getKey? [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {m : Raw₀ α β} | |
| (hm : Raw.WFImp m.1) {a : α} : | |
| m.getKey?ₘ a = List.getKey? a (toListModel m.1.buckets) := | |
| apply_bucket hm AssocList.getKey?_eq List.getKey?_of_perm List.getKey?_append_of_containsKey_eq_false | |
| theorem getKey?_eq_getKey? [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {m : Raw₀ α β} | |
| (hm : Raw.WFImp m.1) {a : α} : | |
| m.getKey? a = List.getKey? a (toListModel m.1.buckets) := by | |
| rw [getKey?_eq_getKey?ₘ, getKey?ₘ_eq_getKey? hm] | |
| theorem getKeyₘ_eq_getKey [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {m : Raw₀ α β} | |
| (hm : Raw.WFImp m.1) {a : α} {h : m.contains a} : | |
| m.getKeyₘ a h = List.getKey a (toListModel m.1.buckets) (contains_eq_containsKey hm ▸ h) := | |
| apply_bucket_with_proof hm a AssocList.getKey List.getKey AssocList.getKey_eq | |
| List.getKey_of_perm List.getKey_append_of_containsKey_eq_false | |
| theorem getKey_eq_getKey [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {m : Raw₀ α β} | |
| (hm : Raw.WFImp m.1) {a : α} {h : m.contains a} : | |
| m.getKey a h = List.getKey a (toListModel m.1.buckets) (contains_eq_containsKey hm ▸ h) := by | |
| rw [getKey_eq_getKeyₘ, getKeyₘ_eq_getKey hm] | |
| theorem getKey!ₘ_eq_getKey! [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] [Inhabited α] | |
| {m : Raw₀ α β} (hm : Raw.WFImp m.1) {a : α} : | |
| m.getKey!ₘ a = List.getKey! a (toListModel m.1.buckets) := by | |
| rw [getKey!ₘ, getKey?ₘ_eq_getKey? hm, List.getKey!_eq_getKey?] | |
| theorem getKey!_eq_getKey! [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] [Inhabited α] | |
| {m : Raw₀ α β} (hm : Raw.WFImp m.1) {a : α} : | |
| m.getKey! a = List.getKey! a (toListModel m.1.buckets) := by | |
| rw [getKey!_eq_getKey!ₘ, getKey!ₘ_eq_getKey! hm] | |
| theorem getKeyDₘ_eq_getKeyD [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {m : Raw₀ α β} | |
| (hm : Raw.WFImp m.1) {a fallback : α} : | |
| m.getKeyDₘ a fallback = List.getKeyD a (toListModel m.1.buckets) fallback := by | |
| rw [getKeyDₘ, getKey?ₘ_eq_getKey? hm, List.getKeyD_eq_getKey?] | |
| theorem getKeyD_eq_getKeyD [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {m : Raw₀ α β} | |
| (hm : Raw.WFImp m.1) {a fallback : α} : | |
| m.getKeyD a fallback = List.getKeyD a (toListModel m.1.buckets) fallback := by | |
| rw [getKeyD_eq_getKeyDₘ, getKeyDₘ_eq_getKeyD hm] | |
| section | |
| variable {β : Type v} | |
| theorem Const.get?ₘ_eq_getValue? [BEq α] [Hashable α] [PartialEquivBEq α] [LawfulHashable α] | |
| {m : Raw₀ α (fun _ => β)} (hm : Raw.WFImp m.1) {a : α} : | |
| Const.get?ₘ m a = getValue? a (toListModel m.1.buckets) := | |
| apply_bucket hm AssocList.get?_eq List.getValue?_of_perm getValue?_append_of_containsKey_eq_false | |
| theorem Const.get?_eq_getValue? [BEq α] [Hashable α] [PartialEquivBEq α] [LawfulHashable α] | |
| {m : Raw₀ α (fun _ => β)} (hm : Raw.WFImp m.1) {a : α} : | |
| Const.get? m a = getValue? a (toListModel m.1.buckets) := by | |
| rw [Const.get?_eq_get?ₘ, Const.get?ₘ_eq_getValue? hm] | |
| theorem Const.getₘ_eq_getValue [BEq α] [Hashable α] [PartialEquivBEq α] [LawfulHashable α] | |
| {m : Raw₀ α (fun _ => β)} (hm : Raw.WFImp m.1) {a : α} {h} : | |
| Const.getₘ m a h = getValue a (toListModel m.1.buckets) (containsₘ_eq_containsKey hm ▸ h) := | |
| apply_bucket_with_proof hm a AssocList.get List.getValue AssocList.get_eq List.getValue_of_perm | |
| List.getValue_append_of_containsKey_eq_false | |
| theorem Const.get_eq_getValue [BEq α] [Hashable α] [PartialEquivBEq α] [LawfulHashable α] | |
| {m : Raw₀ α (fun _ => β)} (hm : Raw.WFImp m.1) {a : α} {h} : | |
| Const.get m a h = getValue a (toListModel m.1.buckets) (contains_eq_containsKey hm ▸ h) := by | |
| rw [Const.get_eq_getₘ, Const.getₘ_eq_getValue hm] | |
| theorem Const.get!ₘ_eq_getValue! [BEq α] [Hashable α] [PartialEquivBEq α] [LawfulHashable α] | |
| [Inhabited β] {m : Raw₀ α (fun _ => β)} (hm : Raw.WFImp m.1) {a : α} : | |
| Const.get!ₘ m a = getValue! a (toListModel m.1.buckets) := by | |
| rw [get!ₘ, get?ₘ_eq_getValue? hm, List.getValue!_eq_getValue?] | |
| theorem Const.get!_eq_getValue! [BEq α] [Hashable α] [PartialEquivBEq α] [LawfulHashable α] | |
| [Inhabited β] {m : Raw₀ α (fun _ => β)} (hm : Raw.WFImp m.1) {a : α} : | |
| Const.get! m a = getValue! a (toListModel m.1.buckets) := by | |
| rw [get!_eq_get!ₘ, get!ₘ_eq_getValue! hm] | |
| theorem Const.getDₘ_eq_getValueD [BEq α] [Hashable α] [PartialEquivBEq α] [LawfulHashable α] | |
| {m : Raw₀ α (fun _ => β)} (hm : Raw.WFImp m.1) {a : α} {fallback : β} : | |
| Const.getDₘ m a fallback = getValueD a (toListModel m.1.buckets) fallback := by | |
| rw [getDₘ, get?ₘ_eq_getValue? hm, List.getValueD_eq_getValue?] | |
| theorem Const.getD_eq_getValueD [BEq α] [Hashable α] [PartialEquivBEq α] [LawfulHashable α] | |
| {m : Raw₀ α (fun _ => β)} (hm : Raw.WFImp m.1) {a : α} {fallback : β} : | |
| Const.getD m a fallback = getValueD a (toListModel m.1.buckets) fallback := by | |
| rw [getD_eq_getDₘ, getDₘ_eq_getValueD hm] | |
| end | |
| /-! # `replaceₘ` -/ | |
| theorem toListModel_replaceₘ [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (m : Raw₀ α β) | |
| (h : Raw.WFImp m.1) (a : α) (b : β a) : | |
| Perm (toListModel (m.replaceₘ a b).1.buckets) (replaceEntry a b (toListModel m.1.2)) := | |
| toListModel_updateBucket h AssocList.toList_replace List.replaceEntry_of_perm | |
| List.replaceEntry_append_of_containsKey_right_eq_false | |
| theorem isHashSelf_replaceₘ [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (m : Raw₀ α β) | |
| (h : Raw.WFImp m.1) (a : α) (b : β a) : IsHashSelf (m.replaceₘ a b).1.buckets := by | |
| apply h.buckets_hash_self.updateBucket (fun l p hp => ?_) | |
| exact Or.inl (by simpa using containsKey_of_mem hp) | |
| theorem wfImp_replaceₘ [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (m : Raw₀ α β) | |
| (h : Raw.WFImp m.1) (a : α) (b : β a) : Raw.WFImp (m.replaceₘ a b).1 where | |
| buckets_hash_self := isHashSelf_replaceₘ m h a b | |
| size_eq := h.size_eq.trans | |
| (Eq.trans length_replaceEntry.symm (toListModel_replaceₘ _ h _ _).length_eq.symm) | |
| distinct := h.distinct.replaceEntry.perm (toListModel_replaceₘ _ h _ _) | |
| /-! # `insertₘ` -/ | |
| theorem toListModel_consₘ [BEq α] [Hashable α] [PartialEquivBEq α] [LawfulHashable α] | |
| (m : Raw₀ α β) (h : Raw.WFImp m.1) (a : α) (b : β a) : | |
| Perm (toListModel (m.consₘ a b).1.buckets) (⟨a, b⟩ :: (toListModel m.1.2)) := | |
| toListModel_updateBucket h rfl (fun _ => Perm.cons _) (fun _ => cons_append _ _ _) | |
| theorem isHashSelf_consₘ [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (m : Raw₀ α β) | |
| (h : Raw.WFImp m.1) (a : α) (b : β a) : IsHashSelf (m.consₘ a b).1.buckets := by | |
| apply h.buckets_hash_self.updateBucket (fun l p hp => ?_) | |
| simp only [AssocList.toList_cons, mem_cons] at hp | |
| rcases hp with (rfl|hp) | |
| · exact Or.inr rfl | |
| · exact Or.inl (containsKey_of_mem hp) | |
| theorem wfImp_consₘ [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (m : Raw₀ α β) | |
| (h : Raw.WFImp m.1) (a : α) (b : β a) (hc : m.containsₘ a = false) : | |
| Raw.WFImp (m.consₘ a b).1 where | |
| buckets_hash_self := isHashSelf_consₘ m h a b | |
| size_eq := by | |
| refine Eq.trans ?_ (toListModel_consₘ _ h _ _).length_eq.symm | |
| simpa [consₘ] using h.size_eq | |
| distinct := by | |
| refine (h.distinct.cons ?_).perm (toListModel_consₘ _ h _ _) | |
| rwa [← containsₘ_eq_containsKey h] | |
| theorem toListModel_insertₘ [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {m : Raw₀ α β} | |
| (h : Raw.WFImp m.1) {a : α} {b : β a} : | |
| Perm (toListModel (m.insertₘ a b).1.2) (insertEntry a b (toListModel m.1.2)) := by | |
| rw [insertₘ] | |
| split | |
| · next h' => | |
| rw [containsₘ_eq_containsKey h] at h' | |
| rw [insertEntry_of_containsKey h'] | |
| exact toListModel_replaceₘ _ h _ _ | |
| · next h' => | |
| rw [containsₘ_eq_containsKey h, Bool.not_eq_true] at h' | |
| rw [insertEntry_of_containsKey_eq_false h'] | |
| refine (Raw₀.toListModel_expandIfNecessary _).trans ?_ | |
| exact toListModel_consₘ m h a b | |
| theorem wfImp_insertₘ [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {m : Raw₀ α β} | |
| (h : Raw.WFImp m.1) {a : α} {b : β a} : Raw.WFImp (m.insertₘ a b).1 := by | |
| rw [insertₘ] | |
| split | |
| · apply wfImp_replaceₘ _ h | |
| · apply wfImp_expandIfNecessary | |
| apply wfImp_consₘ _ h _ _ (by simp_all) | |
| /-! # `insert` -/ | |
| theorem toListModel_insert [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {m : Raw₀ α β} | |
| (h : Raw.WFImp m.1) {a : α} {b : β a} : | |
| Perm (toListModel (m.insert a b).1.2) (insertEntry a b (toListModel m.1.2)) := by | |
| rw [insert_eq_insertₘ] | |
| exact toListModel_insertₘ h | |
| theorem wfImp_insert [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {m : Raw₀ α β} | |
| (h : Raw.WFImp m.1) {a : α} {b : β a} : Raw.WFImp (m.insert a b).1 := by | |
| rw [insert_eq_insertₘ] | |
| exact wfImp_insertₘ h | |
| /-! # `containsThenInsert` -/ | |
| theorem toListModel_containsThenInsert [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] | |
| {m : Raw₀ α β} (h : Raw.WFImp m.1) {a : α} {b : β a} : | |
| Perm (toListModel (m.containsThenInsert a b).2.1.2) (insertEntry a b (toListModel m.1.2)) := by | |
| rw [containsThenInsert_eq_insertₘ] | |
| exact toListModel_insertₘ h | |
| theorem wfImp_containsThenInsert [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {m : Raw₀ α β} | |
| (h : Raw.WFImp m.1) {a : α} {b : β a} : Raw.WFImp (m.containsThenInsert a b).2.1 := by | |
| rw [containsThenInsert_eq_insertₘ] | |
| exact wfImp_insertₘ h | |
| /-! # `insertIfNewₘ` -/ | |
| theorem toListModel_insertIfNewₘ [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {m : Raw₀ α β} | |
| (h : Raw.WFImp m.1) {a : α} {b : β a} : | |
| Perm (toListModel (m.insertIfNewₘ a b).1.buckets) | |
| (insertEntryIfNew a b (toListModel m.1.buckets)) := by | |
| rw [insertIfNewₘ, insertEntryIfNew, containsₘ_eq_containsKey h, cond_eq_if] | |
| split | |
| · next h' => exact Perm.refl _ | |
| · next h' => exact (toListModel_expandIfNecessary _).trans (toListModel_consₘ m h a b) | |
| theorem wfImp_insertIfNewₘ [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {m : Raw₀ α β} | |
| (h : Raw.WFImp m.1) {a : α} {b : β a} : Raw.WFImp (m.insertIfNewₘ a b).1 := by | |
| rw [insertIfNewₘ] | |
| split | |
| · exact h | |
| · apply wfImp_expandIfNecessary | |
| apply wfImp_consₘ _ h _ _ (by simp_all) | |
| /-! # `insertIfNew` -/ | |
| theorem toListModel_insertIfNew [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {m : Raw₀ α β} | |
| (h : Raw.WFImp m.1) {a : α} {b : β a} : | |
| Perm (toListModel (m.insertIfNew a b).1.buckets) | |
| (insertEntryIfNew a b (toListModel m.1.buckets)) := by | |
| rw [insertIfNew_eq_insertIfNewₘ] | |
| exact toListModel_insertIfNewₘ h | |
| theorem wfImp_insertIfNew [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {m : Raw₀ α β} | |
| (h : Raw.WFImp m.1) {a : α} {b : β a} : Raw.WFImp (m.insertIfNew a b).1 := by | |
| rw [insertIfNew_eq_insertIfNewₘ] | |
| exact wfImp_insertIfNewₘ h | |
| /-! # `containsThenInsertIfNew` -/ | |
| theorem toListModel_containsThenInsertIfNew [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] | |
| {m : Raw₀ α β} (h : Raw.WFImp m.1) {a : α} {b : β a} : | |
| Perm (toListModel (m.containsThenInsertIfNew a b).2.1.2) | |
| (insertEntryIfNew a b (toListModel m.1.2)) := by | |
| rw [containsThenInsertIfNew_eq_insertIfNewₘ] | |
| exact toListModel_insertIfNewₘ h | |
| theorem wfImp_containsThenInsertIfNew [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] | |
| {m : Raw₀ α β} (h : Raw.WFImp m.1) {a : α} {b : β a} : | |
| Raw.WFImp (m.containsThenInsertIfNew a b).2.1 := by | |
| rw [containsThenInsertIfNew_eq_insertIfNewₘ] | |
| exact wfImp_insertIfNewₘ h | |
| /-! # `getThenInsertIfNew?` -/ | |
| theorem toListModel_getThenInsertIfNew? [BEq α] [Hashable α] [LawfulBEq α] {m : Raw₀ α β} {a : α} | |
| {b : β a} (h : Raw.WFImp m.1) : | |
| Perm (toListModel (m.getThenInsertIfNew? a b).2.1.buckets) | |
| (insertEntryIfNew a b (toListModel m.1.buckets)) := by | |
| rw [getThenInsertIfNew?_eq_insertIfNewₘ] | |
| exact toListModel_insertIfNewₘ h | |
| theorem wfImp_getThenInsertIfNew? [BEq α] [Hashable α] [LawfulBEq α] {m : Raw₀ α β} {a : α} | |
| {b : β a} (h : Raw.WFImp m.1) : Raw.WFImp (m.getThenInsertIfNew? a b).2.1 := by | |
| rw [getThenInsertIfNew?_eq_insertIfNewₘ] | |
| exact wfImp_insertIfNewₘ h | |
| /-! # `Const.getThenInsertIfNew?` -/ | |
| theorem Const.toListModel_getThenInsertIfNew? {β : Type v} [BEq α] [Hashable α] [EquivBEq α] | |
| [LawfulHashable α] {m : Raw₀ α (fun _ => β)} {a : α} {b : β} (h : Raw.WFImp m.1) : | |
| Perm (toListModel (Const.getThenInsertIfNew? m a b).2.1.buckets) | |
| (insertEntryIfNew a b (toListModel m.1.buckets)) := by | |
| rw [getThenInsertIfNew?_eq_insertIfNewₘ] | |
| exact toListModel_insertIfNewₘ h | |
| theorem Const.wfImp_getThenInsertIfNew? {β : Type v} [BEq α] [Hashable α] [EquivBEq α] | |
| [LawfulHashable α] {m : Raw₀ α (fun _ => β)} {a : α} {b : β} (h : Raw.WFImp m.1): | |
| Raw.WFImp (Const.getThenInsertIfNew? m a b).2.1 := by | |
| rw [getThenInsertIfNew?_eq_insertIfNewₘ] | |
| exact wfImp_insertIfNewₘ h | |
| /-! # `eraseₘ` -/ | |
| theorem toListModel_eraseₘaux [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (m : Raw₀ α β) | |
| (a : α) (h : Raw.WFImp m.1) : | |
| Perm (toListModel (m.eraseₘaux a).1.buckets) (eraseKey a (toListModel m.1.buckets)) := | |
| toListModel_updateBucket h AssocList.toList_erase List.eraseKey_of_perm | |
| List.eraseKey_append_of_containsKey_right_eq_false | |
| theorem isHashSelf_eraseₘaux [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (m : Raw₀ α β) | |
| (a : α) (h : Raw.WFImp m.1) : IsHashSelf (m.eraseₘaux a).1.buckets := by | |
| apply h.buckets_hash_self.updateBucket (fun l p hp => ?_) | |
| rw [AssocList.toList_erase] at hp | |
| exact Or.inl (containsKey_of_mem ((sublist_eraseKey.mem hp))) | |
| theorem wfImp_eraseₘaux [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] (m : Raw₀ α β) (a : α) | |
| (h : Raw.WFImp m.1) (h' : m.containsₘ a = true) : Raw.WFImp (m.eraseₘaux a).1 where | |
| buckets_hash_self := isHashSelf_eraseₘaux m a h | |
| size_eq := by | |
| rw [(toListModel_eraseₘaux m a h).length_eq, eraseₘaux, length_eraseKey, | |
| ← containsₘ_eq_containsKey h, h'] | |
| simp [h.size_eq] | |
| distinct := h.distinct.eraseKey.perm (toListModel_eraseₘaux m a h) | |
| theorem toListModel_perm_eraseKey_of_containsₘ_eq_false [BEq α] [Hashable α] [EquivBEq α] | |
| [LawfulHashable α] (m : Raw₀ α β) (a : α) (h : Raw.WFImp m.1) (h' : m.containsₘ a = false) : | |
| Perm (toListModel m.1.buckets) (eraseKey a (toListModel m.1.buckets)) := by | |
| rw [eraseKey_of_containsKey_eq_false] | |
| rw [← containsₘ_eq_containsKey h, h'] | |
| theorem toListModel_eraseₘ [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {m : Raw₀ α β} | |
| {a : α} (h : Raw.WFImp m.1) : | |
| Perm (toListModel (m.eraseₘ a).1.buckets) (eraseKey a (toListModel m.1.buckets)) := by | |
| rw [eraseₘ] | |
| split | |
| · exact toListModel_eraseₘaux m a h | |
| · next h' => | |
| exact toListModel_perm_eraseKey_of_containsₘ_eq_false _ _ h (eq_false_of_ne_true h') | |
| theorem wfImp_eraseₘ [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {m : Raw₀ α β} {a : α} | |
| (h : Raw.WFImp m.1) : Raw.WFImp (m.eraseₘ a).1 := by | |
| rw [eraseₘ] | |
| split | |
| · next h' => exact wfImp_eraseₘaux m a h h' | |
| · exact h | |
| /-! # `erase` -/ | |
| theorem toListModel_erase [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {m : Raw₀ α β} | |
| {a : α} (h : Raw.WFImp m.1) : | |
| Perm (toListModel (m.erase a).1.buckets) (eraseKey a (toListModel m.1.buckets)) := by | |
| rw [erase_eq_eraseₘ] | |
| exact toListModel_eraseₘ h | |
| theorem wfImp_erase [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {m : Raw₀ α β} {a : α} | |
| (h : Raw.WFImp m.1) : Raw.WFImp (m.erase a).1 := by | |
| rw [erase_eq_eraseₘ] | |
| exact wfImp_eraseₘ h | |
| /-! # `filterMapₘ` -/ | |
| theorem toListModel_filterMapₘ {m : Raw₀ α β} {f : (a : α) → β a → Option (δ a)} : | |
| Perm (toListModel (m.filterMapₘ f).1.buckets) | |
| ((toListModel m.1.buckets).filterMap fun p => (f p.1 p.2).map (⟨p.1, ·⟩)) := | |
| toListModel_updateAllBuckets AssocList.toList_filterMap | |
| (by simp [List.filterMap_append]) | |
| theorem isHashSelf_filterMapₘ [BEq α] [Hashable α] [ReflBEq α] [LawfulHashable α] {m : Raw₀ α β} | |
| {f : (a : α) → β a → Option (δ a)} (h : Raw.WFImp m.1) : | |
| IsHashSelf (m.filterMapₘ f).1.buckets := by | |
| refine h.buckets_hash_self.updateAllBuckets (fun l p hp => ?_) | |
| have hp := AssocList.toList_filterMap.mem_iff.1 hp | |
| simp only [mem_filterMap, Option.map_eq_some'] at hp | |
| obtain ⟨p, ⟨hkv, ⟨d, ⟨-, rfl⟩⟩⟩⟩ := hp | |
| exact containsKey_of_mem hkv | |
| theorem wfImp_filterMapₘ [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {m : Raw₀ α β} | |
| {f : (a : α) → β a → Option (δ a)} (h : Raw.WFImp m.1) : Raw.WFImp (m.filterMapₘ f).1 where | |
| buckets_hash_self := isHashSelf_filterMapₘ h | |
| size_eq := by simp [filterMapₘ] | |
| distinct := h.distinct.filterMap.perm toListModel_filterMapₘ | |
| /-! # `filterMap` -/ | |
| theorem toListModel_filterMap {m : Raw₀ α β} {f : (a : α) → β a → Option (δ a)} : | |
| Perm (toListModel (m.filterMap f).1.buckets) | |
| ((toListModel m.1.buckets).filterMap fun p => (f p.1 p.2).map (⟨p.1, ·⟩)) := by | |
| rw [filterMap_eq_filterMapₘ] | |
| exact toListModel_filterMapₘ | |
| theorem wfImp_filterMap [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {m : Raw₀ α β} | |
| {f : (a : α) → β a → Option (δ a)} (h : Raw.WFImp m.1) : | |
| Raw.WFImp (m.filterMap f).1 := by | |
| rw [filterMap_eq_filterMapₘ] | |
| exact wfImp_filterMapₘ h | |
| /-! # `mapₘ` -/ | |
| theorem toListModel_mapₘ {m : Raw₀ α β} {f : (a : α) → β a → δ a} : | |
| Perm (toListModel (m.mapₘ f).1.buckets) | |
| ((toListModel m.1.buckets).map fun p => ⟨p.1, f p.1 p.2⟩) := | |
| toListModel_updateAllBuckets AssocList.toList_map (by simp) | |
| theorem isHashSelf_mapₘ [BEq α] [Hashable α] [ReflBEq α] [LawfulHashable α] {m : Raw₀ α β} | |
| {f : (a : α) → β a → δ a} (h : Raw.WFImp m.1) : IsHashSelf (m.mapₘ f).1.buckets := by | |
| refine h.buckets_hash_self.updateAllBuckets (fun l p hp => ?_) | |
| have hp := AssocList.toList_map.mem_iff.1 hp | |
| obtain ⟨p, hp₁, rfl⟩ := mem_map.1 hp | |
| exact containsKey_of_mem hp₁ | |
| theorem wfImp_mapₘ [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {m : Raw₀ α β} | |
| {f : (a : α) → β a → δ a} (h : Raw.WFImp m.1) : Raw.WFImp (m.mapₘ f).1 where | |
| buckets_hash_self := isHashSelf_mapₘ h | |
| size_eq := by rw [toListModel_mapₘ.length_eq, List.length_map, ← h.size_eq, mapₘ] | |
| distinct := h.distinct.map.perm toListModel_mapₘ | |
| /-! # `map` -/ | |
| theorem toListModel_map {m : Raw₀ α β} {f : (a : α) → β a → δ a} : | |
| Perm (toListModel (m.map f).1.buckets) | |
| ((toListModel m.1.buckets).map fun p => ⟨p.1, f p.1 p.2⟩) := by | |
| rw [map_eq_mapₘ] | |
| exact toListModel_mapₘ | |
| theorem wfImp_map [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {m : Raw₀ α β} | |
| {f : (a : α) → β a → δ a} (h : Raw.WFImp m.1) : Raw.WFImp (m.map f).1 := by | |
| rw [map_eq_mapₘ] | |
| exact wfImp_mapₘ h | |
| /-! # `filterₘ` -/ | |
| theorem toListModel_filterₘ {m : Raw₀ α β} {f : (a : α) → β a → Bool} : | |
| Perm (toListModel (m.filterₘ f).1.buckets) | |
| ((toListModel m.1.buckets).filter fun p => f p.1 p.2) := | |
| toListModel_updateAllBuckets AssocList.toList_filter (by simp) | |
| theorem isHashSelf_filterₘ [BEq α] [Hashable α] [ReflBEq α] [LawfulHashable α] {m : Raw₀ α β} | |
| {f : (a : α) → β a → Bool} (h : Raw.WFImp m.1) : IsHashSelf (m.filterₘ f).1.buckets := by | |
| refine h.buckets_hash_self.updateAllBuckets (fun l p hp => ?_) | |
| have hp := AssocList.toList_filter.mem_iff.1 hp | |
| obtain ⟨hp, -⟩ := mem_filter.1 hp | |
| exact containsKey_of_mem hp | |
| theorem wfImp_filterₘ [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {m : Raw₀ α β} | |
| {f : (a : α) → β a → Bool} (h : Raw.WFImp m.1) : Raw.WFImp (m.filterₘ f).1 where | |
| buckets_hash_self := isHashSelf_filterₘ h | |
| size_eq := by simp [filterₘ] | |
| distinct := h.distinct.filter.perm toListModel_filterₘ | |
| /-! # `filter` -/ | |
| theorem toListModel_filter {m : Raw₀ α β} {f : (a : α) → β a → Bool} : | |
| Perm (toListModel (m.filter f).1.buckets) | |
| ((toListModel m.1.buckets).filter fun p => f p.1 p.2) := by | |
| rw [filter_eq_filterₘ] | |
| exact toListModel_filterₘ | |
| theorem wfImp_filter [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {m : Raw₀ α β} | |
| {f : (a : α) → β a → Bool} (h : Raw.WFImp m.1) : Raw.WFImp (m.filter f).1 := by | |
| rw [filter_eq_filterₘ] | |
| exact wfImp_filterₘ h | |
| end Raw₀ | |
| namespace Raw | |
| theorem WF.out [BEq α] [Hashable α] [i₁ : EquivBEq α] [i₂ : LawfulHashable α] {m : Raw α β} | |
| (h : m.WF) : Raw.WFImp m := by | |
| induction h generalizing i₁ i₂ | |
| · next h => apply h | |
| · exact Raw₀.wfImp_empty | |
| · next h => exact Raw₀.wfImp_insert (by apply h) | |
| · next h => exact Raw₀.wfImp_containsThenInsert (by apply h) | |
| · next h => exact Raw₀.wfImp_containsThenInsertIfNew (by apply h) | |
| · next h => exact Raw₀.wfImp_erase (by apply h) | |
| · next h => exact Raw₀.wfImp_insertIfNew (by apply h) | |
| · next h => exact Raw₀.wfImp_getThenInsertIfNew? (by apply h) | |
| · next h => exact Raw₀.wfImp_filter (by apply h) | |
| · next h => exact Raw₀.Const.wfImp_getThenInsertIfNew? (by apply h) | |
| end Raw | |
| namespace Raw₀ | |
| theorem wfImp_insertMany [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {ρ : Type w} | |
| [ForIn Id ρ ((a : α) × β a)] {m : Raw₀ α β} {l : ρ} (h : Raw.WFImp m.1) : | |
| Raw.WFImp (m.insertMany l).1.1 := | |
| Raw.WF.out ((m.insertMany l).2 _ Raw.WF.insert₀ (.wf m.2 h)) | |
| theorem Const.wfImp_insertMany {β : Type v} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] | |
| {ρ : Type w} [ForIn Id ρ (α × β)] {m : Raw₀ α (fun _ => β)} | |
| {l : ρ} (h : Raw.WFImp m.1) : Raw.WFImp (Const.insertMany m l).1.1 := | |
| Raw.WF.out ((Const.insertMany m l).2 _ Raw.WF.insert₀ (.wf m.2 h)) | |
| theorem Const.wfImp_insertManyUnit [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {ρ : Type w} | |
| [ForIn Id ρ α] {m : Raw₀ α (fun _ => Unit)} {l : ρ} (h : Raw.WFImp m.1) : | |
| Raw.WFImp (Const.insertManyUnit m l).1.1 := | |
| Raw.WF.out ((Const.insertManyUnit m l).2 _ Raw.WF.insert₀ (.wf m.2 h)) | |
| end Raw₀ |