blob: b62c66248c8660a7e307f02cc7fcd6aa064182ec [file]
/-
Copyright (c) 2024 Lean FRO, LLC. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Markus Himmel
-/
module
prelude
import all Std.Data.Internal.List.Associative
import all Std.Data.DHashMap.Raw
import all Std.Data.DHashMap.Internal.Defs
public import Std.Data.DHashMap.Internal.Model
import all Std.Data.DHashMap.Internal.AssocList.Basic
import all Std.Data.DHashMap.RawDef
import Init.Data.Array.Bootstrap
import Init.Data.List.Nat.TakeDrop
import Init.Data.List.TakeDrop
public section
/-!
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.Internal.List
open Std.Internal
set_option linter.missingDocs true
set_option autoImplicit false
universe u v w w'
variable {α : Type u} {β : α → Type v} {γ : Type w} {δ : α → Type w}
open List
namespace Std.DHashMap.Internal
@[simp]
theorem toListModel_replicate_nil {c} :
toListModel (Array.replicate c (AssocList.nil : AssocList α β)) = [] := by
suffices ∀ d, (List.replicate d AssocList.nil).flatMap 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.flatMap_eq_foldl, Array.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 equiv_iff_toListModel_perm {m₁ m₂ : Raw α β} :
m₁.Equiv m₂ ↔ toListModel m₁.2 ~ toListModel m₂.2 :=
⟨Raw.Equiv.impl, Raw.Equiv.mk⟩
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]
theorem fold_eq {l : Raw α β} {f : γ → (a : α) → β a → γ} {init : γ} :
l.fold f init = l.buckets.foldl (fun acc l => l.foldl f acc) init := (rfl)
theorem fold_cons_apply {l : Raw α β} {acc : List γ} (f : (a : α) → β a → γ) :
l.fold (fun acc k v => f k v :: acc) acc =
((toListModel l.buckets).reverse.map (fun p => f p.1 p.2)) ++ acc := by
rw [fold_eq, ← Array.foldl_toList, toListModel]
induction l.buckets.toList generalizing acc with
| nil => simp
| cons x xs ih =>
rw [foldl_cons, ih, AssocList.foldl_apply]
simp
theorem fold_cons {l : Raw α β} {acc : List ((a : α) × β a)} :
l.fold (fun acc k v => ⟨k, v⟩ :: acc) acc = (toListModel l.buckets).reverse ++ acc := by
simp [fold_cons_apply]
theorem fold_cons_key {l : Raw α β} {acc : List α} :
l.fold (fun acc k _ => k :: acc) acc = List.keys (toListModel l.buckets).reverse ++ acc := by
rw [fold_cons_apply, keys_eq_map, map_reverse]
theorem foldRev_eq {l : Raw α β} {f : γ → (a : α) → β a → γ} {init : γ} :
Raw.Internal.foldRev f init l =
l.buckets.foldr (fun l acc => l.foldr (fun a b g => f g a b) acc) init := by
simp only [Raw.Internal.foldRev, Raw.Internal.foldRevM, Array.id_run_foldrM, AssocList.foldr]
theorem foldRev_cons_apply {l : Raw α β} {acc : List γ} (f : (a : α) → β a → γ) :
Raw.Internal.foldRev (fun acc k v => f k v :: acc) acc l =
((toListModel l.buckets).map (fun p => f p.1 p.2)) ++ acc := by
rw [foldRev_eq, ← Array.foldr_toList, toListModel]
induction l.buckets.toList generalizing acc with
| nil => simp
| cons x xs ih =>
rw [foldr_cons, ih, AssocList.foldr_apply]
simp
theorem fold_push_apply {l : Raw α β} {acc : Array γ} (f : (a : α) → β a → γ) :
Raw.fold (fun acc k v => acc.push (f k v)) acc l =
acc ++ ((toListModel l.buckets).toArray.map (fun p => f p.1 p.2)) := by
rw [fold_eq, ← Array.foldl_toList, toListModel]
induction l.buckets.toList generalizing acc with
| nil => simp
| cons x xs ih =>
rw [foldl_cons, ih, AssocList.foldl_push_apply]
simp
theorem foldRev_cons {l : Raw α β} {acc : List ((a : α) × β a)} :
Raw.Internal.foldRev (fun acc k v => ⟨k, v⟩ :: acc) acc l = toListModel l.buckets ++ acc := by
simp [foldRev_cons_apply]
theorem foldRev_cons_mk {β : Type v} {l : Raw α (fun _ => β)} {acc : List (α × β)} :
Raw.Internal.foldRev (fun acc k v => (k, v) :: acc) acc l =
(toListModel l.buckets).map (fun ⟨k, v⟩ => (k, v)) ++ acc := by
simp [foldRev_cons_apply]
theorem foldRev_cons_key {l : Raw α β} {acc : List α} :
Raw.Internal.foldRev (fun acc k _ => k :: acc) acc l =
List.keys (toListModel l.buckets) ++ acc := by
rw [foldRev_cons_apply, keys_eq_map]
theorem foldRev_cons_value {β : Type v} {l : Raw α (fun _ => β)} {acc : List β} :
Raw.Internal.foldRev (fun acc _ v => v :: acc) acc l =
List.values (toListModel l.buckets) ++ acc := by
rw [foldRev_cons_apply, values_eq_map]
theorem fold_push {l : Raw α β} {acc : Array ((a : α) × β a)} :
Raw.fold (fun acc k v => acc.push ⟨k, v⟩) acc l = acc ++ (toListModel l.buckets).toArray := by
simp [fold_push_apply]
theorem fold_push_mk {β : Type v} {l : Raw α (fun _ => β)} {acc : Array (α × β)} :
Raw.fold (fun acc k v => acc.push (k, v)) acc l =
acc ++ ((toListModel l.buckets).map (fun ⟨k, v⟩ => (k, v))).toArray := by
simp [fold_push_apply]
theorem fold_push_key {l : Raw α β} {acc : Array α} :
Raw.fold (fun acc k _ => acc.push k) acc l =
acc ++ (List.keys (toListModel l.buckets)).toArray := by
simp [fold_push_apply, keys_eq_map]
theorem foldM_eq_foldlM_toListModel {δ : Type w} {m : Type w → Type w'} [Monad m] [LawfulMonad m]
{f : δ → (a : α) → β a → m δ} {init : δ} {b : Raw α β} :
b.foldM f init = (toListModel b.buckets).foldlM (fun a b => f a b.1 b.2) init := by
simp only [Raw.foldM, ← Array.foldlM_toList, toListModel]
induction b.buckets.toList generalizing init with
| nil => simp
| cons hd tl ih =>
simp only [foldlM_cons, ih, flatMap_cons, foldlM_append]
congr
induction hd generalizing init with
| nil => simp [AssocList.foldlM]
| cons hda hdb tl ih =>
simp only [AssocList.foldlM, AssocList.toList_cons, foldlM_cons]
congr
funext init'
rw [ih]
theorem fold_induction {δ : Type w}
{f : δ → (a : α) → β a → δ} {init : δ} {b : Raw α β} {P : δ → Prop}
(base : P init) (step : ∀ acc a b , P acc → P (f acc a b)) :
P (b.fold f init) := by
simp [Raw.fold, Raw.foldM, ← Array.foldlM_toList]
induction b.buckets.toList generalizing init with
| nil => simp [base]
| cons hd tl ih =>
apply ih
induction hd generalizing init with
| nil => simp [AssocList.foldlM, pure, base]
| cons hda hdb tl ih =>
simp only [AssocList.foldlM, pure_bind]
apply ih
apply step
exact base
theorem fold_eq_foldl_toListModel {l : Raw α β} {f : γ → (a : α) → β a → γ} {init : γ} :
l.fold f init = (toListModel l.buckets).foldl (fun a b => f a b.1 b.2) init := by
simp [Raw.fold, foldM_eq_foldlM_toListModel]
theorem foldRevM_eq_foldrM_toListModel {δ : Type w} {m : Type w → Type w'} [Monad m] [LawfulMonad m]
{f : δ → (a : α) → β a → m δ} {init : δ} {b : Raw α β} :
Raw.Internal.foldRevM f init b =
(toListModel b.buckets).foldrM (fun a b => f b a.1 a.2) init := by
simp only [Raw.Internal.foldRevM, ← Array.foldrM_toList, toListModel]
induction b.buckets.toList generalizing init with
| nil => simp
| cons hd tl ih =>
simp only [foldrM_cons, ih, flatMap_cons, foldrM_append]
congr
funext init'
induction hd generalizing init' with
| nil => simp [AssocList.foldrM]
| cons hda hdb tl ih =>
simp only [AssocList.foldrM, AssocList.toList_cons, foldrM_cons]
congr
rw [ih]
theorem foldRev_eq_foldr_toListModel {l : Raw α β} {f : γ → (a : α) → β a → γ} {init : γ} :
Raw.Internal.foldRev f init l =
(toListModel l.buckets).foldr (fun a b => f b a.1 a.2) init := by
simp [Raw.Internal.foldRev, foldRevM_eq_foldrM_toListModel]
theorem toList_eq_toListModel {m : Raw α β} : m.toList = toListModel m.buckets := by
simp [Raw.toList, foldRev_cons]
theorem Const.toList_eq_toListModel_map {β : Type v} {m : Raw α (fun _ => β)} :
Raw.Const.toList m = (toListModel m.buckets).map (fun ⟨k, v⟩ => ⟨k, v⟩) := by
simp [Raw.Const.toList, foldRev_cons_mk]
theorem toArray_eq_toArray_toListModel {m : Raw α β} : m.toArray = (toListModel m.buckets).toArray := by
simp [Raw.toArray, fold_push]
theorem Const.toArray_eq_toArray_map_toListModel {β : Type v} {m : Raw α (fun _ => β)} :
Raw.Const.toArray m = ((toListModel m.buckets).map (fun ⟨k, v⟩ => (k,v))).toArray := by
simp [Raw.Const.toArray, fold_push_mk]
theorem keys_eq_keys_toListModel {m : Raw α β} :
m.keys = List.keys (toListModel m.buckets) := by
simp [Raw.keys, foldRev_cons_key, keys_eq_map]
theorem values_eq_values_toListModel {β : Type v} {m : Raw α (fun _ => β)} :
m.values = List.values (toListModel m.buckets) := by
simp [Raw.values, foldRev_cons_value, values_eq_map]
theorem keysArray_eq_toArray_keys_toListModel {m : Raw α β} :
m.keysArray = (List.keys (toListModel m.buckets)).toArray := by
simp [Raw.keysArray, fold_push_key]
theorem forM_eq_forM_toListModel {l: Raw α β} {m : Type w → Type w'} [Monad m] [LawfulMonad m]
{f : (a : α) → β a → m PUnit} :
l.forM f = (toListModel l.buckets).forM (fun a => f a.1 a.2) := by
simp only [Raw.forM, Array.forM, ← Array.foldlM_toList, toListModel]
induction l.buckets.toList with
| nil => simp
| cons hd tl ih =>
simp only [foldlM_cons, flatMap_cons, forM_eq_forM, forM_append]
congr
· simp [AssocList.forM]
induction hd with
| nil => simp [AssocList.foldlM]
| cons hda hdb tl ih =>
simp only [AssocList.foldlM, AssocList.toList_cons, forM_cons]
congr
funext x
rw [ih]
· funext x
simp [ih]
theorem forIn_eq_forIn_toListModel {δ : Type w} {l : Raw α β} {m : Type w → Type w'} [Monad m] [LawfulMonad m]
{f : (a : α) → β a → δ → m (ForInStep δ)} {init : δ} :
l.forIn f init = ForIn.forIn (toListModel l.buckets) init (fun a d => f a.1 a.2 d) := by
rw [Raw.forIn, ← Array.forIn_toList, toListModel]
induction l.buckets.toList generalizing init with
| nil => simp
| cons hd tl ih =>
induction hd generalizing init with
| nil => simpa [AssocList.forInStep, AssocList.forInStep.go] using ih
| cons k v tl' ih' =>
simp only [AssocList.forInStep, forIn_cons, AssocList.forInStep.go, LawfulMonad.bind_assoc,
flatMap_cons, AssocList.toList_cons, cons_append]
congr
apply funext
rintro (⟨d⟩|⟨d⟩)
· simp
· simpa using ih'
theorem all_eq_all_toListModel {p : (a: α) → β a → Bool} {m : Raw α β} :
m.all p = (toListModel m.buckets).all (fun x => p x.1 x.2) := by
simp only [Raw.all, ForIn.forIn, Bool.not_eq_true, bind_pure_comp, map_pure, Id.run_bind]
rw [forIn_eq_forIn_toListModel, ← toList_eq_toListModel, forIn_eq_forIn']
induction m.toList with
| nil => simp only [all_nil, forIn'_nil, Id.run_pure]
| cons hd tl ih =>
simp only [forIn'_eq_forIn, List.all_cons]
by_cases h : p hd.fst hd.snd = false
· simp [h]
· simp only [forIn'_eq_forIn] at ih
simp [h, ih]
end Raw
namespace Raw₀
/-! # Raw₀.empty -/
@[simp]
theorem toListModel_buckets_emptyWithCapacity {c} : toListModel (emptyWithCapacity c : Raw₀ α β).1.buckets = [] :=
toListModel_replicate_nil
theorem wfImp_emptyWithCapacity [BEq α] [Hashable α] {c} : Raw.WFImp (emptyWithCapacity c : Raw₀ α β).1 where
buckets_hash_self := by simp [Raw₀.emptyWithCapacity]
size_eq := by simp [Raw₀.emptyWithCapacity]
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
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
private 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 .nil) ((source[i]).foldl (reinsertAux hash) target) := by
rw [expand.go]
simp only [h, dite_true]
private 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]
private 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).flatMap 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 [AssocList.foldl_eq, Array.toList_set]
rw [List.drop_eq_getElem_cons hi, List.flatMap_cons, List.foldl_append,
List.drop_set_of_lt (by omega), Array.getElem_toList]
next i source target hi =>
rw [expand.go_neg hi, List.drop_eq_nil_of_le, flatMap_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)
⟨.replicate (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
@[simp]
theorem size_expandIfNecessary [BEq α] [Hashable α] {m : Raw₀ α β} :
(expandIfNecessary m).val.size = m.val.size := by
rw [expandIfNecessary]
split <;> rfl
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 getEntryₘ_eq_getEntry [BEq α] [PartialEquivBEq α] [Hashable α] [LawfulHashable α] {m : Raw₀ α β} (hm : Raw.WFImp m.1)
{a : α} {h : m.containsₘ a} :
m.getEntryₘ a h = List.getEntry a (toListModel m.1.buckets) (containsₘ_eq_containsKey hm ▸ h) :=
apply_bucket_with_proof hm a AssocList.getEntry List.getEntry AssocList.getEntry_eq getEntry_of_perm getEntry_append_of_containsKey_eq_false
theorem getEntry?ₘ_eq_getEntry? [BEq α] [PartialEquivBEq α] [Hashable α] [LawfulHashable α] {m : Raw₀ α β} (hm : Raw.WFImp m.1)
{a : α} :
m.getEntry?ₘ a = List.getEntry? a (toListModel m.1.buckets) :=
apply_bucket hm AssocList.getEntry?_eq getEntry?_of_perm getEntry?_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 getEntry_eq_getEntry [BEq α] [Hashable α] [PartialEquivBEq α] [LawfulHashable α] {m : Raw₀ α β} (hm : Raw.WFImp m.1)
{a : α} {h : m.contains a} :
m.getEntry a h = List.getEntry a (toListModel m.1.buckets) (contains_eq_containsKey hm ▸ h) := by
rw [getEntry_eq_getEntryₘ, getEntryₘ_eq_getEntry hm]
theorem getEntry?_eq_getEntry? [BEq α] [Hashable α] [PartialEquivBEq α] [LawfulHashable α] {m : Raw₀ α β} (hm : Raw.WFImp m.1)
{a : α} :
m.getEntry? a = List.getEntry? a (toListModel m.1.buckets) := by
rw [getEntry?_eq_getEntry?ₘ, getEntry?ₘ_eq_getEntry? hm]
theorem getEntryDₘ_eq_getEntryD [BEq α] [PartialEquivBEq α] [Hashable α] [LawfulHashable α] {m : Raw₀ α β} (hm : Raw.WFImp m.1)
{a : α} {fallback : (a : α) × β a} :
m.getEntryDₘ a fallback = List.getEntryD a fallback (toListModel m.1.buckets) :=
apply_bucket hm AssocList.getEntryD_eq getEntryD_of_perm getEntryD_append_of_containsKey_eq_false
theorem getEntryD_eq_getEntryD [BEq α] [Hashable α] [PartialEquivBEq α] [LawfulHashable α] {m : Raw₀ α β} (hm : Raw.WFImp m.1)
{a : α} {fallback : (a : α) × β a} :
m.getEntryD a fallback = List.getEntryD a fallback (toListModel m.1.buckets) := by
rw [getEntryD_eq_getEntryDₘ, getEntryDₘ_eq_getEntryD hm]
theorem getEntry!ₘ_eq_getEntry! [BEq α] [PartialEquivBEq α] [Hashable α] [LawfulHashable α] {m : Raw₀ α β} (hm : Raw.WFImp m.1)
{a : α} [Inhabited ((a : α) × β a)] :
m.getEntry!ₘ a = List.getEntry! a (toListModel m.1.buckets) :=
apply_bucket hm AssocList.getEntry!_eq getEntry!_of_perm getEntry!_append_of_containsKey_eq_false
theorem getEntry!_eq_getEntry! [BEq α] [Hashable α] [PartialEquivBEq α] [LawfulHashable α] {m : Raw₀ α β} (hm : Raw.WFImp m.1)
{a : α} [Inhabited ((a : α) × β a)] :
m.getEntry! a = List.getEntry! a (toListModel m.1.buckets) := by
rw [getEntry!_eq_getEntry!ₘ, getEntry!ₘ_eq_getEntry! 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 (by exact 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 (.of_eq 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
/-! # `alter` -/
theorem toListModel_updateBucket_alter [BEq α] [Hashable α] [LawfulBEq α] {m : Raw₀ α β}
(h : Raw.WFImp m.1) {a : α} {f : Option (β a) → Option (β a)} :
Perm (toListModel (updateBucket m.1.buckets m.2 a (AssocList.alter a f)))
(alterKey a f (toListModel m.1.buckets)) := by
exact toListModel_updateBucket h AssocList.toList_alter List.alterKey_of_perm
List.alterKey_append_of_containsKey_right_eq_false
theorem isHashSelf_updateBucket_alter [BEq α] [Hashable α] [LawfulBEq α] {m : Raw₀ α β}
(h : Raw.WFImp m.1) {a : α} {f : Option (β a) → Option (β a)} :
IsHashSelf (updateBucket m.1.buckets m.2 a (AssocList.alter a f)) := by
apply h.buckets_hash_self.updateBucket (fun l p hp => ?_)
rw [AssocList.toList_alter.mem_iff] at hp
by_cases h : p.fst = a
· exact .inr <| congrArg hash h
· rw [mem_alterKey_of_key_ne _ h] at hp
exact .inl <| containsKey_of_mem hp
theorem wfImp_updateBucket_alter [BEq α] [Hashable α] [LawfulBEq α] {m : Raw₀ α β}
(h : Raw.WFImp m.1) {a : α} {f : Option (β a) → Option (β a)} :
Raw.WFImp (withComputedSize <| updateBucket m.1.buckets m.2 a (AssocList.alter a f)) where
buckets_hash_self := isHashSelf_updateBucket_alter h
size_eq := by rw [size_withComputedSize, computeSize_eq, buckets_withComputedSize]
distinct := DistinctKeys.perm (toListModel_updateBucket_alter h) h.distinct.alterKey
theorem isHashSelf_alterₘ [BEq α] [Hashable α] [LawfulBEq α] (m : Raw₀ α β) (h : Raw.WFImp m.1)
(a : α) (f : Option (β a) → Option (β a)) : IsHashSelf (m.alterₘ a f).1.buckets := by
dsimp only [alterₘ, withComputedSize]
split
· exact isHashSelf_updateBucket_alter h
next hc =>
split
· exact h.buckets_hash_self
· refine (wfImp_expandIfNecessary _ (wfImp_consₘ _ h _ _ ?_)).buckets_hash_self
exact Bool.not_eq_true _ ▸ hc
theorem toListModel_alterₘ [BEq α] [Hashable α] [LawfulBEq α] {m : Raw₀ α β} (h : Raw.WFImp m.1)
{a : α} {f : Option (β a) → Option (β a)} :
Perm (toListModel (m.alterₘ a f).1.2) (alterKey a f (toListModel m.1.2)) := by
rw [alterₘ]
split
· exact toListModel_updateBucket_alter h
next hc =>
rw [Bool.not_eq_true, containsₘ_eq_containsKey h] at hc
rw [alterKey, getValueCast?_eq_none hc]
split
next hn =>
simp only [hn]
rw [eraseKey_of_containsKey_eq_false]
exact hc
next hs =>
simp only [hs]
refine Perm.trans (toListModel_expandIfNecessary _) ?_
refine Perm.trans (toListModel_consₘ m h _ _) ?_
rw [insertEntry_of_containsKey_eq_false]
exact hc
theorem toListModel_alter [BEq α] [Hashable α] [LawfulBEq α] {m : Raw₀ α β} (h : Raw.WFImp m.1)
{a : α} {f : Option (β a) → Option (β a)} :
Perm (toListModel (m.alter a f).1.2) (alterKey a f (toListModel m.1.2)) := by
rw [alter_eq_alterₘ]
exact toListModel_alterₘ h
theorem wfImp_alterₘ [BEq α] [Hashable α] [LawfulBEq α] {m : Raw₀ α β} (h : Raw.WFImp m.1) {a : α}
{f : Option (β a) → Option (β a)} : Raw.WFImp (m.alterₘ a f).1 where
buckets_hash_self := isHashSelf_alterₘ m h a f
distinct := DistinctKeys.perm (toListModel_alterₘ h) h.distinct.alterKey
size_eq := by
rw [← Perm.length_eq (toListModel_alterₘ h).symm, alterₘ]
split
next h₁ =>
rw [containsₘ_eq_containsKey h] at h₁
simp only [length_alterKey, h.size_eq, dif_pos h₁]
rw [containsₘ_eq_containsKey (by apply wfImp_updateBucket_alter h)]
simp only [buckets_withComputedSize]
simp only [containsKey_of_perm <| toListModel_updateBucket_alter h]
rw [← getValueCast?_eq_some_getValueCast h₁]
conv => lhs; congr; rw [containsKey_alterKey_self h.distinct]
next h₁ =>
rw [containsₘ_eq_containsKey h] at h₁
rw [alterKey]
rw [getValueCast?_eq_none <| Bool.not_eq_true _ ▸ h₁]
split
next heq =>
rw [heq, h.size_eq, length_eraseKey, if_neg h₁]
next heq =>
rw [heq, size_expandIfNecessary, consₘ, length_insertEntry, if_neg h₁, h.size_eq]
theorem wfImp_alter [BEq α] [Hashable α] [LawfulBEq α] {m : Raw₀ α β}
(h : Raw.WFImp m.1) {a : α} {f : Option (β a) → Option (β a)} : Raw.WFImp (m.alter a f).1 := by
rw [alter_eq_alterₘ]
exact wfImp_alterₘ h
namespace Const
variable {β : Type v}
theorem toListModel_updateBucket_alter [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α]
{m : Raw₀ α (fun _ => β)} (h : Raw.WFImp m.1) {a : α} {f : Option β → Option β} :
Perm (toListModel (updateBucket m.1.buckets m.2 a (AssocList.Const.alter a f)))
(Const.alterKey a f (toListModel m.1.buckets)) := by
exact toListModel_updateBucket h AssocList.Const.toList_alter List.Const.alterKey_of_perm
List.Const.alterKey_append_of_containsKey_right_eq_false
theorem isHashSelf_updateBucket_alter [BEq α] [EquivBEq α] [Hashable α] [LawfulHashable α]
{m : Raw₀ α (fun _ => β)} (h : Raw.WFImp m.1) {a : α} {f : Option β → Option β} :
IsHashSelf (updateBucket m.1.buckets m.2 a (AssocList.Const.alter a f)) := by
apply h.buckets_hash_self.updateBucket (fun l p hp => ?_)
rw [AssocList.Const.toList_alter.mem_iff] at hp
by_cases h : p.fst == a
· exact .inr <| hash_eq h
· rw [Bool.not_eq_true] at h
rw [Const.mem_alterKey_of_key_not_beq _ h] at hp
exact .inl <| containsKey_of_mem hp
theorem wfImp_updateBucket_alter [BEq α] [EquivBEq α] [Hashable α] [LawfulHashable α]
{m : Raw₀ α (fun _ => β)} (h : Raw.WFImp m.1) {a : α} {f : Option β → Option β} :
Raw.WFImp (withComputedSize <| updateBucket m.1.buckets m.2 a (AssocList.Const.alter a f)) where
buckets_hash_self := isHashSelf_updateBucket_alter h
size_eq := by rw [size_withComputedSize, computeSize_eq]; rfl
distinct := DistinctKeys.perm (toListModel_updateBucket_alter h) h.distinct.constAlterKey
theorem isHashSelf_alterₘ [BEq α] [EquivBEq α] [Hashable α] [LawfulHashable α]
(m : Raw₀ α (fun _ => β)) (h : Raw.WFImp m.1) (a : α) (f : Option β → Option β) :
IsHashSelf (Const.alterₘ m a f).1.buckets := by
dsimp only [alterₘ, withComputedSize]
split
· exact isHashSelf_updateBucket_alter h
next hc =>
split
· exact h.buckets_hash_self
· refine (wfImp_expandIfNecessary _ (wfImp_consₘ _ h _ _ ?_)).buckets_hash_self
exact Bool.not_eq_true _ ▸ hc
theorem toListModel_alterₘ [BEq α] [EquivBEq α] [Hashable α] [LawfulHashable α]
{m : Raw₀ α (fun _ => β)} (h : Raw.WFImp m.1) {a : α} {f : Option β → Option β} :
Perm (toListModel (Const.alterₘ m a f).1.2) (Const.alterKey a f (toListModel m.1.2)) := by
rw [Const.alterₘ]
split
· exact toListModel_updateBucket_alter h
next hc =>
rw [Bool.not_eq_true, containsₘ_eq_containsKey h] at hc
rw [Const.alterKey, getValue?_eq_none.mpr hc]
split
next hn =>
simp only [hn]
rw [eraseKey_of_containsKey_eq_false]
exact hc
next hs =>
simp only [hs]
refine Perm.trans (toListModel_expandIfNecessary _) ?_
refine Perm.trans (toListModel_consₘ m h _ _) ?_
rw [insertEntry_of_containsKey_eq_false]
exact hc
theorem toListModel_alter [BEq α] [EquivBEq α] [Hashable α] [LawfulHashable α]
{m : Raw₀ α (fun _ => β)} (h : Raw.WFImp m.1) {a : α} {f : Option β → Option β} :
Perm (toListModel (Const.alter m a f).1.2) (Const.alterKey a f (toListModel m.1.2)) := by
rw [alter_eq_alterₘ]
exact toListModel_alterₘ h
theorem wfImp_alterₘ [BEq α] [EquivBEq α] [Hashable α] [LawfulHashable α] {m : Raw₀ α (fun _ => β)}
(h : Raw.WFImp m.1) {a : α} {f : Option β → Option β} : Raw.WFImp (Const.alterₘ m a f).1 where
buckets_hash_self := isHashSelf_alterₘ m h a f
distinct := DistinctKeys.perm (toListModel_alterₘ h) h.distinct.constAlterKey
size_eq := by
rw [← Perm.length_eq (toListModel_alterₘ h).symm, alterₘ]
split
next h₁ =>
rw [containsₘ_eq_containsKey h] at h₁
simp only [Const.length_alterKey, h.size_eq, dif_pos h₁]
rw [containsₘ_eq_containsKey (by apply wfImp_updateBucket_alter h)]
simp only [buckets_withComputedSize]
simp only [containsKey_of_perm <| toListModel_updateBucket_alter h]
rw [← getValue?_eq_some_getValue h₁]
conv => lhs; congr; rw [Const.containsKey_alterKey_self h.distinct]
next h₁ =>
rw [containsₘ_eq_containsKey h] at h₁
rw [Const.alterKey]
rw [getValue?_eq_none.mpr <| Bool.not_eq_true _ ▸ h₁]
split
next heq =>
rw [heq, h.size_eq, length_eraseKey, if_neg h₁]
next heq =>
rw [heq, size_expandIfNecessary, consₘ, length_insertEntry, if_neg h₁, h.size_eq]
theorem wfImp_alter [BEq α] [EquivBEq α] [Hashable α] [LawfulHashable α] {m : Raw₀ α (fun _ => β)}
(h : Raw.WFImp m.1) {a : α} {f : Option β → Option β} : Raw.WFImp (Const.alter m a f).1 := by
rw [Const.alter_eq_alterₘ]
exact wfImp_alterₘ h
end Const
/-! # `modify` -/
theorem toListModel_modify [BEq α] [Hashable α] [LawfulBEq α] {m : Raw₀ α β} (h : Raw.WFImp m.1)
{a : α} {f : β a → β a} :
Perm (toListModel (m.modify a f).1.2) (modifyKey a f (toListModel m.1.2)) := by
rw [modify_eq_alter, modifyKey_eq_alterKey]
exact toListModel_alter h
theorem wfImp_modifyₘ [BEq α] [Hashable α] [LawfulBEq α] {m : Raw₀ α β}
(h : Raw.WFImp m.1) {a : α} {f : β a → β a} : Raw.WFImp (m.modifyₘ a f).1 := wfImp_alterₘ h
theorem wfImp_modify [BEq α] [Hashable α] [LawfulBEq α] {m : Raw₀ α β} (h : Raw.WFImp m.1) {a : α}
{f : β a → β a} : Raw.WFImp (m.modify a f).1 := by
rw [modify_eq_modifyₘ]
exact wfImp_alterₘ h
namespace Const
variable {β : Type v} {m : Raw₀ α (fun _ => β)}
theorem toListModel_modify [BEq α] [EquivBEq α] [Hashable α] [LawfulHashable α] (h : Raw.WFImp m.1)
{a : α} {f : β → β} :
Perm (toListModel (Const.modify m a f).1.2) (Const.modifyKey a f (toListModel m.1.2)) := by
rw [Const.modify_eq_alter, Const.modifyKey_eq_alterKey]
exact Const.toListModel_alter h
theorem wfImp_modifyₘ [BEq α] [EquivBEq α] [Hashable α] [LawfulHashable α]
(h : Raw.WFImp m.1) {a : α} {f : β → β} : Raw.WFImp (Const.modifyₘ m a f).1 :=
Const.wfImp_alterₘ h
theorem wfImp_modify [BEq α] [EquivBEq α] [Hashable α] [LawfulHashable α]
(h : Raw.WFImp m.1) {a : α} {f : β → β} : Raw.WFImp (Const.modify m a f).1 := by
rw [Const.modify_eq_modifyₘ]
exact wfImp_alterₘ h
end Const
/-! # `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_ite]
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 (.of_eq 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
/-! # `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
/-! # `insertListₘ` -/
theorem toListModel_insertListₘ [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α]
{m : Raw₀ α β} {l : List ((a : α) × β a)} (h : Raw.WFImp m.1) :
Perm (toListModel (insertListₘ m l).1.buckets)
(List.insertList (toListModel m.1.buckets) l) := by
induction l generalizing m with
| nil =>
simp [insertListₘ, List.insertList]
| cons hd tl ih =>
simp only [insertListₘ, List.insertList]
apply Perm.trans (ih (wfImp_insert h))
apply List.insertList_perm_of_perm_first (toListModel_insert h) (wfImp_insert h).distinct
theorem toListModel_eraseListₘ [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α]
{m : Raw₀ α β} {l : List α} (h : Raw.WFImp m.1) :
Perm (toListModel (eraseListₘ m l).1.buckets)
(List.eraseList (toListModel m.1.buckets) l) := by
induction l generalizing m with
| nil =>
simp [eraseListₘ, List.eraseList]
| cons hd tl ih =>
simp only [eraseListₘ, List.eraseList]
apply Perm.trans (ih (wfImp_erase h))
apply List.eraseList_perm_of_perm_first (toListModel_erase h) (wfImp_erase h).distinct
/-! # `insertListₘ` -/
theorem toListModel_insertListIfNewₘ [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α]
{m : Raw₀ α β} {l : List ((a : α) × β a)} (h : Raw.WFImp m.1) :
Perm (toListModel (insertListIfNewₘ m l).1.buckets)
(List.insertListIfNew (toListModel m.1.buckets) l) := by
induction l generalizing m with
| nil =>
simp [insertListIfNewₘ, List.insertListIfNew]
| cons hd tl ih =>
simp only [insertListIfNewₘ, List.insertListIfNew]
apply Perm.trans (ih (wfImp_insertIfNew h))
apply List.insertListIfNew_perm_of_perm_first (toListModel_insertIfNew h) (wfImp_insertIfNew h).distinct
/-! # `unionₘ` -/
theorem insertMany_eq_insertListₘ_toListModel [BEq α] [Hashable α] (m m₂ : Raw₀ α β) :
insertMany m m₂.1 = insertListₘ m (toListModel m₂.1.buckets) := by
simp only [insertMany, bind_pure_comp, map_pure, bind_pure]
simp only [ForIn.forIn]
simp only [Raw.forIn_eq_forIn_toListModel, forIn_pure_yield_eq_foldl, Id.run_pure]
generalize toListModel m₂.val.buckets = l
suffices ∀ (t : { m' // ∀ (P : Raw₀ α β → Prop),
(∀ {m'' : Raw₀ α β} {a : α} {b : β a}, P m'' → P (m''.insert a b)) → P m → P m' }),
(List.foldl (fun m' p => ⟨m'.val.insert p.1 p.2, fun P h₁ h₂ => h₁ (m'.2 _ h₁ h₂)⟩) t l).val =
t.val.insertListₘ l from this _
intro t
induction l generalizing m with
| nil => simp [insertListₘ]
| cons hd tl ih =>
simp only [List.foldl_cons, insertListₘ]
apply ih
theorem insertMany_array_eq_insertMany_toList [BEq α] [Hashable α] (m : Raw₀ α β) (a : Array ((k : α) × (β k))) :
insertMany m a = insertMany m a.toList := by
simp only [insertMany, bind_pure_comp, map_pure, bind_pure, ← Array.forIn_toList, forIn_pure_yield_eq_foldl, Array.foldl_toList, Id.run_pure]
theorem Const.insertMany_array_eq_insertMany_toList [BEq α] [Hashable α] {β : Type v} (m : Raw₀ α fun _ => β) (a : Array (α × β)) :
Const.insertMany m a = Const.insertMany m a.toList := by
simp only [insertMany, bind_pure_comp, map_pure, bind_pure, ← Array.forIn_toList, forIn_pure_yield_eq_foldl, Array.foldl_toList, Id.run_pure]
theorem Const.insertManyIfNewUnit_array_eq_insertManyIfNewUnit_toList [BEq α] [Hashable α] (m : Raw₀ α fun _ => Unit) (a : Array α) :
Const.insertManyIfNewUnit m a = Const.insertManyIfNewUnit m a.toList := by
simp only [insertManyIfNewUnit, bind_pure_comp, map_pure, bind_pure, ← Array.forIn_toList, forIn_pure_yield_eq_foldl, Array.foldl_toList, Id.run_pure]
theorem insertManyIfNew_eq_insertListIfNewₘ_toListModel [BEq α] [Hashable α] (m m₂ : Raw₀ α β) :
insertManyIfNew m m₂.1 = insertListIfNewₘ m (toListModel m₂.1.buckets) := by
simp only [insertManyIfNew, bind_pure_comp, map_pure, bind_pure]
simp only [ForIn.forIn]
simp only [Raw.forIn_eq_forIn_toListModel, forIn_pure_yield_eq_foldl, Id.run_pure]
generalize toListModel m₂.val.buckets = l
suffices ∀ (t : { m' // ∀ (P : Raw₀ α β → Prop),
(∀ {m'' : Raw₀ α β} {a : α} {b : β a}, P m'' → P (m''.insertIfNew a b)) → P m → P m' }),
(List.foldl (fun m' p => ⟨m'.val.insertIfNew p.1 p.2, fun P h₁ h₂ => h₁ (m'.2 _ h₁ h₂)⟩) t l).val =
t.val.insertListIfNewₘ l from this _
intro t
induction l generalizing m with
| nil => simp [insertListIfNewₘ]
| cons hd tl ih =>
simp only [List.foldl_cons]
apply ih
theorem union_eq_unionₘ [BEq α] [Hashable α] (m₁ m₂ : Raw₀ α β) :
union m₁ m₂ = unionₘ m₁ m₂ := by
rw [union, unionₘ]
split
· rw [insertManyIfNew_eq_insertListIfNewₘ_toListModel]
· rw [insertMany_eq_insertListₘ_toListModel]
theorem toListModel_unionₘ [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α]
{m₁ m₂ : Raw₀ α β} (h₁ : Raw.WFImp m₁.1) (h₂ : Raw.WFImp m₂.1) :
Perm (toListModel (unionₘ m₁ m₂).1.buckets)
(List.insertList (toListModel m₁.1.buckets) (toListModel m₂.1.buckets)) := by
refine Perm.trans ?_ (Perm.symm (List.insertList_perm_insertSmallerList h₁.distinct h₂.distinct))
rw [unionₘ, insertSmallerList, h₁.size_eq, h₂.size_eq]
split
· exact toListModel_insertListIfNewₘ ‹_›
· exact toListModel_insertListₘ ‹_›
theorem wfImp_inter [BEq α] [EquivBEq α] [Hashable α] [LawfulHashable α]
{m₁ m₂ : Raw α β} {h₁ : 0 < m₁.buckets.size} {h₂ : 0 < m₂.buckets.size} (wh₁ : Raw.WFImp m₁) :
Raw.WFImp (Raw₀.inter ⟨m₁, h₁⟩ ⟨m₂, h₂⟩).val := by
rw [inter]
split
· apply wfImp_filter wh₁
· rw [interSmaller]
apply @Raw.fold_induction _ β _ (fun sofar k x => interSmallerFn ⟨m₁, h₁⟩ sofar k) emptyWithCapacity m₂ (Raw.WFImp ·.val) wfImp_emptyWithCapacity
intro acc a b wf
rw [interSmallerFn]
split
· apply wfImp_insert wf
· apply wf
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₂ with
| wf _ h => apply h
| emptyWithCapacity₀ => exact Raw₀.wfImp_emptyWithCapacity
| insert₀ _ h => exact Raw₀.wfImp_insert (by apply h)
| containsThenInsert₀ _ h => exact Raw₀.wfImp_containsThenInsert (by apply h)
| containsThenInsertIfNew₀ _ h => exact Raw₀.wfImp_containsThenInsertIfNew (by apply h)
| erase₀ _ h => exact Raw₀.wfImp_erase (by apply h)
| insertIfNew₀ _ h => exact Raw₀.wfImp_insertIfNew (by apply h)
| getThenInsertIfNew?₀ _ h => exact Raw₀.wfImp_getThenInsertIfNew? (by apply h)
| filter₀ _ h => exact Raw₀.wfImp_filter (by apply h)
| constGetThenInsertIfNew?₀ _ h => exact Raw₀.Const.wfImp_getThenInsertIfNew? (by apply h)
| modify₀ _ h => exact Raw₀.wfImp_modify (by apply h)
| constModify₀ _ h => exact Raw₀.Const.wfImp_modify (by apply h)
| alter₀ _ h => exact Raw₀.wfImp_alter (by apply h)
| constAlter₀ _ h => exact Raw₀.Const.wfImp_alter (by apply h)
| inter₀ _ _ h _ => exact Raw₀.wfImp_inter (by apply h)
end Raw
namespace Raw₀
/-! # `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_iff] 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
theorem wf_filterMap₀ [BEq α] [Hashable α] {m : Raw₀ α β} (h : m.1.WF)
{f : (a : α) → β a → Option (δ a)} : (m.filterMap f).1.WF :=
.wf (Raw₀.filterMap f ⟨m, h.size_buckets_pos⟩).2 (wfImp_filterMap (Raw.WF.out h))
theorem filterMap_eq_filter {m : Raw₀ α β} {f : (a : α) → β a → Bool} :
m.filterMap (fun k => Option.guard (fun v => f k v)) = m.filter f := by
rw [filter_eq_filterₘ, filterMap_eq_filterMapₘ, filterₘ, filterMapₘ]
simp only [AssocList.filterMap_eq_filter]
theorem filterMap_eq_map [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α]
{γ : α → Type w} (m : Raw₀ α β) (f : (a : α) → β a → γ a) (h : m.1.WF) :
m.filterMap (fun k v => Option.some (f k v)) = m.map f := by
rw [map_eq_mapₘ, filterMap_eq_filterMapₘ, mapₘ, filterMapₘ]
simp only [AssocList.filterMap_eq_map, withComputedSize]
simp only [computeSize_eq, Subtype.mk.injEq, Raw.mk.injEq, and_true]
rw [(toListModel_updateAllBuckets (f := fun a => a.map f)
AssocList.toList_map (by simp)).length_eq]
rw [(Raw.WF.out h).size_eq, List.length_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⟩) :=
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
theorem wf_map₀ [BEq α] [Hashable α] {m : Raw₀ α β} (h : m.1.WF) {f : (a : α) → β a → δ a} :
(m.map f).1.WF :=
.wf (Raw₀.map f ⟨m, h.size_buckets_pos⟩).2 (Raw₀.wfImp_map (Raw.WF.out h))
/-! # `insertMany` -/
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 toListModel_insertMany_list [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α]
{m : Raw₀ α β} {l : List ((a : α) × (β a))} (h : Raw.WFImp m.1) :
Perm (toListModel (insertMany m l).1.1.buckets)
(List.insertList (toListModel m.1.buckets) l) := by
rw [insertMany_eq_insertListₘ]
apply toListModel_insertListₘ
exact h
/-! # `eraseMany` -/
theorem WF.eraseManyEntries [BEq α] [Hashable α] {ρ : Type w} [ForIn Id ρ ((a : α) × β a)] {m : Raw α β}
{l : ρ} (h : m.WF) : (m.eraseManyEntries l).WF := by
simpa [Raw.eraseManyEntries, h.size_buckets_pos] using
(Raw₀.eraseManyEntries ⟨m, h.size_buckets_pos⟩ l).2 _ Raw.WF.erase₀ h
theorem wf_insertMany₀ [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {ρ : Type w}
[ForIn Id ρ ((a : α) × β a)] {m : Raw α β} {h : 0 < m.buckets.size} {l : ρ} (h' : m.WF) :
(Raw₀.insertMany ⟨m, h⟩ l).1.1.WF :=
(Raw₀.insertMany ⟨m, h⟩ l).2 _ Raw.WF.insert₀ h'
theorem wf_eraseMany₀ [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {ρ : Type w}
[ForIn Id ρ ((a : α) × β a)] {m : Raw α β} {h : 0 < m.buckets.size} {l : ρ} (h' : m.WF) :
(eraseManyEntries ⟨m, h⟩ l).1.1.WF :=
(eraseManyEntries ⟨m, h⟩ l).2 _ Raw.WF.erase₀ h'
theorem eraseMany_eq_eraseListₘ_toListModel [BEq α] [Hashable α] (m m₂ : Raw₀ α β) :
eraseManyEntries m m₂.1 = eraseListₘ m ((toListModel m₂.1.buckets).map (·.1)) := by
simp only [eraseManyEntries, bind_pure_comp, map_pure, bind_pure]
simp only [ForIn.forIn]
simp only [Raw.forIn_eq_forIn_toListModel, forIn_pure_yield_eq_foldl, Id.run_pure]
generalize toListModel m₂.val.buckets = l
suffices ∀ (t : { m' // ∀ (P : Raw₀ α β → Prop),
(∀ {m'' : Raw₀ α β} {a : α}, P m'' → P (m''.erase a)) → P m → P m' }),
(List.foldl (fun m' p => ⟨m'.val.erase p.1, fun P h₁ h₂ => h₁ (m'.2 _ h₁ h₂)⟩) t l).val =
t.val.eraseListₘ (l.map (·.1)) from this _
intro t
induction l generalizing m with
| nil => simp [eraseListₘ]
| cons hd tl ih =>
simp only [List.foldl_cons]
apply ih
theorem toListModel_diffₘ [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α]
{m₁ m₂ : Raw₀ α β} (h₁ : Raw.WFImp m₁.1) (h₂ : Raw.WFImp m₂.1) :
Perm (toListModel (diffₘ m₁ m₂).1.buckets)
(List.filter (fun k => !List.contains ((toListModel m₂.1.buckets).map Sigma.fst) k.fst) (toListModel m₁.1.buckets)) := by
rw [diffₘ]
split
· apply Perm.trans
· apply toListModel_filterₘ
· conv =>
lhs
lhs
ext p
congr
rw [containsₘ_eq_containsKey h₂]
rw [containsKey_eq_contains_map_fst]
· rw [eraseManyEntries_eq_eraseListₘ]
apply Perm.trans (toListModel_eraseListₘ h₁)
· apply eraseList_perm_filter_not_contains
· exact h₁.distinct
theorem diff_eq_diffₘ [BEq α] [Hashable α] (m₁ m₂ : Raw₀ α β) :
diff m₁ m₂ = diffₘ m₁ m₂ := by
rw [diff, diffₘ]
split
· rw [filter_eq_filterₘ]
congr
· rw [eraseMany_eq_eraseListₘ_toListModel]
rw [eraseManyEntries_eq_eraseListₘ]
theorem toListModel_diff [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {m₁ m₂ : Raw₀ α β}
(h₁ : Raw.WFImp m₁.1) (h₂ : Raw.WFImp m₂.1) :
Perm (toListModel (m₁.diff m₂).1.buckets)
(List.filter (fun k => !List.contains ((toListModel m₂.1.buckets).map Sigma.fst) k.fst) (toListModel m₁.1.buckets)) := by
rw [diff_eq_diffₘ]
exact toListModel_diffₘ h₁ h₂
theorem wf_diff₀ [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α]
{m₁ m₂ : Raw α β} {h₁ : 0 < m₁.buckets.size} {h₂ : 0 < m₂.buckets.size} (h'₁ : m₁.WF) :
(Raw₀.diff ⟨m₁, h₁⟩ ⟨m₂, h₂⟩).1.WF := by
rw [diff]
split
· apply Raw.WF.filter₀ h'₁
· exact wf_eraseMany₀ ‹_›
/-! # `insertManyIfNew` -/
theorem wfImp_insertManyIfNew [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {ρ : Type w}
[ForIn Id ρ ((a : α) × β a)] {m : Raw₀ α β} {l : ρ} (h : Raw.WFImp m.1) :
Raw.WFImp (m.insertManyIfNew l).1.1 :=
Raw.WF.out ((m.insertManyIfNew l).2 _ Raw.WF.insertIfNew₀ (.wf m.2 h))
theorem wf_insertManyIfNew₀ [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {ρ : Type w}
[ForIn Id ρ ((a : α) × β a)] {m : Raw α β} {h : 0 < m.buckets.size} {l : ρ} (h' : m.WF) :
(Raw₀.insertManyIfNew ⟨m, h⟩ l).1.1.WF :=
(Raw₀.insertManyIfNew ⟨m, h⟩ l).2 _ Raw.WF.insertIfNew₀ h'
theorem toListModel_insertManyIfNew_list [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α]
{m : Raw₀ α β} {l : List ((a : α) × (β a))} (h : Raw.WFImp m.1) :
Perm (toListModel (insertManyIfNew m l).1.1.buckets)
(List.insertListIfNew (toListModel m.1.buckets) l) := by
rw [insertManyIfNew_eq_insertListIfNewₘ]
apply toListModel_insertListIfNewₘ
exact h
/-! # `union` -/
theorem wf_union₀ [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α]
{m₁ m₂ : Raw α β} {h₁ : 0 < m₁.buckets.size} {h₂ : 0 < m₂.buckets.size} (h'₁ : m₁.WF)
(h'₂ : m₂.WF) :
(Raw₀.union ⟨m₁, h₁⟩ ⟨m₂, h₂⟩).1.WF := by
rw [union]
split
· exact wf_insertManyIfNew₀ ‹_›
· exact wf_insertMany₀ ‹_›
theorem toListModel_union [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α] {m₁ m₂ : Raw₀ α β}
(h₁ : Raw.WFImp m₁.1) (h₂ : Raw.WFImp m₂.1) :
Perm (toListModel (m₁.union m₂).1.buckets)
(List.insertList (toListModel m₁.1.buckets) (toListModel m₂.1.buckets)) := by
rw [union_eq_unionₘ]
exact toListModel_unionₘ h₁ h₂
/-! # `inter` -/
theorem wfImp_interSmallerFnₘ [BEq α] [EquivBEq α] [Hashable α] [LawfulHashable α] (m₁ : Raw₀ α β) (m₂ : Raw₀ α β)
(hm₂ : Raw.WFImp m₂.1) (k : α) : Raw.WFImp (m₁.interSmallerFnₘ m₂ k).1 := by
rw [interSmallerFnₘ]
split
· exact wfImp_insertₘ hm₂
· exact hm₂
/-- Internal implementation detail of the hash map -/
def interSmallerₘ [BEq α] [Hashable α] (m₁ : Raw₀ α β) (m₂ : Raw α β) : Raw₀ α β :=
m₂.fold (fun sofar k _ => interSmallerFnₘ m₁ sofar k) emptyWithCapacity
theorem interSmaller_eq_interSmallerₘ [BEq α] [Hashable α] (m₁ : Raw₀ α β) (m₂ : Raw α β) :
m₁.interSmaller m₂ = m₁.interSmallerₘ m₂ := by
rw [interSmaller, interSmallerₘ]
simp only [interSmallerFn_eq_interSmallerFnₘ]
theorem foldl_perm_cong [BEq α] {init₁ init₂ : List ((a : α) × β a)} {l : List ((a : α) × β a)}
{f : List ((a : α) × β a) → ((a : α) × β a) → List ((a : α) × β a)} (h₁ : Perm init₁ init₂)
(h₂ : ∀ h l₁ l₂, (w : DistinctKeys l₁) → Perm l₁ l₂ → Perm (f l₁ h) (f l₂ h) ∧ DistinctKeys (f l₁ h))
(h₃ : DistinctKeys init₁)
: Perm (List.foldl f init₁ l) (List.foldl f init₂ l) := by
induction l generalizing init₁ init₂
case nil =>
simp only [foldl_nil, h₁]
case cons h t ih =>
simp only [foldl_cons]
apply ih
· exact (h₂ h init₁ init₂ h₃ h₁).1
· exact (h₂ h init₁ init₂ h₃ h₁).2
theorem toListModel_interSmallerFnₘ [BEq α] [EquivBEq α] [Hashable α] [LawfulHashable α] (m sofar : Raw₀ α β)
(l : List ((a : α) × β a))
(hm : Raw.WFImp m.1) (hs : Raw.WFImp sofar.1) (k : α) (hml : toListModel sofar.1.buckets ~ l) :
Perm (toListModel ((interSmallerFnₘ m sofar k).1.buckets))
(List.interSmallerFn (toListModel m.1.buckets) l k) := by
rw [interSmallerFnₘ, getEntry?ₘ_eq_getEntry? hm, List.interSmallerFn]
split
· simpa [*] using (toListModel_insertₘ hs).trans (List.insertEntry_of_perm hs.distinct hml)
· simp [*]
theorem toListModel_interSmallerₘ [BEq α] [EquivBEq α] [Hashable α] [LawfulHashable α]
(m₁ : Raw₀ α β) (m₂ : Raw α β) (hm₁ : Raw.WFImp m₁.1) :
toListModel (m₁.interSmallerₘ m₂).1.buckets ~
List.interSmaller (toListModel m₁.1.buckets) (toListModel m₂.buckets) := by
rw [interSmallerₘ, Raw.fold_eq_foldl_toListModel, List.interSmaller]
generalize toListModel m₂.buckets = l
suffices ∀ m l', Raw.WFImp m.1 → toListModel m.1.buckets ~ l' → toListModel (foldl (fun a b => m₁.interSmallerFnₘ a b.fst) m l).val.buckets ~
foldl (fun sofar kv => List.interSmallerFn (toListModel m₁.val.buckets) sofar kv.fst) l' l by
simpa using this emptyWithCapacity [] wfImp_emptyWithCapacity (by simp)
intro m l' hm hml'
induction l generalizing m l' with
| nil => simpa
| cons ht tl ih =>
rw [List.foldl_cons, List.foldl_cons]
exact ih _ _ (wfImp_interSmallerFnₘ _ _ hm _) (toListModel_interSmallerFnₘ _ _ _ hm₁ hm _ hml')
theorem toListModel_inter [BEq α] [EquivBEq α] [Hashable α] [LawfulHashable α] (m₁ m₂ : Raw₀ α β) (hm₁ : Raw.WFImp m₁.1) (hm₂ : Raw.WFImp m₂.1) :
Perm (toListModel (m₁.inter m₂).1.buckets) ((toListModel m₁.1.buckets).filter fun p => containsKey p.1 (toListModel m₂.1.buckets) ) := by
simp [inter]
split
· rw [filter_eq_filterₘ]
simp only [contains_eq_containsKey hm₂]
exact toListModel_filterₘ
· rw [interSmaller_eq_interSmallerₘ]
exact Perm.trans (toListModel_interSmallerₘ _ _ hm₁)
(interSmaller_perm_filter _ _ hm₁.distinct)
/-! # `Const.insertListₘ` -/
theorem Const.toListModel_insertListₘ {β : Type v} [BEq α] [Hashable α] [EquivBEq α]
[LawfulHashable α] {m : Raw₀ α (fun _ => β)} {l : List (α × β)} (h : Raw.WFImp m.1) :
Perm (toListModel (Const.insertListₘ m l).1.buckets)
(insertListConst (toListModel m.1.buckets) l) := by
induction l generalizing m with
| nil => simp [Const.insertListₘ, insertListConst, insertList]
| cons hd tl ih =>
simp only [Const.insertListₘ, insertListConst]
apply Perm.trans (ih (wfImp_insert h))
unfold insertListConst
apply List.insertList_perm_of_perm_first (toListModel_insert h) (wfImp_insert h).distinct
/-! # `Const.insertMany` -/
theorem Const.toListModel_insertMany_list {β : Type v} [BEq α] [Hashable α] [EquivBEq α]
[LawfulHashable α] {m : Raw₀ α (fun _ => β)} {l : List (α × β)} (h : Raw.WFImp m.1) :
Perm (toListModel (Const.insertMany m l).1.1.buckets)
(insertListConst (toListModel m.1.buckets) l) := by
rw [Const.insertMany_eq_insertListₘ]
apply toListModel_insertListₘ 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.wf_insertMany₀ {β : Type v} [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α]
{ρ : Type w} [ForIn Id ρ (α × β)] {m : Raw α (fun _ => β)} {h : 0 < m.buckets.size}
{l : ρ} (h' : m.WF) : (Const.insertMany ⟨m, h⟩ l).1.1.WF :=
(Raw₀.Const.insertMany ⟨m, h⟩ l).2 _ Raw.WF.insert₀ h'
/-! # `Const.insertListIfNewUnitₘ` -/
theorem Const.toListModel_insertListIfNewUnitₘ [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α]
{m : Raw₀ α (fun _ => Unit)} {l : List α} (h : Raw.WFImp m.1) :
Perm (toListModel (Const.insertListIfNewUnitₘ m l).1.buckets)
(List.insertListIfNewUnit (toListModel m.1.buckets) l) := by
induction l generalizing m with
| nil => simp [insertListIfNewUnitₘ, List.insertListIfNewUnit]
| cons hd tl ih =>
simp only [insertListIfNewUnitₘ, insertListIfNewUnit]
apply Perm.trans (ih (wfImp_insertIfNew h))
apply List.insertListIfNewUnit_perm_of_perm_first (toListModel_insertIfNew h)
apply (wfImp_insertIfNew h).distinct
/-! # `Const.insertManyIfNewUnit` -/
theorem Const.toListModel_insertManyIfNewUnit_list [BEq α] [Hashable α] [EquivBEq α]
[LawfulHashable α] {m : Raw₀ α (fun _ => Unit)} {l : List α} (h : Raw.WFImp m.1) :
Perm (toListModel (Const.insertManyIfNewUnit m l).1.1.buckets)
(List.insertListIfNewUnit (toListModel m.1.buckets) l) := by
rw [Const.insertManyIfNewUnit_eq_insertListIfNewUnitₘ]
apply toListModel_insertListIfNewUnitₘ h
theorem Const.wfImp_insertManyIfNewUnit [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α]
{ρ : Type w} [ForIn Id ρ α] {m : Raw₀ α (fun _ => Unit)} {l : ρ} (h : Raw.WFImp m.1) :
Raw.WFImp (Const.insertManyIfNewUnit m l).1.1 :=
Raw.WF.out ((Const.insertManyIfNewUnit m l).2 _ Raw.WF.insertIfNew₀ (.wf m.2 h))
theorem Const.wf_insertManyIfNewUnit₀ [BEq α] [Hashable α] [EquivBEq α] [LawfulHashable α]
{ρ : Type w} [ForIn Id ρ α] {m : Raw α (fun _ => Unit)} {h : 0 < m.buckets.size}
{l : ρ} (h' : m.WF) : (Const.insertManyIfNewUnit ⟨m, h⟩ l).1.1.WF :=
(Raw₀.Const.insertManyIfNewUnit ⟨m, h⟩ l).2 _ Raw.WF.insertIfNew₀ h'
theorem beq_eq_beqModel [BEq α] [LawfulBEq α] [Hashable α] [∀ k, BEq (β k)] {m₁ m₂ : Raw₀ α β} (h₁ : Raw.WFImp m₁.1) (h₂ : Raw.WFImp m₂.1) :
beq m₁ m₂ = beqModel (toListModel m₁.1.buckets) (toListModel m₂.1.buckets) := by
simp [beq, beqModel, Raw.size_eq_length h₁, Raw.size_eq_length h₂, Raw.all_eq_all_toListModel,
get?_eq_getValueCast? h₂]
theorem Const.beq_eq_beqModel {β : Type v} [BEq α] [PartialEquivBEq α] [Hashable α] [LawfulHashable α] [BEq β] {m₁ m₂ : Raw₀ α (fun _ => β)} (h₁ : Raw.WFImp m₁.1) (h₂ : Raw.WFImp m₂.1) :
beq m₁ m₂ = Const.beqModel (toListModel m₁.1.buckets) (toListModel m₂.1.buckets) := by
simp [beq, Const.beqModel, Raw.size_eq_length h₁, Raw.size_eq_length h₂, Raw.all_eq_all_toListModel, get?_eq_getValue? h₂]
end Raw₀