Hash map lemmas

This module contains lemmas about Std.Data.HashMap. Most of the lemmas require EquivBEq α and LawfulHashable α for the key type α. The easiest way to obtain these instances is to provide an instance of LawfulBEq α.

@[simp]

theorem Std.HashMap.isEmpty_emptyWithCapacity {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {c : Nat} : (emptyWithCapacity c).isEmpty = true

@[simp]

theorem Std.HashMap.isEmpty_empty {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} : ∅.isEmpty = true

@[reducible, inline, deprecated Std.HashMap.isEmpty_empty (since := "2025-03-12")]

abbrev Std.HashMap.isEmpty_emptyc {α : Type u_1} {β : Type u_2} {x✝ : BEq α} {x✝¹ : Hashable α} : ∅.isEmpty = true

Equations

• @Std.HashMap.isEmpty_emptyc = @Std.HashMap.isEmpty_empty

@[simp]

theorem Std.HashMap.isEmpty_insert {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {v : β} : (m.insert k v).isEmpty = false

theorem Std.HashMap.mem_iff_contains {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {a : α} : a ∈ m ↔ m.contains a = true

@[simp]

theorem Std.HashMap.contains_iff_mem {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {a : α} : m.contains a = true ↔ a ∈ m

theorem Std.HashMap.contains_congr {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a b : α} (hab : (a == b) = true) : m.contains a = m.contains b

theorem Std.HashMap.mem_congr {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a b : α} (hab : (a == b) = true) : a ∈ m ↔ b ∈ m

@[simp]

theorem Std.HashMap.contains_emptyWithCapacity {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {a : α} {c : Nat} : (emptyWithCapacity c).contains a = false

@[simp]

theorem Std.HashMap.not_mem_emptyWithCapacity {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {a : α} {c : Nat} : ¬a ∈ emptyWithCapacity c

@[simp]

theorem Std.HashMap.contains_empty {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {a : α} : ∅.contains a = false

@[reducible, inline, deprecated Std.HashMap.contains_empty (since := "2025-03-12")]

abbrev Std.HashMap.contains_emptyc {α : Type u_1} {β : Type u_2} {x✝ : BEq α} {x✝¹ : Hashable α} {a : α} : ∅.contains a = false

Equations

• @Std.HashMap.contains_emptyc = @Std.HashMap.contains_empty

@[simp]

theorem Std.HashMap.not_mem_empty {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {a : α} : ¬a ∈ ∅

@[reducible, inline, deprecated Std.HashMap.not_mem_empty (since := "2025-03-12")]

abbrev Std.HashMap.not_mem_emptyc {α : Type u_1} {β : Type u_2} {x✝ : BEq α} {x✝¹ : Hashable α} {a : α} : ¬a ∈ ∅

Equations

• @Std.HashMap.not_mem_emptyc = @Std.HashMap.not_mem_empty

theorem Std.HashMap.contains_of_isEmpty {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a : α} : m.isEmpty = true → m.contains a = false

theorem Std.HashMap.not_mem_of_isEmpty {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a : α} : m.isEmpty = true → ¬a ∈ m

theorem Std.HashMap.isEmpty_eq_false_iff_exists_contains_eq_true {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] : m.isEmpty = false ↔ ∃ (a : α), m.contains a = true

theorem Std.HashMap.isEmpty_eq_false_iff_exists_mem {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] : m.isEmpty = false ↔ ∃ (a : α), a ∈ m

theorem Std.HashMap.isEmpty_iff_forall_contains {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] : m.isEmpty = true ↔ ∀ (a : α), m.contains a = false

theorem Std.HashMap.isEmpty_iff_forall_not_mem {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] : m.isEmpty = true ↔ ∀ (a : α), ¬a ∈ m

@[simp]

theorem Std.HashMap.insert_eq_insert {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {p : α × β} : Insert.insert p m = m.insert p.fst p.snd

@[simp]

theorem Std.HashMap.singleton_eq_insert {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {p : α × β} : {p} = ∅.insert p.fst p.snd

@[simp]

theorem Std.HashMap.contains_insert {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k a : α} {v : β} : (m.insert k v).contains a = (k == a || m.contains a)

@[simp]

theorem Std.HashMap.mem_insert {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k a : α} {v : β} : a ∈ m.insert k v ↔ (k == a) = true ∨ a ∈ m

theorem Std.HashMap.contains_of_contains_insert {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k a : α} {v : β} : (m.insert k v).contains a = true → (k == a) = false → m.contains a = true

theorem Std.HashMap.mem_of_mem_insert {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k a : α} {v : β} : a ∈ m.insert k v → (k == a) = false → a ∈ m

theorem Std.HashMap.contains_insert_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {v : β} : (m.insert k v).contains k = true

theorem Std.HashMap.mem_insert_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {v : β} : k ∈ m.insert k v

@[simp]

theorem Std.HashMap.size_emptyWithCapacity {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {c : Nat} : (emptyWithCapacity c).size = 0

@[simp]

theorem Std.HashMap.size_empty {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} : ∅.size = 0

@[reducible, inline, deprecated Std.HashMap.size_empty (since := "2025-03-12")]

abbrev Std.HashMap.size_emptyc {α : Type u_1} {β : Type u_2} {x✝ : BEq α} {x✝¹ : Hashable α} : ∅.size = 0

Equations

• @Std.HashMap.size_emptyc = @Std.HashMap.size_empty

theorem Std.HashMap.isEmpty_eq_size_eq_zero {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} : m.isEmpty = (m.size == 0)

theorem Std.HashMap.size_insert {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {v : β} : (m.insert k v).size = if k ∈ m then m.size else m.size + 1

theorem Std.HashMap.size_le_size_insert {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {v : β} : m.size ≤ (m.insert k v).size

theorem Std.HashMap.size_insert_le {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {v : β} : (m.insert k v).size ≤ m.size + 1

@[simp]

theorem Std.HashMap.erase_emptyWithCapacity {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {a : α} {c : Nat} : (emptyWithCapacity c).erase a = emptyWithCapacity c

@[simp]

theorem Std.HashMap.erase_empty {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {a : α} : ∅.erase a = ∅

@[reducible, inline, deprecated Std.HashMap.erase_empty (since := "2025-03-12")]

abbrev Std.HashMap.erase_emptyc {α : Type u_1} {β : Type u_2} {x✝ : BEq α} {x✝¹ : Hashable α} {a : α} : ∅.erase a = ∅

Equations

• @Std.HashMap.erase_emptyc = @Std.HashMap.erase_empty

@[simp]

theorem Std.HashMap.isEmpty_erase {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} : (m.erase k).isEmpty = (m.isEmpty || m.size == 1 && m.contains k)

@[simp]

theorem Std.HashMap.contains_erase {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k a : α} : (m.erase k).contains a = (!k == a && m.contains a)

@[simp]

theorem Std.HashMap.mem_erase {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k a : α} : a ∈ m.erase k ↔ (k == a) = false ∧ a ∈ m

theorem Std.HashMap.contains_of_contains_erase {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k a : α} : (m.erase k).contains a = true → m.contains a = true

theorem Std.HashMap.mem_of_mem_erase {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k a : α} : a ∈ m.erase k → a ∈ m

theorem Std.HashMap.size_erase {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} : (m.erase k).size = if k ∈ m then m.size - 1 else m.size

theorem Std.HashMap.size_erase_le {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} : (m.erase k).size ≤ m.size

theorem Std.HashMap.size_le_size_erase {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} : m.size ≤ (m.erase k).size + 1

@[simp]

theorem Std.HashMap.containsThenInsert_fst {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {k : α} {v : β} : (m.containsThenInsert k v).fst = m.contains k

@[simp]

theorem Std.HashMap.containsThenInsert_snd {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {k : α} {v : β} : (m.containsThenInsert k v).snd = m.insert k v

@[simp]

theorem Std.HashMap.containsThenInsertIfNew_fst {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {k : α} {v : β} : (m.containsThenInsertIfNew k v).fst = m.contains k

@[simp]

theorem Std.HashMap.containsThenInsertIfNew_snd {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {k : α} {v : β} : (m.containsThenInsertIfNew k v).snd = m.insertIfNew k v

@[simp]

theorem Std.HashMap.get_eq_getElem {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {a : α} {h : a ∈ m} : m.get a h = m[a]

@[simp]

theorem Std.HashMap.get?_eq_getElem? {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {a : α} : m.get? a = m[a]?

@[simp]

theorem Std.HashMap.get!_eq_getElem! {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [Inhabited β] {a : α} : m.get! a = m[a]!

@[simp]

theorem Std.HashMap.getElem?_emptyWithCapacity {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {a : α} {c : Nat} : (emptyWithCapacity c)[a]? = none

@[simp]

theorem Std.HashMap.getElem?_empty {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {a : α} : ∅[a]? = none

@[reducible, inline, deprecated Std.HashMap.getElem?_empty (since := "2025-03-12")]

abbrev Std.HashMap.getElem?_emptyc {α : Type u_1} {β : Type u_2} {x✝ : BEq α} {x✝¹ : Hashable α} {a : α} : ∅[a]? = none

Equations

• @Std.HashMap.getElem?_emptyc = @Std.HashMap.getElem?_empty

theorem Std.HashMap.getElem?_of_isEmpty {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a : α} : m.isEmpty = true → m[a]? = none

theorem Std.HashMap.getElem?_insert {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k a : α} {v : β} : (m.insert k v)[a]? = if (k == a) = true then some v else m[a]?

@[simp]

theorem Std.HashMap.getElem?_insert_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {v : β} : (m.insert k v)[k]? = some v

theorem Std.HashMap.contains_eq_isSome_getElem? {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a : α} : m.contains a = m[a]?.isSome

@[simp]

theorem Std.HashMap.isSome_getElem?_eq_contains {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a : α} : m[a]?.isSome = m.contains a

theorem Std.HashMap.mem_iff_isSome_getElem? {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a : α} : a ∈ m ↔ m[a]?.isSome = true

@[simp]

theorem Std.HashMap.isSome_getElem?_iff_mem {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a : α} : m[a]?.isSome = true ↔ a ∈ m

theorem Std.HashMap.getElem?_eq_some_iff {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {v : β} : m[k]? = some v ↔ ∃ (h : k ∈ m), m[k] = v

theorem Std.HashMap.getElem?_eq_none_of_contains_eq_false {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a : α} : m.contains a = false → m[a]? = none

theorem Std.HashMap.getElem?_eq_none {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a : α} : ¬a ∈ m → m[a]? = none

theorem Std.HashMap.getElem?_erase {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k a : α} : (m.erase k)[a]? = if (k == a) = true then none else m[a]?

@[simp]

theorem Std.HashMap.getElem?_erase_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} : (m.erase k)[k]? = none

theorem Std.HashMap.getElem?_congr {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a b : α} (hab : (a == b) = true) : m[a]? = m[b]?

theorem Std.HashMap.getElem_insert {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k a : α} {v : β} {h₁ : a ∈ m.insert k v} : (m.insert k v)[a] = if h₂ : (k == a) = true then v else m[a]

@[simp]

theorem Std.HashMap.getElem_insert_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {v : β} : (m.insert k v)[k] = v

@[simp]

theorem Std.HashMap.getElem_erase {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k a : α} {h' : a ∈ m.erase k} : (m.erase k)[a] = m[a]

theorem Std.HashMap.getElem?_eq_some_getElem {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a : α} (h' : a ∈ m) : m[a]? = some m[a]

theorem Std.HashMap.getElem_eq_get_getElem? {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a : α} {h : a ∈ m} : m[a] = m[a]?.get ⋯

theorem Std.HashMap.get_getElem? {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a : α} {h : m[a]?.isSome = true} : m[a]?.get h = m[a]

theorem Std.HashMap.getElem_congr {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a b : α} (hab : (a == b) = true) {h' : a ∈ m} : m[a] = m[b]

@[simp]

theorem Std.HashMap.getElem!_emptyWithCapacity {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} [Inhabited β] {a : α} {c : Nat} : (emptyWithCapacity c)[a]! = default

@[simp]

theorem Std.HashMap.getElem!_empty {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} [Inhabited β] {a : α} : ∅[a]! = default

@[reducible, inline, deprecated Std.HashMap.getElem!_empty (since := "2025-03-12")]

abbrev Std.HashMap.getElem!_emptyc {α : Type u_1} {β : Type u_2} {x✝ : BEq α} {x✝¹ : Hashable α} [Inhabited β] {a : α} : ∅[a]! = default

Equations

• @Std.HashMap.getElem!_emptyc = @Std.HashMap.getElem!_empty

theorem Std.HashMap.getElem!_of_isEmpty {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited β] {a : α} : m.isEmpty = true → m[a]! = default

theorem Std.HashMap.getElem!_insert {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited β] {k a : α} {v : β} : (m.insert k v)[a]! = if (k == a) = true then v else m[a]!

@[simp]

theorem Std.HashMap.getElem!_insert_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited β] {k : α} {v : β} : (m.insert k v)[k]! = v

theorem Std.HashMap.getElem!_eq_default_of_contains_eq_false {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited β] {a : α} : m.contains a = false → m[a]! = default

theorem Std.HashMap.getElem!_eq_default {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited β] {a : α} : ¬a ∈ m → m[a]! = default

theorem Std.HashMap.getElem!_erase {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited β] {k a : α} : (m.erase k)[a]! = if (k == a) = true then default else m[a]!

@[simp]

theorem Std.HashMap.getElem!_erase_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited β] {k : α} : (m.erase k)[k]! = default

theorem Std.HashMap.getElem?_eq_some_getElem!_of_contains {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited β] {a : α} : m.contains a = true → m[a]? = some m[a]!

theorem Std.HashMap.getElem?_eq_some_getElem! {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited β] {a : α} : a ∈ m → m[a]? = some m[a]!

theorem Std.HashMap.getElem!_eq_get!_getElem? {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited β] {a : α} : m[a]! = m[a]?.get!

theorem Std.HashMap.getElem_eq_getElem! {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited β] {a : α} {h' : a ∈ m} : m[a] = m[a]!

theorem Std.HashMap.getElem!_congr {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited β] {a b : α} (hab : (a == b) = true) : m[a]! = m[b]!

@[simp]

theorem Std.HashMap.getD_emptyWithCapacity {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {a : α} {fallback : β} {c : Nat} : (emptyWithCapacity c).getD a fallback = fallback

@[simp]

theorem Std.HashMap.getD_empty {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {a : α} {fallback : β} : ∅.getD a fallback = fallback

@[reducible, inline, deprecated Std.HashMap.getD_empty (since := "2025-03-12")]

abbrev Std.HashMap.getD_emptyc {α : Type u_1} {β : Type u_2} {x✝ : BEq α} {x✝¹ : Hashable α} {a : α} {fallback : β} : ∅.getD a fallback = fallback

Equations

• @Std.HashMap.getD_emptyc = @Std.HashMap.getD_empty

theorem Std.HashMap.getD_of_isEmpty {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a : α} {fallback : β} : m.isEmpty = true → m.getD a fallback = fallback

theorem Std.HashMap.getD_insert {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k a : α} {fallback v : β} : (m.insert k v).getD a fallback = if (k == a) = true then v else m.getD a fallback

@[simp]

theorem Std.HashMap.getD_insert_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {fallback v : β} : (m.insert k v).getD k fallback = v

theorem Std.HashMap.getD_eq_fallback_of_contains_eq_false {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a : α} {fallback : β} : m.contains a = false → m.getD a fallback = fallback

theorem Std.HashMap.getD_eq_fallback {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a : α} {fallback : β} : ¬a ∈ m → m.getD a fallback = fallback

theorem Std.HashMap.getD_erase {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k a : α} {fallback : β} : (m.erase k).getD a fallback = if (k == a) = true then fallback else m.getD a fallback

@[simp]

theorem Std.HashMap.getD_erase_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {fallback : β} : (m.erase k).getD k fallback = fallback

theorem Std.HashMap.getElem?_eq_some_getD_of_contains {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a : α} {fallback : β} : m.contains a = true → m[a]? = some (m.getD a fallback)

theorem Std.HashMap.getElem?_eq_some_getD {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a : α} {fallback : β} : a ∈ m → m[a]? = some (m.getD a fallback)

theorem Std.HashMap.getD_eq_getD_getElem? {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a : α} {fallback : β} : m.getD a fallback = m[a]?.getD fallback

theorem Std.HashMap.getElem_eq_getD {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a : α} {fallback : β} {h' : a ∈ m} : m[a] = m.getD a fallback

theorem Std.HashMap.getElem!_eq_getD_default {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited β] {a : α} : m[a]! = m.getD a default

theorem Std.HashMap.getD_congr {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a b : α} {fallback : β} (hab : (a == b) = true) : m.getD a fallback = m.getD b fallback

@[simp]

theorem Std.HashMap.getKey?_emptyWithCapacity {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {a : α} {c : Nat} : (emptyWithCapacity c).getKey? a = none

@[simp]

theorem Std.HashMap.getKey?_empty {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {a : α} : ∅.getKey? a = none

@[reducible, inline, deprecated Std.HashMap.getKey?_empty (since := "2025-03-12")]

abbrev Std.HashMap.getKey?_emptyc {α : Type u_1} {β : Type u_2} {x✝ : BEq α} {x✝¹ : Hashable α} {a : α} : ∅.getKey? a = none

Equations

• @Std.HashMap.getKey?_emptyc = @Std.HashMap.getKey?_empty

theorem Std.HashMap.getKey?_of_isEmpty {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a : α} : m.isEmpty = true → m.getKey? a = none

theorem Std.HashMap.getKey?_insert {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k a : α} {v : β} : (m.insert k v).getKey? a = if (k == a) = true then some k else m.getKey? a

@[simp]

theorem Std.HashMap.getKey?_insert_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {v : β} : (m.insert k v).getKey? k = some k

theorem Std.HashMap.contains_eq_isSome_getKey? {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a : α} : m.contains a = (m.getKey? a).isSome

@[simp]

theorem Std.HashMap.isSome_getKey?_eq_contains {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a : α} : (m.getKey? a).isSome = m.contains a

theorem Std.HashMap.mem_iff_isSome_getKey? {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a : α} : a ∈ m ↔ (m.getKey? a).isSome = true

@[simp]

theorem Std.HashMap.isSome_getKey?_iff_mem {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a : α} : (m.getKey? a).isSome = true ↔ a ∈ m

theorem Std.HashMap.mem_of_getKey?_eq_some {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k k' : α} (h : m.getKey? k = some k') : k' ∈ m

theorem Std.HashMap.getKey?_eq_some_iff {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k k' : α} : m.getKey? k = some k' ↔ ∃ (h : k ∈ m), m.getKey k h = k'

theorem Std.HashMap.getKey?_eq_none_of_contains_eq_false {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a : α} : m.contains a = false → m.getKey? a = none

theorem Std.HashMap.getKey?_eq_none {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a : α} : ¬a ∈ m → m.getKey? a = none

theorem Std.HashMap.getKey?_erase {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k a : α} : (m.erase k).getKey? a = if (k == a) = true then none else m.getKey? a

@[simp]

theorem Std.HashMap.getKey?_erase_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} : (m.erase k).getKey? k = none

theorem Std.HashMap.getKey?_beq {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} : Option.all (fun (x : α) => x == k) (m.getKey? k) = true

theorem Std.HashMap.getKey?_congr {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k k' : α} (h : (k == k') = true) : m.getKey? k = m.getKey? k'

theorem Std.HashMap.getKey?_eq_some_of_contains {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [LawfulBEq α] {k : α} (h : m.contains k = true) : m.getKey? k = some k

theorem Std.HashMap.getKey?_eq_some {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [LawfulBEq α] {k : α} (h : k ∈ m) : m.getKey? k = some k

theorem Std.HashMap.getKey_insert {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k a : α} {v : β} {h₁ : a ∈ m.insert k v} : (m.insert k v).getKey a h₁ = if h₂ : (k == a) = true then k else m.getKey a ⋯

@[simp]

theorem Std.HashMap.getKey_insert_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {v : β} : (m.insert k v).getKey k ⋯ = k

@[simp]

theorem Std.HashMap.getKey_erase {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k a : α} {h' : a ∈ m.erase k} : (m.erase k).getKey a h' = m.getKey a ⋯

theorem Std.HashMap.getKey?_eq_some_getKey {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a : α} (h : a ∈ m) : m.getKey? a = some (m.getKey a h)

theorem Std.HashMap.getKey_eq_get_getKey? {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a : α} {h : a ∈ m} : m.getKey a h = (m.getKey? a).get ⋯

@[simp]

theorem Std.HashMap.get_getKey? {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a : α} {h : (m.getKey? a).isSome = true} : (m.getKey? a).get h = m.getKey a ⋯

theorem Std.HashMap.getKey_beq {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} (h : k ∈ m) : (m.getKey k h == k) = true

theorem Std.HashMap.getKey_congr {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k₁ k₂ : α} (h : (k₁ == k₂) = true) (h₁ : k₁ ∈ m) : m.getKey k₁ h₁ = m.getKey k₂ ⋯

@[simp]

theorem Std.HashMap.getKey_eq {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [LawfulBEq α] {k : α} (h : k ∈ m) : m.getKey k h = k

@[simp]

theorem Std.HashMap.getKey!_emptyWithCapacity {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} [Inhabited α] {a : α} {c : Nat} : (emptyWithCapacity c).getKey! a = default

@[simp]

theorem Std.HashMap.getKey!_empty {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} [Inhabited α] {a : α} : ∅.getKey! a = default

@[reducible, inline, deprecated Std.HashMap.getKey!_empty (since := "2025-03-12")]

abbrev Std.HashMap.getKey!_emptyc {α : Type u_1} {β : Type u_2} {x✝ : BEq α} {x✝¹ : Hashable α} [Inhabited α] {a : α} : ∅.getKey! a = default

Equations

• @Std.HashMap.getKey!_emptyc = @Std.HashMap.getKey!_empty

theorem Std.HashMap.getKey!_of_isEmpty {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited α] {a : α} : m.isEmpty = true → m.getKey! a = default

theorem Std.HashMap.getKey!_insert {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited α] {k a : α} {v : β} : (m.insert k v).getKey! a = if (k == a) = true then k else m.getKey! a

@[simp]

theorem Std.HashMap.getKey!_insert_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited α] {k : α} {v : β} : (m.insert k v).getKey! k = k

theorem Std.HashMap.getKey!_eq_default_of_contains_eq_false {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited α] {a : α} : m.contains a = false → m.getKey! a = default

theorem Std.HashMap.getKey!_eq_default {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited α] {a : α} : ¬a ∈ m → m.getKey! a = default

theorem Std.HashMap.getKey!_erase {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited α] {k a : α} : (m.erase k).getKey! a = if (k == a) = true then default else m.getKey! a

@[simp]

theorem Std.HashMap.getKey!_erase_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited α] {k : α} : (m.erase k).getKey! k = default

theorem Std.HashMap.getKey?_eq_some_getKey!_of_contains {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited α] {a : α} : m.contains a = true → m.getKey? a = some (m.getKey! a)

theorem Std.HashMap.getKey?_eq_some_getKey! {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited α] {a : α} : a ∈ m → m.getKey? a = some (m.getKey! a)

theorem Std.HashMap.getKey!_eq_get!_getKey? {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited α] {a : α} : m.getKey! a = (m.getKey? a).get!

theorem Std.HashMap.getKey_eq_getKey! {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited α] {a : α} {h' : a ∈ m} : m.getKey a h' = m.getKey! a

theorem Std.HashMap.getKey!_congr {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited α] {k k' : α} (h : (k == k') = true) : m.getKey! k = m.getKey! k'

theorem Std.HashMap.getKey!_eq_of_contains {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [LawfulBEq α] [Inhabited α] {k : α} (h : m.contains k = true) : m.getKey! k = k

theorem Std.HashMap.getKey!_eq_of_mem {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [LawfulBEq α] [Inhabited α] {k : α} (h : k ∈ m) : m.getKey! k = k

@[simp]

theorem Std.HashMap.getKeyD_emptyWithCapacity {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {a fallback : α} {c : Nat} : (emptyWithCapacity c).getKeyD a fallback = fallback

@[simp]

theorem Std.HashMap.getKeyD_empty {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {a fallback : α} : ∅.getKeyD a fallback = fallback

@[reducible, inline, deprecated Std.HashMap.getKeyD_empty (since := "2025-03-12")]

abbrev Std.HashMap.getKeyD_emptyc {α : Type u_1} {β : Type u_2} {x✝ : BEq α} {x✝¹ : Hashable α} {a fallback : α} : ∅.getKeyD a fallback = fallback

Equations

• @Std.HashMap.getKeyD_emptyc = @Std.HashMap.getKeyD_empty

theorem Std.HashMap.getKeyD_of_isEmpty {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a fallback : α} : m.isEmpty = true → m.getKeyD a fallback = fallback

theorem Std.HashMap.getKeyD_insert {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k a fallback : α} {v : β} : (m.insert k v).getKeyD a fallback = if (k == a) = true then k else m.getKeyD a fallback

@[simp]

theorem Std.HashMap.getKeyD_insert_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k fallback : α} {v : β} : (m.insert k v).getKeyD k fallback = k

theorem Std.HashMap.getKeyD_eq_fallback_of_contains_eq_false {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a fallback : α} : m.contains a = false → m.getKeyD a fallback = fallback

theorem Std.HashMap.getKeyD_eq_fallback {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a fallback : α} : ¬a ∈ m → m.getKeyD a fallback = fallback

theorem Std.HashMap.getKeyD_erase {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k a fallback : α} : (m.erase k).getKeyD a fallback = if (k == a) = true then fallback else m.getKeyD a fallback

@[simp]

theorem Std.HashMap.getKeyD_erase_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k fallback : α} : (m.erase k).getKeyD k fallback = fallback

theorem Std.HashMap.getKey?_eq_some_getKeyD_of_contains {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a fallback : α} : m.contains a = true → m.getKey? a = some (m.getKeyD a fallback)

theorem Std.HashMap.getKey?_eq_some_getKeyD {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a fallback : α} : a ∈ m → m.getKey? a = some (m.getKeyD a fallback)

theorem Std.HashMap.getKeyD_eq_getD_getKey? {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a fallback : α} : m.getKeyD a fallback = (m.getKey? a).getD fallback

theorem Std.HashMap.getKey_eq_getKeyD {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {a fallback : α} {h' : a ∈ m} : m.getKey a h' = m.getKeyD a fallback

theorem Std.HashMap.getKey!_eq_getKeyD_default {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited α] {a : α} : m.getKey! a = m.getKeyD a default

theorem Std.HashMap.getKeyD_congr {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k k' fallback : α} (h : (k == k') = true) : m.getKeyD k fallback = m.getKeyD k' fallback

theorem Std.HashMap.getKeyD_eq_of_contains {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [LawfulBEq α] {k fallback : α} (h : m.contains k = true) : m.getKeyD k fallback = k

theorem Std.HashMap.getKeyD_eq_of_mem {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [LawfulBEq α] {k fallback : α} (h : k ∈ m) : m.getKeyD k fallback = k

@[simp]

theorem Std.HashMap.isEmpty_insertIfNew {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {v : β} : (m.insertIfNew k v).isEmpty = false

@[simp]

theorem Std.HashMap.contains_insertIfNew {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k a : α} {v : β} : (m.insertIfNew k v).contains a = (k == a || m.contains a)

@[simp]

theorem Std.HashMap.mem_insertIfNew {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k a : α} {v : β} : a ∈ m.insertIfNew k v ↔ (k == a) = true ∨ a ∈ m

theorem Std.HashMap.contains_insertIfNew_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {v : β} : (m.insertIfNew k v).contains k = true

theorem Std.HashMap.mem_insertIfNew_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {v : β} : k ∈ m.insertIfNew k v

theorem Std.HashMap.contains_of_contains_insertIfNew {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k a : α} {v : β} : (m.insertIfNew k v).contains a = true → (k == a) = false → m.contains a = true

theorem Std.HashMap.mem_of_mem_insertIfNew {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k a : α} {v : β} : a ∈ m.insertIfNew k v → (k == a) = false → a ∈ m

theorem Std.HashMap.contains_of_contains_insertIfNew' {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k a : α} {v : β} : (m.insertIfNew k v).contains a = true → ¬((k == a) = true ∧ m.contains k = false) → m.contains a = true

This is a restatement of contains_of_contains_insertIfNew that is written to exactly match the proof obligation in the statement of getElem_insertIfNew.

theorem Std.HashMap.mem_of_mem_insertIfNew' {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k a : α} {v : β} : a ∈ m.insertIfNew k v → ¬((k == a) = true ∧ ¬k ∈ m) → a ∈ m

This is a restatement of mem_of_mem_insertIfNew that is written to exactly match the proof obligation in the statement of getElem_insertIfNew.

theorem Std.HashMap.size_insertIfNew {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {v : β} : (m.insertIfNew k v).size = if k ∈ m then m.size else m.size + 1

theorem Std.HashMap.size_le_size_insertIfNew {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {v : β} : m.size ≤ (m.insertIfNew k v).size

theorem Std.HashMap.size_insertIfNew_le {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {v : β} : (m.insertIfNew k v).size ≤ m.size + 1

theorem Std.HashMap.getElem?_insertIfNew {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k a : α} {v : β} : (m.insertIfNew k v)[a]? = if (k == a) = true ∧ ¬k ∈ m then some v else m[a]?

theorem Std.HashMap.getElem_insertIfNew {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k a : α} {v : β} {h₁ : a ∈ m.insertIfNew k v} : (m.insertIfNew k v)[a] = if h₂ : (k == a) = true ∧ ¬k ∈ m then v else m[a]

theorem Std.HashMap.getElem!_insertIfNew {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited β] {k a : α} {v : β} : (m.insertIfNew k v)[a]! = if (k == a) = true ∧ ¬k ∈ m then v else m[a]!

theorem Std.HashMap.getD_insertIfNew {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k a : α} {fallback v : β} : (m.insertIfNew k v).getD a fallback = if (k == a) = true ∧ ¬k ∈ m then v else m.getD a fallback

theorem Std.HashMap.getKey?_insertIfNew {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k a : α} {v : β} : (m.insertIfNew k v).getKey? a = if (k == a) = true ∧ ¬k ∈ m then some k else m.getKey? a

theorem Std.HashMap.getKey_insertIfNew {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k a : α} {v : β} {h₁ : a ∈ m.insertIfNew k v} : (m.insertIfNew k v).getKey a h₁ = if h₂ : (k == a) = true ∧ ¬k ∈ m then k else m.getKey a ⋯

theorem Std.HashMap.getKey!_insertIfNew {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited α] {k a : α} {v : β} : (m.insertIfNew k v).getKey! a = if (k == a) = true ∧ ¬k ∈ m then k else m.getKey! a

theorem Std.HashMap.getKeyD_insertIfNew {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k a fallback : α} {v : β} : (m.insertIfNew k v).getKeyD a fallback = if (k == a) = true ∧ ¬k ∈ m then k else m.getKeyD a fallback

@[simp]

theorem Std.HashMap.getThenInsertIfNew?_fst {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {k : α} {v : β} : (m.getThenInsertIfNew? k v).fst = m.get? k

@[simp]

theorem Std.HashMap.getThenInsertIfNew?_snd {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {k : α} {v : β} : (m.getThenInsertIfNew? k v).snd = m.insertIfNew k v

instance Std.HashMap.instLawfulGetElemMemOfEquivBEqOfLawfulHashable {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] : LawfulGetElem (HashMap α β) α β fun (m : HashMap α β) (a : α) => a ∈ m

@[simp]

theorem Std.HashMap.length_keys {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] : m.keys.length = m.size

@[simp]

theorem Std.HashMap.isEmpty_keys {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] : m.keys.isEmpty = m.isEmpty

@[simp]

theorem Std.HashMap.contains_keys {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} : m.keys.contains k = m.contains k

@[simp]

theorem Std.HashMap.mem_keys {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [LawfulBEq α] {k : α} : k ∈ m.keys ↔ k ∈ m

theorem Std.HashMap.mem_of_mem_keys {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} (h : k ∈ m.keys) : k ∈ m

theorem Std.HashMap.distinct_keys {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] : List.Pairwise (fun (a b : α) => (a == b) = false) m.keys

theorem Std.HashMap.nodup_keys {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] : m.keys.Nodup

@[simp]

theorem Std.HashMap.toArray_keys {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} : m.keys.toArray = m.keysArray

@[simp]

theorem Std.HashMap.toList_keysArray {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} : m.keysArray.toList = m.keys

@[simp]

theorem Std.HashMap.size_keysArray {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] : m.keysArray.size = m.size

@[simp]

theorem Std.HashMap.isEmpty_keysArray {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] : m.keysArray.isEmpty = m.isEmpty

@[simp]

theorem Std.HashMap.contains_keysArray {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} : m.keysArray.contains k = m.contains k

@[simp]

theorem Std.HashMap.mem_keysArray {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [LawfulBEq α] {k : α} : k ∈ m.keysArray ↔ k ∈ m

theorem Std.HashMap.forall_mem_keysArray_iff_forall_mem_getKey {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {p : α → Prop} : (∀ (k : α), k ∈ m.keysArray → p k) ↔ ∀ (k : α) (h : k ∈ m), p (m.getKey k h)

theorem Std.HashMap.contains_of_mem_keysArray {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} (h' : k ∈ m.keysArray) : m.contains k = true

@[simp]

theorem Std.HashMap.map_fst_toList_eq_keys {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] : List.map Prod.fst m.toList = m.keys

@[deprecated Std.HashMap.map_fst_toList_eq_keys (since := "2025-02-28")]

theorem Std.HashMap.map_prod_fst_toList_eq_keys {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] : List.map Prod.fst m.toList = m.keys

@[simp]

theorem Std.HashMap.length_toList {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] : m.toList.length = m.size

@[simp]

theorem Std.HashMap.isEmpty_toList {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] : m.toList.isEmpty = m.isEmpty

@[simp]

theorem Std.HashMap.mem_toList_iff_getElem?_eq_some {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [LawfulBEq α] {k : α} {v : β} : (k, v) ∈ m.toList ↔ m[k]? = some v

@[simp]

theorem Std.HashMap.mem_toList_iff_getKey?_eq_some_and_getElem?_eq_some {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {v : β} : (k, v) ∈ m.toList ↔ m.getKey? k = some k ∧ m[k]? = some v

theorem Std.HashMap.getElem?_eq_some_iff_exists_beq_and_mem_toList {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {v : β} : m[k]? = some v ↔ ∃ (k' : α), (k == k') = true ∧ (k', v) ∈ m.toList

@[reducible, inline, deprecated Std.HashMap.getElem?_eq_some_iff_exists_beq_and_mem_toList (since := "2025-04-13")]

abbrev Std.HashMap.get?_eq_some_iff_exists_beq_and_mem_toList {α : Type u_1} {β : Type u_2} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {v : β} : m[k]? = some v ↔ ∃ (k' : α), (k == k') = true ∧ (k', v) ∈ m.toList

Equations

• @Std.HashMap.get?_eq_some_iff_exists_beq_and_mem_toList = @Std.HashMap.getElem?_eq_some_iff_exists_beq_and_mem_toList

theorem Std.HashMap.find?_toList_eq_some_iff_getKey?_eq_some_and_getElem?_eq_some {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k k' : α} {v : β} : List.find? (fun (a : α × β) => a.fst == k) m.toList = some (k', v) ↔ m.getKey? k = some k' ∧ m[k]? = some v

theorem Std.HashMap.find?_toList_eq_none_iff_contains_eq_false {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} : List.find? (fun (x : α × β) => x.fst == k) m.toList = none ↔ m.contains k = false

@[simp]

theorem Std.HashMap.find?_toList_eq_none_iff_not_mem {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} : List.find? (fun (x : α × β) => x.fst == k) m.toList = none ↔ ¬k ∈ m

theorem Std.HashMap.distinct_keys_toList {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] : List.Pairwise (fun (a b : α × β) => (a.fst == b.fst) = false) m.toList

@[simp]

theorem Std.HashMap.toArray_toList {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} : m.toList.toArray = m.toArray

@[simp]

theorem Std.HashMap.toList_toArray {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} : m.toArray.toList = m.toList

@[simp]

theorem Std.HashMap.map_fst_toArray_eq_keysArray {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] : Array.map Prod.fst m.toArray = m.keysArray

@[simp]

theorem Std.HashMap.size_toArray {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] : m.toArray.size = m.size

@[simp]

theorem Std.HashMap.isEmpty_toArray {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] : m.toArray.isEmpty = m.isEmpty

theorem Std.HashMap.mem_toArray_iff_getElem?_eq_some {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [LawfulBEq α] {k : α} {v : β} : (k, v) ∈ m.toArray ↔ m[k]? = some v

theorem Std.HashMap.getElem?_eq_some_iff_exists_beq_and_mem_toArray {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {v : β} : m[k]? = some v ↔ ∃ (k' : α), (k == k') = true ∧ (k', v) ∈ m.toArray

theorem Std.HashMap.find?_toArray_eq_some_iff_getKey?_eq_some_and_get?_eq_some {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k k' : α} {v : β} : Array.find? (fun (a : α × β) => a.fst == k) m.toArray = some (k', v) ↔ m.getKey? k = some k' ∧ m.get? k = some v

theorem Std.HashMap.find?_toArray_eq_none_iff_contains_eq_false {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} : Array.find? (fun (x : α × β) => x.fst == k) m.toArray = none ↔ m.contains k = false

theorem Std.HashMap.mem_toArray_iff_getKey?_eq_some_and_getElem?_eq_some {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {v : β} : (k, v) ∈ m.toArray ↔ m.getKey? k = some k ∧ m[k]? = some v

theorem Std.HashMap.foldM_eq_foldlM_toList {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {δ : Type w} {m' : Type w → Type w'} [Monad m'] [LawfulMonad m'] {f : δ → α → β → m' δ} {init : δ} : foldM f init m = List.foldlM (fun (a : δ) (b : α × β) => f a b.fst b.snd) init m.toList

theorem Std.HashMap.fold_eq_foldl_toList {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {δ : Type w} {f : δ → α → β → δ} {init : δ} : fold f init m = List.foldl (fun (a : δ) (b : α × β) => f a b.fst b.snd) init m.toList

@[simp]

theorem Std.HashMap.forM_eq_forM {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {m' : Type w → Type w'} [Monad m'] [LawfulMonad m'] {f : α → β → m' PUnit} : forM f m = ForM.forM m fun (a : α × β) => f a.fst a.snd

theorem Std.HashMap.forM_eq_forM_toList {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {m' : Type w → Type w'} [Monad m'] [LawfulMonad m'] {f : α × β → m' PUnit} : ForM.forM m f = ForM.forM m.toList f

@[simp]

theorem Std.HashMap.forIn_eq_forIn {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {δ : Type w} {m' : Type w → Type w'} [Monad m'] [LawfulMonad m'] {f : α → β → δ → m' (ForInStep δ)} {init : δ} : forIn f init m = ForIn.forIn m init fun (a : α × β) (d : δ) => f a.fst a.snd d

theorem Std.HashMap.forIn_eq_forIn_toList {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {δ : Type w} {m' : Type w → Type w'} [Monad m'] [LawfulMonad m'] {f : α × β → δ → m' (ForInStep δ)} {init : δ} : ForIn.forIn m init f = ForIn.forIn m.toList init f

theorem Std.HashMap.foldM_eq_foldlM_keys {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {δ : Type w} {m' : Type w → Type w'} [Monad m'] [LawfulMonad m'] {f : δ → α → m' δ} {init : δ} : foldM (fun (d : δ) (a : α) (x : β) => f d a) init m = List.foldlM f init m.keys

theorem Std.HashMap.fold_eq_foldl_keys {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {δ : Type w} {f : δ → α → δ} {init : δ} : fold (fun (d : δ) (a : α) (x : β) => f d a) init m = List.foldl f init m.keys

theorem Std.HashMap.forM_eq_forM_keys {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {m' : Type w → Type w'} [Monad m'] [LawfulMonad m'] {f : α → m' PUnit} : (ForM.forM m fun (a : α × β) => f a.fst) = m.keys.forM f

theorem Std.HashMap.forIn_eq_forIn_keys {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {δ : Type w} {m' : Type w → Type w'} [Monad m'] [LawfulMonad m'] {f : α → δ → m' (ForInStep δ)} {init : δ} : (ForIn.forIn m init fun (a : α × β) (d : δ) => f a.fst d) = ForIn.forIn m.keys init f

theorem Std.HashMap.foldM_eq_foldlM_toArray {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {δ : Type w} {m' : Type w → Type w'} [Monad m'] [LawfulMonad m'] {f : δ → α → β → m' δ} {init : δ} : foldM f init m = Array.foldlM (fun (a : δ) (b : α × β) => f a b.fst b.snd) init m.toArray

theorem Std.HashMap.fold_eq_foldl_toArray {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {δ : Type w} {f : δ → α → β → δ} {init : δ} : fold f init m = Array.foldl (fun (a : δ) (b : α × β) => f a b.fst b.snd) init m.toArray

theorem Std.HashMap.forM_eq_forM_toArray {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {m' : Type w → Type w'} [Monad m'] [LawfulMonad m'] {f : α → β → m' PUnit} : forM f m = Array.forM (fun (a : α × β) => f a.fst a.snd) m.toArray

theorem Std.HashMap.forIn_eq_forIn_toArray {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {δ : Type w} {m' : Type w → Type w'} [Monad m'] [LawfulMonad m'] {f : α → β → δ → m' (ForInStep δ)} {init : δ} : forIn f init m = ForIn.forIn m.toArray init fun (a : α × β) (b : δ) => f a.fst a.snd b

theorem Std.HashMap.foldM_eq_foldlM_keysArray {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {δ : Type w} {m' : Type w → Type w'} [Monad m'] [LawfulMonad m'] {f : δ → α → m' δ} {init : δ} : foldM (fun (d : δ) (a : α) (x : β) => f d a) init m = Array.foldlM f init m.keysArray

theorem Std.HashMap.fold_eq_foldl_keysArray {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {δ : Type w} {f : δ → α → δ} {init : δ} : fold (fun (d : δ) (a : α) (x : β) => f d a) init m = Array.foldl f init m.keysArray

theorem Std.HashMap.forM_eq_forM_keysArray {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {m' : Type w → Type w'} [Monad m'] [LawfulMonad m'] {f : α → m' PUnit} : forM (fun (a : α) (x : β) => f a) m = Array.forM f m.keysArray

theorem Std.HashMap.forIn_eq_forIn_keysArray {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {δ : Type w} {m' : Type w → Type w'} [Monad m'] [LawfulMonad m'] {f : α → δ → m' (ForInStep δ)} {init : δ} : forIn (fun (a : α) (x : β) (d : δ) => f a d) init m = ForIn.forIn m.keysArray init f

@[simp]

theorem Std.HashMap.insertMany_nil {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} : m.insertMany [] = m

@[simp]

theorem Std.HashMap.insertMany_list_singleton {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {k : α} {v : β} : m.insertMany [(k, v)] = m.insert k v

theorem Std.HashMap.insertMany_cons {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {l : List (α × β)} {k : α} {v : β} : m.insertMany ((k, v) :: l) = (m.insert k v).insertMany l

theorem Std.HashMap.insertMany_append {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {l₁ l₂ : List (α × β)} : m.insertMany (l₁ ++ l₂) = (m.insertMany l₁).insertMany l₂

theorem Std.HashMap.insertMany_ind {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {ρ : Type w} [ForIn Id ρ (α × β)] {motive : HashMap α β → Prop} (m : HashMap α β) {l : ρ} (init : motive m) (insert : ∀ (m : HashMap α β) (a : α) (b : β), motive m → motive (m.insert a b)) : motive (m.insertMany l)

@[simp]

theorem Std.HashMap.contains_insertMany_list {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} {k : α} : (m.insertMany l).contains k = (m.contains k || (List.map Prod.fst l).contains k)

@[simp]

theorem Std.HashMap.mem_insertMany_list {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} {k : α} : k ∈ m.insertMany l ↔ k ∈ m ∨ (List.map Prod.fst l).contains k = true

theorem Std.HashMap.mem_of_mem_insertMany_list {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} {k : α} (mem : k ∈ m.insertMany l) (contains_eq_false : (List.map Prod.fst l).contains k = false) : k ∈ m

theorem Std.HashMap.mem_insertMany_of_mem {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {ρ : Type w} [ForIn Id ρ (α × β)] [EquivBEq α] [LawfulHashable α] {l : ρ} {k : α} : k ∈ m → k ∈ m.insertMany l

theorem Std.HashMap.getElem?_insertMany_list_of_contains_eq_false {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} {k : α} (contains_eq_false : (List.map Prod.fst l).contains k = false) : (m.insertMany l)[k]? = m[k]?

theorem Std.HashMap.getElem?_insertMany_list_of_mem {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} {k k' : α} (k_beq : (k == k') = true) {v : β} (distinct : List.Pairwise (fun (a b : α × β) => (a.fst == b.fst) = false) l) (mem : (k, v) ∈ l) : (m.insertMany l)[k']? = some v

theorem Std.HashMap.getElem?_insertMany_list {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} {k : α} : (m.insertMany l)[k]? = (List.findSomeRev? (fun (x : α × β) => match x with | (a, b) => if (a == k) = true then some b else none) l).or m[k]?

theorem Std.HashMap.getElem_insertMany_list_of_contains_eq_false {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} {k : α} (contains_eq_false : (List.map Prod.fst l).contains k = false) {h : k ∈ m.insertMany l} : (m.insertMany l)[k] = m[k]

theorem Std.HashMap.getElem_insertMany_list_of_mem {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} {k k' : α} (k_beq : (k == k') = true) {v : β} (distinct : List.Pairwise (fun (a b : α × β) => (a.fst == b.fst) = false) l) (mem : (k, v) ∈ l) {h : k' ∈ m.insertMany l} : (m.insertMany l)[k'] = v

theorem Std.HashMap.getElem!_insertMany_list_of_contains_eq_false {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited β] {l : List (α × β)} {k : α} (contains_eq_false : (List.map Prod.fst l).contains k = false) : (m.insertMany l)[k]! = m[k]!

theorem Std.HashMap.getElem!_insertMany_list_of_mem {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited β] {l : List (α × β)} {k k' : α} (k_beq : (k == k') = true) {v : β} (distinct : List.Pairwise (fun (a b : α × β) => (a.fst == b.fst) = false) l) (mem : (k, v) ∈ l) : (m.insertMany l)[k']! = v

theorem Std.HashMap.getD_insertMany_list_of_contains_eq_false {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} {k : α} {fallback : β} (contains_eq_false : (List.map Prod.fst l).contains k = false) : (m.insertMany l).getD k fallback = m.getD k fallback

theorem Std.HashMap.getD_insertMany_list_of_mem {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} {k k' : α} (k_beq : (k == k') = true) {v fallback : β} (distinct : List.Pairwise (fun (a b : α × β) => (a.fst == b.fst) = false) l) (mem : (k, v) ∈ l) : (m.insertMany l).getD k' fallback = v

theorem Std.HashMap.getKey?_insertMany_list_of_contains_eq_false {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} {k : α} (contains_eq_false : (List.map Prod.fst l).contains k = false) : (m.insertMany l).getKey? k = m.getKey? k

theorem Std.HashMap.getKey?_insertMany_list_of_mem {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} {k k' : α} (k_beq : (k == k') = true) (distinct : List.Pairwise (fun (a b : α × β) => (a.fst == b.fst) = false) l) (mem : k ∈ List.map Prod.fst l) : (m.insertMany l).getKey? k' = some k

theorem Std.HashMap.getKey_insertMany_list_of_contains_eq_false {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} {k : α} (contains_eq_false : (List.map Prod.fst l).contains k = false) {h : k ∈ m.insertMany l} : (m.insertMany l).getKey k h = m.getKey k ⋯

theorem Std.HashMap.getKey_insertMany_list_of_mem {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} {k k' : α} (k_beq : (k == k') = true) (distinct : List.Pairwise (fun (a b : α × β) => (a.fst == b.fst) = false) l) (mem : k ∈ List.map Prod.fst l) {h : k' ∈ m.insertMany l} : (m.insertMany l).getKey k' h = k

theorem Std.HashMap.getKey!_insertMany_list_of_contains_eq_false {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited α] {l : List (α × β)} {k : α} (contains_eq_false : (List.map Prod.fst l).contains k = false) : (m.insertMany l).getKey! k = m.getKey! k

theorem Std.HashMap.getKey!_insertMany_list_of_mem {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited α] {l : List (α × β)} {k k' : α} (k_beq : (k == k') = true) (distinct : List.Pairwise (fun (a b : α × β) => (a.fst == b.fst) = false) l) (mem : k ∈ List.map Prod.fst l) : (m.insertMany l).getKey! k' = k

theorem Std.HashMap.getKeyD_insertMany_list_of_contains_eq_false {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} {k fallback : α} (contains_eq_false : (List.map Prod.fst l).contains k = false) : (m.insertMany l).getKeyD k fallback = m.getKeyD k fallback

theorem Std.HashMap.getKeyD_insertMany_list_of_mem {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} {k k' fallback : α} (k_beq : (k == k') = true) (distinct : List.Pairwise (fun (a b : α × β) => (a.fst == b.fst) = false) l) (mem : k ∈ List.map Prod.fst l) : (m.insertMany l).getKeyD k' fallback = k

theorem Std.HashMap.size_insertMany_list {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} (distinct : List.Pairwise (fun (a b : α × β) => (a.fst == b.fst) = false) l) : (∀ (a : α), a ∈ m → (List.map Prod.fst l).contains a = false) → (m.insertMany l).size = m.size + l.length

theorem Std.HashMap.size_le_size_insertMany_list {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} : m.size ≤ (m.insertMany l).size

theorem Std.HashMap.size_le_size_insertMany {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {ρ : Type w} [ForIn Id ρ (α × β)] [EquivBEq α] [LawfulHashable α] {l : ρ} : m.size ≤ (m.insertMany l).size

theorem Std.HashMap.size_insertMany_list_le {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} : (m.insertMany l).size ≤ m.size + l.length

@[simp]

theorem Std.HashMap.isEmpty_insertMany_list {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} : (m.insertMany l).isEmpty = (m.isEmpty && l.isEmpty)

theorem Std.HashMap.isEmpty_of_isEmpty_insertMany {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {ρ : Type w} [ForIn Id ρ (α × β)] [EquivBEq α] [LawfulHashable α] {l : ρ} : (m.insertMany l).isEmpty = true → m.isEmpty = true

@[simp]

theorem Std.HashMap.insertManyIfNewUnit_nil {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α Unit} : m.insertManyIfNewUnit [] = m

@[simp]

theorem Std.HashMap.insertManyIfNewUnit_list_singleton {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α Unit} {k : α} : m.insertManyIfNewUnit [k] = m.insertIfNew k ()

theorem Std.HashMap.insertManyIfNewUnit_cons {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α Unit} {l : List α} {k : α} : m.insertManyIfNewUnit (k :: l) = (m.insertIfNew k ()).insertManyIfNewUnit l

theorem Std.HashMap.insertManyIfNewUnit_ind {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {ρ : Type w} [ForIn Id ρ α] {motive : HashMap α Unit → Prop} (m : HashMap α Unit) (l : ρ) (init : motive m) (insert : ∀ (m : HashMap α Unit) (a : α), motive m → motive (m.insertIfNew a ())) : motive (m.insertManyIfNewUnit l)

@[simp]

theorem Std.HashMap.contains_insertManyIfNewUnit_list {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α Unit} [EquivBEq α] [LawfulHashable α] {l : List α} {k : α} : (m.insertManyIfNewUnit l).contains k = (m.contains k || l.contains k)

@[simp]

theorem Std.HashMap.mem_insertManyIfNewUnit_list {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α Unit} [EquivBEq α] [LawfulHashable α] {l : List α} {k : α} : k ∈ m.insertManyIfNewUnit l ↔ k ∈ m ∨ l.contains k = true

theorem Std.HashMap.mem_of_mem_insertManyIfNewUnit_list {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α Unit} [EquivBEq α] [LawfulHashable α] {l : List α} {k : α} (contains_eq_false : l.contains k = false) : k ∈ m.insertManyIfNewUnit l → k ∈ m

theorem Std.HashMap.mem_insertManyIfNewUnit_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α Unit} {ρ : Type w} [ForIn Id ρ α] [EquivBEq α] [LawfulHashable α] {l : ρ} {k : α} : k ∈ m → k ∈ m.insertManyIfNewUnit l

theorem Std.HashMap.getElem?_insertManyIfNewUnit_list {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α Unit} [EquivBEq α] [LawfulHashable α] {l : List α} {k : α} : (m.insertManyIfNewUnit l)[k]? = if k ∈ m ∨ l.contains k = true then some () else none

theorem Std.HashMap.getElem_insertManyIfNewUnit_list {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α Unit} {l : List α} {k : α} {h : k ∈ m.insertManyIfNewUnit l} : (m.insertManyIfNewUnit l)[k] = ()

theorem Std.HashMap.getElem!_insertManyIfNewUnit_list {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α Unit} {l : List α} {k : α} : (m.insertManyIfNewUnit l)[k]! = ()

theorem Std.HashMap.getD_insertManyIfNewUnit_list {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α Unit} {l : List α} {k : α} {fallback : Unit} : (m.insertManyIfNewUnit l).getD k fallback = ()

theorem Std.HashMap.getKey?_insertManyIfNewUnit_list_of_not_mem_of_contains_eq_false {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α Unit} [EquivBEq α] [LawfulHashable α] {l : List α} {k : α} (not_mem : ¬k ∈ m) (contains_eq_false : l.contains k = false) : (m.insertManyIfNewUnit l).getKey? k = none

theorem Std.HashMap.getKey?_insertManyIfNewUnit_list_of_not_mem_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α Unit} [EquivBEq α] [LawfulHashable α] {l : List α} {k k' : α} (k_beq : (k == k') = true) (not_mem : ¬k ∈ m) (distinct : List.Pairwise (fun (a b : α) => (a == b) = false) l) (mem : k ∈ l) : (m.insertManyIfNewUnit l).getKey? k' = some k

theorem Std.HashMap.getKey?_insertManyIfNewUnit_list_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α Unit} [EquivBEq α] [LawfulHashable α] {l : List α} {k : α} (mem : k ∈ m) : (m.insertManyIfNewUnit l).getKey? k = m.getKey? k

theorem Std.HashMap.getKey_insertManyIfNewUnit_list_of_not_mem_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α Unit} [EquivBEq α] [LawfulHashable α] {l : List α} {k k' : α} (k_beq : (k == k') = true) (not_mem : ¬k ∈ m) (distinct : List.Pairwise (fun (a b : α) => (a == b) = false) l) (mem : k ∈ l) {h : k' ∈ m.insertManyIfNewUnit l} : (m.insertManyIfNewUnit l).getKey k' h = k

theorem Std.HashMap.getKey_insertManyIfNewUnit_list_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α Unit} [EquivBEq α] [LawfulHashable α] {l : List α} {k : α} (mem : k ∈ m) {h : k ∈ m.insertManyIfNewUnit l} : (m.insertManyIfNewUnit l).getKey k h = m.getKey k mem

theorem Std.HashMap.getKey!_insertManyIfNewUnit_list_of_not_mem_of_contains_eq_false {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α Unit} [EquivBEq α] [LawfulHashable α] [Inhabited α] {l : List α} {k : α} (not_mem : ¬k ∈ m) (contains_eq_false : l.contains k = false) : (m.insertManyIfNewUnit l).getKey! k = default

theorem Std.HashMap.getKey!_insertManyIfNewUnit_list_of_not_mem_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α Unit} [EquivBEq α] [LawfulHashable α] [Inhabited α] {l : List α} {k k' : α} (k_beq : (k == k') = true) (not_mem : ¬k ∈ m) (distinct : List.Pairwise (fun (a b : α) => (a == b) = false) l) (mem : k ∈ l) : (m.insertManyIfNewUnit l).getKey! k' = k

theorem Std.HashMap.getKey!_insertManyIfNewUnit_list_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α Unit} [EquivBEq α] [LawfulHashable α] [Inhabited α] {l : List α} {k : α} (mem : k ∈ m) : (m.insertManyIfNewUnit l).getKey! k = m.getKey! k

theorem Std.HashMap.getKeyD_insertManyIfNewUnit_list_of_not_mem_of_contains_eq_false {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α Unit} [EquivBEq α] [LawfulHashable α] {l : List α} {k fallback : α} (not_mem : ¬k ∈ m) (contains_eq_false : l.contains k = false) : (m.insertManyIfNewUnit l).getKeyD k fallback = fallback

theorem Std.HashMap.getKeyD_insertManyIfNewUnit_list_of_not_mem_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α Unit} [EquivBEq α] [LawfulHashable α] {l : List α} {k k' fallback : α} (k_beq : (k == k') = true) (not_mem : ¬k ∈ m) (distinct : List.Pairwise (fun (a b : α) => (a == b) = false) l) (mem : k ∈ l) : (m.insertManyIfNewUnit l).getKeyD k' fallback = k

theorem Std.HashMap.getKeyD_insertManyIfNewUnit_list_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α Unit} [EquivBEq α] [LawfulHashable α] {l : List α} {k fallback : α} (mem : k ∈ m) : (m.insertManyIfNewUnit l).getKeyD k fallback = m.getKeyD k fallback

theorem Std.HashMap.size_insertManyIfNewUnit_list {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α Unit} [EquivBEq α] [LawfulHashable α] {l : List α} (distinct : List.Pairwise (fun (a b : α) => (a == b) = false) l) : (∀ (a : α), a ∈ m → l.contains a = false) → (m.insertManyIfNewUnit l).size = m.size + l.length

theorem Std.HashMap.size_le_size_insertManyIfNewUnit_list {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α Unit} [EquivBEq α] [LawfulHashable α] {l : List α} : m.size ≤ (m.insertManyIfNewUnit l).size

theorem Std.HashMap.size_le_size_insertManyIfNewUnit {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α Unit} {ρ : Type w} [ForIn Id ρ α] [EquivBEq α] [LawfulHashable α] {l : ρ} : m.size ≤ (m.insertManyIfNewUnit l).size

theorem Std.HashMap.size_insertManyIfNewUnit_list_le {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α Unit} [EquivBEq α] [LawfulHashable α] {l : List α} : (m.insertManyIfNewUnit l).size ≤ m.size + l.length

@[simp]

theorem Std.HashMap.isEmpty_insertManyIfNewUnit_list {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α Unit} [EquivBEq α] [LawfulHashable α] {l : List α} : (m.insertManyIfNewUnit l).isEmpty = (m.isEmpty && l.isEmpty)

theorem Std.HashMap.isEmpty_of_isEmpty_insertManyIfNewUnit {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α Unit} {ρ : Type w} [ForIn Id ρ α] [EquivBEq α] [LawfulHashable α] {l : ρ} : (m.insertManyIfNewUnit l).isEmpty = true → m.isEmpty = true

@[simp]

theorem Std.HashMap.ofList_nil {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} : ofList [] = ∅

@[simp]

theorem Std.HashMap.ofList_singleton {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {k : α} {v : β} : ofList [(k, v)] = ∅.insert k v

theorem Std.HashMap.ofList_cons {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {k : α} {v : β} {tl : List (α × β)} : ofList ((k, v) :: tl) = (∅.insert k v).insertMany tl

theorem Std.HashMap.ofList_eq_insertMany_empty {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {l : List (α × β)} : ofList l = ∅.insertMany l

@[simp]

theorem Std.HashMap.contains_ofList {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} {k : α} : (ofList l).contains k = (List.map Prod.fst l).contains k

@[simp]

theorem Std.HashMap.mem_ofList {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} {k : α} : k ∈ ofList l ↔ (List.map Prod.fst l).contains k = true

theorem Std.HashMap.getElem?_ofList_of_contains_eq_false {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} {k : α} (contains_eq_false : (List.map Prod.fst l).contains k = false) : (ofList l)[k]? = none

theorem Std.HashMap.getElem?_ofList_of_mem {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} {k k' : α} (k_beq : (k == k') = true) {v : β} (distinct : List.Pairwise (fun (a b : α × β) => (a.fst == b.fst) = false) l) (mem : (k, v) ∈ l) : (ofList l)[k']? = some v

theorem Std.HashMap.getElem_ofList_of_mem {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} {k k' : α} (k_beq : (k == k') = true) {v : β} (distinct : List.Pairwise (fun (a b : α × β) => (a.fst == b.fst) = false) l) (mem : (k, v) ∈ l) {h : k' ∈ ofList l} : (ofList l)[k'] = v

theorem Std.HashMap.getElem!_ofList_of_contains_eq_false {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} {k : α} [Inhabited β] (contains_eq_false : (List.map Prod.fst l).contains k = false) : (ofList l)[k]! = default

theorem Std.HashMap.getElem!_ofList_of_mem {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} {k k' : α} (k_beq : (k == k') = true) {v : β} [Inhabited β] (distinct : List.Pairwise (fun (a b : α × β) => (a.fst == b.fst) = false) l) (mem : (k, v) ∈ l) : (ofList l)[k']! = v

theorem Std.HashMap.getD_ofList_of_contains_eq_false {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} {k : α} {fallback : β} (contains_eq_false : (List.map Prod.fst l).contains k = false) : (ofList l).getD k fallback = fallback

theorem Std.HashMap.getD_ofList_of_mem {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} {k k' : α} (k_beq : (k == k') = true) {v fallback : β} (distinct : List.Pairwise (fun (a b : α × β) => (a.fst == b.fst) = false) l) (mem : (k, v) ∈ l) : (ofList l).getD k' fallback = v

theorem Std.HashMap.getKey?_ofList_of_contains_eq_false {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} {k : α} (contains_eq_false : (List.map Prod.fst l).contains k = false) : (ofList l).getKey? k = none

theorem Std.HashMap.getKey?_ofList_of_mem {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} {k k' : α} (k_beq : (k == k') = true) (distinct : List.Pairwise (fun (a b : α × β) => (a.fst == b.fst) = false) l) (mem : k ∈ List.map Prod.fst l) : (ofList l).getKey? k' = some k

theorem Std.HashMap.getKey_ofList_of_mem {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} {k k' : α} (k_beq : (k == k') = true) (distinct : List.Pairwise (fun (a b : α × β) => (a.fst == b.fst) = false) l) (mem : k ∈ List.map Prod.fst l) {h : k' ∈ ofList l} : (ofList l).getKey k' h = k

theorem Std.HashMap.getKey!_ofList_of_contains_eq_false {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {l : List (α × β)} {k : α} (contains_eq_false : (List.map Prod.fst l).contains k = false) : (ofList l).getKey! k = default

theorem Std.HashMap.getKey!_ofList_of_mem {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {l : List (α × β)} {k k' : α} (k_beq : (k == k') = true) (distinct : List.Pairwise (fun (a b : α × β) => (a.fst == b.fst) = false) l) (mem : k ∈ List.map Prod.fst l) : (ofList l).getKey! k' = k

theorem Std.HashMap.getKeyD_ofList_of_contains_eq_false {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} {k fallback : α} (contains_eq_false : (List.map Prod.fst l).contains k = false) : (ofList l).getKeyD k fallback = fallback

theorem Std.HashMap.getKeyD_ofList_of_mem {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} {k k' fallback : α} (k_beq : (k == k') = true) (distinct : List.Pairwise (fun (a b : α × β) => (a.fst == b.fst) = false) l) (mem : k ∈ List.map Prod.fst l) : (ofList l).getKeyD k' fallback = k

theorem Std.HashMap.size_ofList {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} (distinct : List.Pairwise (fun (a b : α × β) => (a.fst == b.fst) = false) l) : (ofList l).size = l.length

theorem Std.HashMap.size_ofList_le {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} : (ofList l).size ≤ l.length

@[simp]

theorem Std.HashMap.isEmpty_ofList {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List (α × β)} : (ofList l).isEmpty = l.isEmpty

@[simp]

theorem Std.HashMap.unitOfList_nil {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} : unitOfList [] = ∅

@[simp]

theorem Std.HashMap.unitOfList_singleton {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {k : α} : unitOfList [k] = ∅.insertIfNew k ()

theorem Std.HashMap.unitOfList_cons {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {hd : α} {tl : List α} : unitOfList (hd :: tl) = (∅.insertIfNew hd ()).insertManyIfNewUnit tl

@[simp]

theorem Std.HashMap.contains_unitOfList {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List α} {k : α} : (unitOfList l).contains k = l.contains k

@[simp]

theorem Std.HashMap.mem_unitOfList {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List α} {k : α} : k ∈ unitOfList l ↔ l.contains k = true

@[simp]

theorem Std.HashMap.getElem?_unitOfList {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List α} {k : α} : (unitOfList l)[k]? = if l.contains k = true then some () else none

@[simp]

theorem Std.HashMap.getElem_unitOfList {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {l : List α} {k : α} {h : k ∈ unitOfList l} : (unitOfList l)[k] = ()

@[simp]

theorem Std.HashMap.getElem!_unitOfList {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {l : List α} {k : α} : (unitOfList l)[k]! = ()

@[simp]

theorem Std.HashMap.getD_unitOfList {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {l : List α} {k : α} {fallback : Unit} : (unitOfList l).getD k fallback = ()

theorem Std.HashMap.getKey?_unitOfList_of_contains_eq_false {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List α} {k : α} (contains_eq_false : l.contains k = false) : (unitOfList l).getKey? k = none

theorem Std.HashMap.getKey?_unitOfList_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List α} {k k' : α} (k_beq : (k == k') = true) (distinct : List.Pairwise (fun (a b : α) => (a == b) = false) l) (mem : k ∈ l) : (unitOfList l).getKey? k' = some k

theorem Std.HashMap.getKey_unitOfList_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List α} {k k' : α} (k_beq : (k == k') = true) (distinct : List.Pairwise (fun (a b : α) => (a == b) = false) l) (mem : k ∈ l) {h : k' ∈ unitOfList l} : (unitOfList l).getKey k' h = k

theorem Std.HashMap.getKey!_unitOfList_of_contains_eq_false {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {l : List α} {k : α} (contains_eq_false : l.contains k = false) : (unitOfList l).getKey! k = default

theorem Std.HashMap.getKey!_unitOfList_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] [Inhabited α] {l : List α} {k k' : α} (k_beq : (k == k') = true) (distinct : List.Pairwise (fun (a b : α) => (a == b) = false) l) (mem : k ∈ l) : (unitOfList l).getKey! k' = k

theorem Std.HashMap.getKeyD_unitOfList_of_contains_eq_false {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List α} {k fallback : α} (contains_eq_false : l.contains k = false) : (unitOfList l).getKeyD k fallback = fallback

theorem Std.HashMap.getKeyD_unitOfList_of_mem {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List α} {k k' fallback : α} (k_beq : (k == k') = true) (distinct : List.Pairwise (fun (a b : α) => (a == b) = false) l) (mem : k ∈ l) : (unitOfList l).getKeyD k' fallback = k

theorem Std.HashMap.size_unitOfList {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List α} (distinct : List.Pairwise (fun (a b : α) => (a == b) = false) l) : (unitOfList l).size = l.length

theorem Std.HashMap.size_unitOfList_le {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List α} : (unitOfList l).size ≤ l.length

@[simp]

theorem Std.HashMap.isEmpty_unitOfList {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {l : List α} : (unitOfList l).isEmpty = l.isEmpty

theorem Std.HashMap.isEmpty_alter_eq_isEmpty_erase {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {f : Option β → Option β} : (m.alter k f).isEmpty = ((m.erase k).isEmpty && (f m[k]?).isNone)

@[simp]

theorem Std.HashMap.isEmpty_alter {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {f : Option β → Option β} : (m.alter k f).isEmpty = ((m.isEmpty || m.size == 1 && m.contains k) && (f m[k]?).isNone)

theorem Std.HashMap.contains_alter {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k k' : α} {f : Option β → Option β} : (m.alter k f).contains k' = if (k == k') = true then (f m[k]?).isSome else m.contains k'

theorem Std.HashMap.mem_alter {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k k' : α} {f : Option β → Option β} : k' ∈ m.alter k f ↔ if (k == k') = true then (f m[k]?).isSome = true else k' ∈ m

theorem Std.HashMap.mem_alter_of_beq {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k k' : α} {f : Option β → Option β} (h : (k == k') = true) : k' ∈ m.alter k f ↔ (f m[k]?).isSome = true

@[simp]

theorem Std.HashMap.contains_alter_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {f : Option β → Option β} : (m.alter k f).contains k = (f m[k]?).isSome

@[simp]

theorem Std.HashMap.mem_alter_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {f : Option β → Option β} : k ∈ m.alter k f ↔ (f m[k]?).isSome = true

theorem Std.HashMap.contains_alter_of_beq_eq_false {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k k' : α} {f : Option β → Option β} (h : (k == k') = false) : (m.alter k f).contains k' = m.contains k'

theorem Std.HashMap.mem_alter_of_beq_eq_false {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k k' : α} {f : Option β → Option β} (h : (k == k') = false) : k' ∈ m.alter k f ↔ k' ∈ m

theorem Std.HashMap.size_alter {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {f : Option β → Option β} : (m.alter k f).size = if k ∈ m ∧ (f m[k]?).isNone = true then m.size - 1 else if ¬k ∈ m ∧ (f m[k]?).isSome = true then m.size + 1 else m.size

theorem Std.HashMap.size_alter_eq_add_one {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {f : Option β → Option β} (h : ¬k ∈ m) (h' : (f m[k]?).isSome = true) : (m.alter k f).size = m.size + 1

theorem Std.HashMap.size_alter_eq_sub_one {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {f : Option β → Option β} (h : k ∈ m) (h' : (f m[k]?).isNone = true) : (m.alter k f).size = m.size - 1

theorem Std.HashMap.size_alter_eq_self_of_not_mem {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {f : Option β → Option β} (h : ¬k ∈ m) (h' : (f m[k]?).isNone = true) : (m.alter k f).size = m.size

theorem Std.HashMap.size_alter_eq_self_of_mem {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {f : Option β → Option β} (h : k ∈ m) (h' : (f m[k]?).isSome = true) : (m.alter k f).size = m.size

theorem Std.HashMap.size_alter_le_size {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {f : Option β → Option β} : (m.alter k f).size ≤ m.size + 1

theorem Std.HashMap.size_le_size_alter {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {f : Option β → Option β} : m.size - 1 ≤ (m.alter k f).size

theorem Std.HashMap.getElem?_alter {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k k' : α} {f : Option β → Option β} : (m.alter k f)[k']? = if (k == k') = true then f m[k]? else m[k']?

@[deprecated Std.HashMap.getElem?_alter (since := "2025-02-09")]

theorem Std.HashMap.get?_alter {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k k' : α} {f : Option β → Option β} : (m.alter k f).get? k' = if (k == k') = true then f (m.get? k) else m.get? k'

@[simp]

theorem Std.HashMap.getElem?_alter_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {f : Option β → Option β} : (m.alter k f)[k]? = f m[k]?

@[deprecated Std.HashMap.getElem?_alter_self (since := "2025-02-09")]

theorem Std.HashMap.get?_alter_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {f : Option β → Option β} : (m.alter k f).get? k = f (m.get? k)

theorem Std.HashMap.getElem_alter {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k k' : α} {f : Option β → Option β} {h : k' ∈ m.alter k f} : (m.alter k f)[k'] = if heq : (k == k') = true then (f m[k]?).get ⋯ else m[k']

@[deprecated Std.HashMap.getElem_alter (since := "2025-02-09")]

theorem Std.HashMap.get_alter {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k k' : α} {f : Option β → Option β} {h : k' ∈ m.alter k f} : (m.alter k f).get k' h = if heq : (k == k') = true then (f (m.get? k)).get ⋯ else m.get k' ⋯

@[simp]

theorem Std.HashMap.getElem_alter_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {f : Option β → Option β} {h : k ∈ m.alter k f} : (m.alter k f)[k] = (f m[k]?).get ⋯

@[deprecated Std.HashMap.getElem_alter_self (since := "2025-02-09")]

theorem Std.HashMap.get_alter_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {f : Option β → Option β} {h : k ∈ m.alter k f} : (m.alter k f).get k h = (f (m.get? k)).get ⋯

theorem Std.HashMap.getElem!_alter {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k k' : α} [Inhabited β] {f : Option β → Option β} : (m.alter k f)[k']! = if (k == k') = true then (f m[k]?).get! else m[k']!

@[deprecated Std.HashMap.getElem!_alter (since := "2025-02-09")]

theorem Std.HashMap.get!_alter {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k k' : α} [Inhabited β] {f : Option β → Option β} : (m.alter k f).get! k' = if (k == k') = true then (f (m.get? k)).get! else m.get! k'

@[simp]

theorem Std.HashMap.getElem!_alter_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} [Inhabited β] {f : Option β → Option β} : (m.alter k f)[k]! = (f m[k]?).get!

@[deprecated Std.HashMap.getElem!_alter_self (since := "2025-02-09")]

theorem Std.HashMap.get!_alter_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} [Inhabited β] {f : Option β → Option β} : (m.alter k f).get! k = (f (m.get? k)).get!

theorem Std.HashMap.getD_alter {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k k' : α} {fallback : β} {f : Option β → Option β} : (m.alter k f).getD k' fallback = if (k == k') = true then (f m[k]?).getD fallback else m.getD k' fallback

@[simp]

theorem Std.HashMap.getD_alter_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {fallback : β} {f : Option β → Option β} : (m.alter k f).getD k fallback = (f m[k]?).getD fallback

theorem Std.HashMap.getKey?_alter {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k k' : α} {f : Option β → Option β} : (m.alter k f).getKey? k' = if (k == k') = true then if (f m[k]?).isSome = true then some k else none else m.getKey? k'

theorem Std.HashMap.getKey?_alter_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {f : Option β → Option β} : (m.alter k f).getKey? k = if (f m[k]?).isSome = true then some k else none

theorem Std.HashMap.getKey!_alter {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited α] {k k' : α} {f : Option β → Option β} : (m.alter k f).getKey! k' = if (k == k') = true then if (f m[k]?).isSome = true then k else default else m.getKey! k'

theorem Std.HashMap.getKey!_alter_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited α] {k : α} {f : Option β → Option β} : (m.alter k f).getKey! k = if (f m[k]?).isSome = true then k else default

theorem Std.HashMap.getKey_alter {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited α] {k k' : α} {f : Option β → Option β} {h : k' ∈ m.alter k f} : (m.alter k f).getKey k' h = if heq : (k == k') = true then k else m.getKey k' ⋯

@[simp]

theorem Std.HashMap.getKey_alter_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited α] {k : α} {f : Option β → Option β} {h : k ∈ m.alter k f} : (m.alter k f).getKey k h = k

theorem Std.HashMap.getKeyD_alter {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k k' fallback : α} {f : Option β → Option β} : (m.alter k f).getKeyD k' fallback = if (k == k') = true then if (f m[k]?).isSome = true then k else fallback else m.getKeyD k' fallback

theorem Std.HashMap.getKeyD_alter_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited α] {k fallback : α} {f : Option β → Option β} : (m.alter k f).getKeyD k fallback = if (f m[k]?).isSome = true then k else fallback

@[simp]

theorem Std.HashMap.isEmpty_modify {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {f : β → β} : (m.modify k f).isEmpty = m.isEmpty

@[simp]

theorem Std.HashMap.contains_modify {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k k' : α} {f : β → β} : (m.modify k f).contains k' = m.contains k'

@[simp]

theorem Std.HashMap.mem_modify {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k k' : α} {f : β → β} : k' ∈ m.modify k f ↔ k' ∈ m

@[simp]

theorem Std.HashMap.size_modify {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {f : β → β} : (m.modify k f).size = m.size

theorem Std.HashMap.getElem?_modify {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k k' : α} {f : β → β} : (m.modify k f)[k']? = if (k == k') = true then Option.map f m[k]? else m[k']?

@[deprecated Std.HashMap.getElem?_modify (since := "2025-02-09")]

theorem Std.HashMap.get?_modify {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k k' : α} {f : β → β} : (m.modify k f).get? k' = if (k == k') = true then Option.map f (m.get? k) else m.get? k'

@[simp]

theorem Std.HashMap.getElem?_modify_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {f : β → β} : (m.modify k f)[k]? = Option.map f m[k]?

@[deprecated Std.HashMap.getElem?_modify_self (since := "2025-02-09")]

theorem Std.HashMap.get?_modify_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {f : β → β} : (m.modify k f).get? k = Option.map f (m.get? k)

theorem Std.HashMap.getElem_modify {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k k' : α} {f : β → β} {h : k' ∈ m.modify k f} : (m.modify k f)[k'] = if heq : (k == k') = true then f m[k] else m[k']

@[deprecated Std.HashMap.getElem_modify (since := "2025-02-09")]

theorem Std.HashMap.get_modify {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k k' : α} {f : β → β} {h : k' ∈ m.modify k f} : (m.modify k f).get k' h = if heq : (k == k') = true then f (m.get k ⋯) else m.get k' ⋯

@[simp]

theorem Std.HashMap.getElem_modify_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {f : β → β} {h : k ∈ m.modify k f} : (m.modify k f)[k] = f m[k]

@[deprecated Std.HashMap.getElem_modify_self (since := "2025-02-09")]

theorem Std.HashMap.get_modify_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {f : β → β} {h : k ∈ m.modify k f} : (m.modify k f).get k h = f (m.get k ⋯)

theorem Std.HashMap.getElem!_modify {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k k' : α} [Inhabited β] {f : β → β} : (m.modify k f)[k']! = if (k == k') = true then (Option.map f m[k]?).get! else m[k']!

@[deprecated Std.HashMap.getElem!_modify (since := "2025-02-09")]

theorem Std.HashMap.get!_modify {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k k' : α} [Inhabited β] {f : β → β} : (m.modify k f).get! k' = if (k == k') = true then (Option.map f (m.get? k)).get! else m.get! k'

@[simp]

theorem Std.HashMap.getElem!_modify_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} [Inhabited β] {f : β → β} : (m.modify k f)[k]! = (Option.map f m[k]?).get!

@[deprecated Std.HashMap.getElem!_modify_self (since := "2025-02-09")]

theorem Std.HashMap.get!_modify_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} [Inhabited β] {f : β → β} : (m.modify k f).get! k = (Option.map f (m.get? k)).get!

theorem Std.HashMap.getD_modify {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k k' : α} {fallback : β} {f : β → β} : (m.modify k f).getD k' fallback = if (k == k') = true then (Option.map f m[k]?).getD fallback else m.getD k' fallback

@[simp]

theorem Std.HashMap.getD_modify_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {fallback : β} {f : β → β} : (m.modify k f).getD k fallback = (Option.map f m[k]?).getD fallback

theorem Std.HashMap.getKey?_modify {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k k' : α} {f : β → β} : (m.modify k f).getKey? k' = if (k == k') = true then if k ∈ m then some k else none else m.getKey? k'

theorem Std.HashMap.getKey?_modify_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {f : β → β} : (m.modify k f).getKey? k = if k ∈ m then some k else none

theorem Std.HashMap.getKey!_modify {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited α] {k k' : α} {f : β → β} : (m.modify k f).getKey! k' = if (k == k') = true then if k ∈ m then k else default else m.getKey! k'

theorem Std.HashMap.getKey!_modify_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited α] {k : α} {f : β → β} : (m.modify k f).getKey! k = if k ∈ m then k else default

theorem Std.HashMap.getKey_modify {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited α] {k k' : α} {f : β → β} {h : k' ∈ m.modify k f} : (m.modify k f).getKey k' h = if (k == k') = true then k else m.getKey k' ⋯

@[simp]

theorem Std.HashMap.getKey_modify_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited α] {k : α} {f : β → β} {h : k ∈ m.modify k f} : (m.modify k f).getKey k h = k

theorem Std.HashMap.getKeyD_modify {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {k k' fallback : α} {f : β → β} : (m.modify k f).getKeyD k' fallback = if (k == k') = true then if k ∈ m then k else fallback else m.getKeyD k' fallback

theorem Std.HashMap.getKeyD_modify_self {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited α] {k fallback : α} {f : β → β} : (m.modify k f).getKeyD k fallback = if k ∈ m then k else fallback

@[simp]

theorem Std.HashMap.Equiv.refl {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} (m : HashMap α β) : m.Equiv m

theorem Std.HashMap.Equiv.rfl {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} : m.Equiv m

theorem Std.HashMap.Equiv.symm {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashMap α β} : m₁.Equiv m₂ → m₂.Equiv m₁

theorem Std.HashMap.Equiv.trans {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ m₃ : HashMap α β} : m₁.Equiv m₂ → m₂.Equiv m₃ → m₁.Equiv m₃

instance Std.HashMap.Equiv.instTrans {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} : Trans Equiv Equiv Equiv

Equations

• Std.HashMap.Equiv.instTrans = { trans := ⋯ }

theorem Std.HashMap.Equiv.comm {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashMap α β} : m₁.Equiv m₂ ↔ m₂.Equiv m₁

theorem Std.HashMap.Equiv.congr_left {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ m₃ : HashMap α β} (h : m₁.Equiv m₂) : m₁.Equiv m₃ ↔ m₂.Equiv m₃

theorem Std.HashMap.Equiv.congr_right {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ m₃ : HashMap α β} (h : m₁.Equiv m₂) : m₃.Equiv m₁ ↔ m₃.Equiv m₂

theorem Std.HashMap.Equiv.isEmpty_eq {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashMap α β} [EquivBEq α] [LawfulHashable α] (h : m₁.Equiv m₂) : m₁.isEmpty = m₂.isEmpty

theorem Std.HashMap.Equiv.size_eq {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashMap α β} [EquivBEq α] [LawfulHashable α] (h : m₁.Equiv m₂) : m₁.size = m₂.size

theorem Std.HashMap.Equiv.contains_eq {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} (h : m₁.Equiv m₂) : m₁.contains k = m₂.contains k

theorem Std.HashMap.Equiv.mem_iff {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} (h : m₁.Equiv m₂) : k ∈ m₁ ↔ k ∈ m₂

theorem Std.HashMap.Equiv.toList_perm {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashMap α β} (h : m₁.Equiv m₂) : m₁.toList.Perm m₂.toList

theorem Std.HashMap.Equiv.of_toList_perm {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashMap α β} (h : m₁.toList.Perm m₂.toList) : m₁.Equiv m₂

theorem Std.HashMap.Equiv.keys_perm {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashMap α β} (h : m₁.Equiv m₂) : m₁.keys.Perm m₂.keys

theorem Std.HashMap.Equiv.of_keys_unit_perm {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashMap α Unit} (h : m₁.keys.Perm m₂.keys) : m₁.Equiv m₂

theorem Std.HashMap.Equiv.getElem?_eq {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} (h : m₁.Equiv m₂) : m₁[k]? = m₂[k]?

theorem Std.HashMap.Equiv.getElem_eq {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} (hk : k ∈ m₁) (h : m₁.Equiv m₂) : m₁[k] = m₂[k]

theorem Std.HashMap.Equiv.getElem!_eq {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} [Inhabited β] (h : m₁.Equiv m₂) : m₁[k]! = m₂[k]!

theorem Std.HashMap.Equiv.getD_eq {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} {fallback : β} (h : m₁.Equiv m₂) : m₁.getD k fallback = m₂.getD k fallback

theorem Std.HashMap.Equiv.getKey?_eq {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} (h : m₁.Equiv m₂) : m₁.getKey? k = m₂.getKey? k

theorem Std.HashMap.Equiv.getKey_eq {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashMap α β} [EquivBEq α] [LawfulHashable α] {k : α} (hk : k ∈ m₁) (h : m₁.Equiv m₂) : m₁.getKey k hk = m₂.getKey k ⋯

theorem Std.HashMap.Equiv.getKey!_eq {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited α] {k : α} (h : m₁.Equiv m₂) : m₁.getKey! k = m₂.getKey! k

theorem Std.HashMap.Equiv.getKeyD_eq {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashMap α β} [EquivBEq α] [LawfulHashable α] {k fallback : α} (h : m₁.Equiv m₂) : m₁.getKeyD k fallback = m₂.getKeyD k fallback

theorem Std.HashMap.Equiv.insert {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashMap α β} [EquivBEq α] [LawfulHashable α] (k : α) (v : β) (h : m₁.Equiv m₂) : (m₁.insert k v).Equiv (m₂.insert k v)

theorem Std.HashMap.Equiv.erase {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashMap α β} [EquivBEq α] [LawfulHashable α] (k : α) (h : m₁.Equiv m₂) : (m₁.erase k).Equiv (m₂.erase k)

theorem Std.HashMap.Equiv.insertIfNew {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashMap α β} [EquivBEq α] [LawfulHashable α] (k : α) (v : β) (h : m₁.Equiv m₂) : (m₁.insertIfNew k v).Equiv (m₂.insertIfNew k v)

theorem Std.HashMap.Equiv.insertMany_list {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashMap α β} [EquivBEq α] [LawfulHashable α] (l : List (α × β)) (h : m₁.Equiv m₂) : (m₁.insertMany l).Equiv (m₂.insertMany l)

theorem Std.HashMap.Equiv.insertManyIfNewUnit_list {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {m₁ m₂ : HashMap α Unit} (l : List α) (h : m₁.Equiv m₂) : (m₁.insertManyIfNewUnit l).Equiv (m₂.insertManyIfNewUnit l)

theorem Std.HashMap.Equiv.alter {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashMap α β} [EquivBEq α] [LawfulHashable α] (k : α) (f : Option β → Option β) (h : m₁.Equiv m₂) : (m₁.alter k f).Equiv (m₂.alter k f)

theorem Std.HashMap.Equiv.modify {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashMap α β} [EquivBEq α] [LawfulHashable α] (k : α) (f : β → β) (h : m₁.Equiv m₂) : (m₁.modify k f).Equiv (m₂.modify k f)

theorem Std.HashMap.Equiv.filter {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashMap α β} (f : α → β → Bool) (h : m₁.Equiv m₂) : (HashMap.filter f m₁).Equiv (HashMap.filter f m₂)

theorem Std.HashMap.Equiv.map {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashMap α β} (f : α → β → γ) (h : m₁.Equiv m₂) : (HashMap.map f m₁).Equiv (HashMap.map f m₂)

theorem Std.HashMap.Equiv.filterMap {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashMap α β} (f : α → β → Option γ) (h : m₁.Equiv m₂) : (HashMap.filterMap f m₁).Equiv (HashMap.filterMap f m₂)

theorem Std.HashMap.Equiv.of_forall_getKey_eq_of_forall_getElem?_eq {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashMap α β} [EquivBEq α] [LawfulHashable α] (hk : ∀ (k : α) (hk : k ∈ m₁) (hk' : k ∈ m₂), m₁.getKey k hk = m₂.getKey k hk') (hv : ∀ (k : α), m₁[k]? = m₂[k]?) : m₁.Equiv m₂

@[deprecated Std.HashMap.Equiv.of_forall_getKey_eq_of_forall_getElem?_eq (since := "2025-04-25")]

theorem Std.HashMap.Equiv.of_forall_getKey?_eq_of_forall_getElem?_eq {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashMap α β} [EquivBEq α] [LawfulHashable α] (hk : ∀ (k : α), m₁.getKey? k = m₂.getKey? k) (hv : ∀ (k : α), m₁[k]? = m₂[k]?) : m₁.Equiv m₂

theorem Std.HashMap.Equiv.of_forall_getElem?_eq {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashMap α β} [LawfulBEq α] (h : ∀ (k : α), m₁[k]? = m₂[k]?) : m₁.Equiv m₂

theorem Std.HashMap.Equiv.of_forall_getKey?_unit_eq {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [EquivBEq α] [LawfulHashable α] {m₁ m₂ : HashMap α Unit} (h : ∀ (k : α), m₁.getKey? k = m₂.getKey? k) : m₁.Equiv m₂

theorem Std.HashMap.Equiv.of_forall_contains_unit_eq {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [LawfulBEq α] {m₁ m₂ : HashMap α Unit} (h : ∀ (k : α), m₁.contains k = m₂.contains k) : m₁.Equiv m₂

theorem Std.HashMap.Equiv.of_forall_mem_unit_iff {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} [LawfulBEq α] {m₁ m₂ : HashMap α Unit} (h : ∀ (k : α), k ∈ m₁ ↔ k ∈ m₂) : m₁.Equiv m₂

@[simp]

theorem Std.HashMap.equiv_emptyWithCapacity_iff_isEmpty {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {c : Nat} : m.Equiv (emptyWithCapacity c) ↔ m.isEmpty = true

@[simp]

theorem Std.HashMap.equiv_empty_iff_isEmpty {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] : m.Equiv ∅ ↔ m.isEmpty = true

@[reducible, inline, deprecated Std.HashMap.equiv_empty_iff_isEmpty (since := "2025-03-12")]

abbrev Std.HashMap.equiv_emptyc_iff_isEmpty {α : Type u_1} {β : Type u_2} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] : m.Equiv ∅ ↔ m.isEmpty = true

Equations

• @Std.HashMap.equiv_emptyc_iff_isEmpty = @Std.HashMap.equiv_empty_iff_isEmpty

@[simp]

theorem Std.HashMap.emptyWithCapacity_equiv_iff_isEmpty {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {c : Nat} : (emptyWithCapacity c).Equiv m ↔ m.isEmpty = true

@[simp]

theorem Std.HashMap.empty_equiv_iff_isEmpty {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] : ∅.Equiv m ↔ m.isEmpty = true

@[reducible, inline, deprecated Std.HashMap.empty_equiv_iff_isEmpty (since := "2025-03-12")]

abbrev Std.HashMap.emptyc_equiv_iff_isEmpty {α : Type u_1} {β : Type u_2} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] : ∅.Equiv m ↔ m.isEmpty = true

Equations

• @Std.HashMap.emptyc_equiv_iff_isEmpty = @Std.HashMap.empty_equiv_iff_isEmpty

theorem Std.HashMap.equiv_iff_toList_perm {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashMap α β} [EquivBEq α] [LawfulHashable α] : m₁.Equiv m₂ ↔ m₁.toList.Perm m₂.toList

theorem Std.HashMap.equiv_iff_keys_unit_perm {α : Type u} {x✝ : BEq α} {x✝¹ : Hashable α} {m₁ m₂ : HashMap α Unit} [EquivBEq α] [LawfulHashable α] : m₁.Equiv m₂ ↔ m₁.keys.Perm m₂.keys

theorem Std.HashMap.toList_filterMap {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {f : α → β → Option γ} : (filterMap f m).toList.Perm (List.filterMap (fun (p : α × β) => Option.map (fun (x : γ) => (p.fst, x)) (f p.fst p.snd)) m.toList)

theorem Std.HashMap.isEmpty_filterMap_iff {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Option γ} : (filterMap f m).isEmpty = true ↔ ∀ (k : α) (h : k ∈ m), f (m.getKey k h) m[k] = none

theorem Std.HashMap.isEmpty_filterMap_eq_false_iff {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Option γ} : (filterMap f m).isEmpty = false ↔ ∃ (k : α), ∃ (h : k ∈ m), (f (m.getKey k h) m[k]).isSome = true

theorem Std.HashMap.mem_filterMap {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Option γ} {k : α} : k ∈ filterMap f m ↔ ∃ (h : k ∈ m), (f (m.getKey k h) m[k]).isSome = true

theorem Std.HashMap.contains_of_contains_filterMap {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Option γ} {k : α} : (filterMap f m).contains k = true → m.contains k = true

theorem Std.HashMap.mem_of_mem_filterMap {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Option γ} {k : α} : k ∈ filterMap f m → k ∈ m

theorem Std.HashMap.size_filterMap_le_size {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Option γ} : (filterMap f m).size ≤ m.size

theorem Std.HashMap.size_filterMap_eq_size_iff {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Option γ} : (filterMap f m).size = m.size ↔ ∀ (k : α) (h : k ∈ m), (f (m.getKey k h) m[k]).isSome = true

@[simp]

theorem Std.HashMap.getElem?_filterMap {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Option γ} {k : α} : (filterMap f m)[k]? = m[k]?.pbind fun (x : β) (h' : m[k]? = some x) => f (m.getKey k ⋯) x

theorem Std.HashMap.getElem?_filterMap' {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [LawfulBEq α] {f : α → β → Option γ} {k : α} : (filterMap f m)[k]? = m[k]?.bind fun (x : β) => f k x

Simpler variant of getElem?_filterMap when LawfulBEq is available.

theorem Std.HashMap.getElem?_filterMap_of_getKey?_eq_some {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Option γ} {k k' : α} (h : m.getKey? k = some k') : (filterMap f m)[k]? = m[k]?.bind (f k')

theorem Std.HashMap.isSome_apply_of_mem_filterMap {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Option γ} {k : α} (h : k ∈ filterMap f m) : (f (m.getKey k ⋯) m[k]).isSome = true

@[simp]

theorem Std.HashMap.getElem_filterMap {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Option γ} {k : α} {h : k ∈ filterMap f m} : (filterMap f m)[k] = (f (m.getKey k ⋯) m[k]).get ⋯

theorem Std.HashMap.getElem_filterMap' {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [LawfulBEq α] {f : α → β → Option γ} {k : α} {h : k ∈ filterMap f m} : (filterMap f m)[k] = (f k m[k]).get ⋯

Simpler variant of getElem_filterMap when LawfulBEq is available.

theorem Std.HashMap.getElem!_filterMap {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited γ] {f : α → β → Option γ} {k : α} : (filterMap f m)[k]! = (m[k]?.pbind fun (x : β) (h' : m[k]? = some x) => f (m.getKey k ⋯) x).get!

theorem Std.HashMap.getElem!_filterMap' {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [LawfulBEq α] [Inhabited γ] {f : α → β → Option γ} {k : α} : (filterMap f m)[k]! = (m[k]?.bind (f k)).get!

Simpler variant of getElem!_filterMap when LawfulBEq is available.

theorem Std.HashMap.getElem!_filterMap_of_getKey?_eq_some {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited γ] {f : α → β → Option γ} {k k' : α} (h : m.getKey? k = some k') : (filterMap f m)[k]! = (m[k]?.bind (f k')).get!

theorem Std.HashMap.getD_filterMap {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Option γ} {k : α} {fallback : γ} : (filterMap f m).getD k fallback = (m[k]?.pbind fun (x : β) (h' : m[k]? = some x) => f (m.getKey k ⋯) x).getD fallback

theorem Std.HashMap.getD_filterMap' {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [LawfulBEq α] {f : α → β → Option γ} {k : α} {fallback : γ} : (filterMap f m).getD k fallback = (m[k]?.bind (f k)).getD fallback

Simpler variant of getD_filterMap when LawfulBEq is available.

theorem Std.HashMap.getD_filterMap_of_getKey?_eq_some {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Option γ} {k k' : α} {fallback : γ} (h : m.getKey? k = some k') : (filterMap f m).getD k fallback = (m[k]?.bind (f k')).getD fallback

theorem Std.HashMap.getKey?_filterMap {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Option γ} {k : α} : (filterMap f m).getKey? k = (m.getKey? k).pfilter fun (x : α) (h' : m.getKey? k = some x) => (f x m[x]).isSome

@[simp]

theorem Std.HashMap.getKey_filterMap {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Option γ} {k : α} {h' : k ∈ filterMap f m} : (filterMap f m).getKey k h' = m.getKey k ⋯

theorem Std.HashMap.getKey!_filterMap {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited α] {f : α → β → Option γ} {k : α} : (filterMap f m).getKey! k = ((m.getKey? k).pfilter fun (x : α) (h' : m.getKey? k = some x) => (f x m[x]).isSome).get!

theorem Std.HashMap.getKeyD_filterMap {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Option γ} {k fallback : α} : (filterMap f m).getKeyD k fallback = ((m.getKey? k).pfilter fun (x : α) (h' : m.getKey? k = some x) => (f x m[x]).isSome).getD fallback

theorem Std.HashMap.filterMap_equiv_filter {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {f : α → β → Bool} : (filterMap (fun (k : α) => Option.guard fun (v : β) => f k v) m).Equiv (filter f m)

theorem Std.HashMap.toList_filter {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {f : α → β → Bool} : (filter f m).toList.Perm (List.filter (fun (p : α × β) => f p.fst p.snd) m.toList)

theorem Std.HashMap.keys_filter_key {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {f : α → Bool} : (filter (fun (k : α) (x : β) => f k) m).keys.Perm (List.filter f m.keys)

theorem Std.HashMap.isEmpty_filter_iff {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Bool} : (filter f m).isEmpty = true ↔ ∀ (k : α) (h : k ∈ m), f (m.getKey k h) m[k] = false

theorem Std.HashMap.isEmpty_filter_eq_false_iff {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Bool} : (filter f m).isEmpty = false ↔ ∃ (k : α), ∃ (h : k ∈ m), f (m.getKey k h) m[k] = true

theorem Std.HashMap.mem_filter {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Bool} {k : α} : k ∈ filter f m ↔ ∃ (h' : k ∈ m), f (m.getKey k h') m[k] = true

theorem Std.HashMap.contains_of_contains_filter {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Bool} {k : α} : (filter f m).contains k = true → m.contains k = true

theorem Std.HashMap.mem_of_mem_filter {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Bool} {k : α} : k ∈ filter f m → k ∈ m

theorem Std.HashMap.size_filter_le_size {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Bool} : (filter f m).size ≤ m.size

theorem Std.HashMap.size_filter_eq_size_iff {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Bool} : (filter f m).size = m.size ↔ ∀ (k : α) (h : k ∈ m), f (m.getKey k h) (m.get k h) = true

theorem Std.HashMap.filter_equiv_self_iff {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Bool} : (filter f m).Equiv m ↔ ∀ (k : α) (h : k ∈ m), f (m.getKey k h) (m.get k h) = true

@[simp]

theorem Std.HashMap.getElem?_filter {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Bool} {k : α} : (filter f m)[k]? = m[k]?.pfilter fun (x : β) (h' : m[k]? = some x) => f (m.getKey k ⋯) x

theorem Std.HashMap.getElem?_filter' {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [LawfulBEq α] {f : α → β → Bool} {k : α} : (filter f m)[k]? = Option.filter (f k) m[k]?

Simpler variant of getElem?_filter when LawfulBEq is available.

theorem Std.HashMap.getElem?_filter_of_getKey?_eq_some {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Bool} {k k' : α} : m.getKey? k = some k' → (filter f m)[k]? = Option.filter (fun (x : β) => f k' x) m[k]?

@[simp]

theorem Std.HashMap.getElem_filter {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Bool} {k : α} {h' : k ∈ filter f m} : (filter f m)[k] = m[k]

theorem Std.HashMap.getElem!_filter {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited β] {f : α → β → Bool} {k : α} : (filter f m)[k]! = (m[k]?.pfilter fun (x : β) (h' : m[k]? = some x) => f (m.getKey k ⋯) x).get!

theorem Std.HashMap.getElem!_filter' {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [LawfulBEq α] [Inhabited β] {f : α → β → Bool} {k : α} : (filter f m)[k]! = (Option.filter (f k) m[k]?).get!

Simpler variant of getElem!_filter when LawfulBEq is available.

theorem Std.HashMap.getElem!_filter_of_getKey?_eq_some {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited β] {f : α → β → Bool} {k k' : α} : m.getKey? k = some k' → (filter f m)[k]! = (Option.filter (f k') m[k]?).get!

theorem Std.HashMap.getD_filter {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Bool} {k : α} {fallback : β} : (filter f m).getD k fallback = (m[k]?.pfilter fun (x : β) (h' : m[k]? = some x) => f (m.getKey k ⋯) x).getD fallback

theorem Std.HashMap.getD_filter' {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [LawfulBEq α] {f : α → β → Bool} {k : α} {fallback : β} : (filter f m).getD k fallback = (Option.filter (f k) m[k]?).getD fallback

Simpler variant of getD_filter when LawfulBEq is available.

theorem Std.HashMap.getD_filter_of_getKey?_eq_some {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Bool} {k k' : α} {fallback : β} : m.getKey? k = some k' → (filter f m).getD k fallback = (Option.filter (fun (x : β) => f k' x) m[k]?).getD fallback

theorem Std.HashMap.keys_filter {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Bool} : (filter f m).keys.Perm (List.filter (fun (x : { x : α // x ∈ m.keys }) => match x with | ⟨x, h'⟩ => f x (m.get x ⋯)) m.keys.attach).unattach

theorem Std.HashMap.getKey?_filter {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Bool} {k : α} : (filter f m).getKey? k = (m.getKey? k).pfilter fun (x : α) (h' : m.getKey? k = some x) => f x m[x]

theorem Std.HashMap.getKey?_filter_key {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → Bool} {k : α} : (filter (fun (k : α) (x : β) => f k) m).getKey? k = Option.filter f (m.getKey? k)

@[simp]

theorem Std.HashMap.getKey_filter {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Bool} {k : α} {h' : k ∈ filter f m} : (filter f m).getKey k h' = m.getKey k ⋯

theorem Std.HashMap.getKey!_filter {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited α] {f : α → β → Bool} {k : α} : (filter f m).getKey! k = ((m.getKey? k).pfilter fun (x : α) (h' : m.getKey? k = some x) => f x m[x]).get!

theorem Std.HashMap.getKey!_filter_key {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited α] {f : α → Bool} {k : α} : (filter (fun (k : α) (x : β) => f k) m).getKey! k = (Option.filter f (m.getKey? k)).get!

theorem Std.HashMap.getKeyD_filter {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → Bool} {k fallback : α} : (filter f m).getKeyD k fallback = ((m.getKey? k).pfilter fun (x : α) (h' : m.getKey? k = some x) => f x m[x]).getD fallback

theorem Std.HashMap.getKeyD_filter_key {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → Bool} {k fallback : α} : (filter (fun (k : α) (x : β) => f k) m).getKeyD k fallback = (Option.filter f (m.getKey? k)).getD fallback

theorem Std.HashMap.map_id_equiv {α : Type u} {β : Type v} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} : (map (fun (x : α) (v : β) => v) m).Equiv m

theorem Std.HashMap.map_map_equiv {α : Type u} {β : Type v} {γ : Type w} {δ : Type w'} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {f : α → β → γ} {g : α → γ → δ} : (map g (map f m)).Equiv (map (fun (k : α) (v : β) => g k (f k v)) m)

theorem Std.HashMap.toList_map {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {f : α → β → γ} : (map f m).toList.Perm (List.map (fun (p : α × β) => (p.fst, f p.fst p.snd)) m.toList)

theorem Std.HashMap.keys_map {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} {f : α → β → γ} : (map f m).keys.Perm m.keys

theorem Std.HashMap.filterMap_equiv_map {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → γ} : (filterMap (fun (k : α) (v : β) => some (f k v)) m).Equiv (map f m)

@[simp]

theorem Std.HashMap.isEmpty_map {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → γ} : (map f m).isEmpty = m.isEmpty

@[simp]

theorem Std.HashMap.contains_map {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → γ} {k : α} : (map f m).contains k = m.contains k

theorem Std.HashMap.contains_of_contains_map {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → γ} {k : α} : (map f m).contains k = true → m.contains k = true

@[simp]

theorem Std.HashMap.mem_map {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → γ} {k : α} : k ∈ map f m ↔ k ∈ m

theorem Std.HashMap.mem_of_mem_map {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → γ} {k : α} : k ∈ map f m → k ∈ m

@[simp]

theorem Std.HashMap.size_map {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → γ} : (map f m).size = m.size

@[simp]

theorem Std.HashMap.getElem?_map {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [LawfulBEq α] {f : α → β → γ} {k : α} : (map f m)[k]? = Option.map (f k) m[k]?

@[simp]

theorem Std.HashMap.getElem?_map' {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → γ} {k : α} : (map f m)[k]? = Option.pmap (fun (v : β) (h' : k ∈ m) => f (m.getKey k h') v) m[k]? ⋯

Variant of getElem?_map that holds with EquivBEq (i.e. without LawfulBEq).

theorem Std.HashMap.getElem?_map_of_getKey?_eq_some {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → γ} {k k' : α} (h : m.getKey? k = some k') : (map f m)[k]? = Option.map (f k') m[k]?

@[simp]

theorem Std.HashMap.getElem_map {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [LawfulBEq α] {f : α → β → γ} {k : α} {h' : k ∈ map f m} : (map f m)[k] = f k m[k]

@[simp]

theorem Std.HashMap.getElem_map' {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → γ} {k : α} {h' : k ∈ map f m} : (map f m)[k] = f (m.getKey k ⋯) m[k]

Variant of getElem_map that holds with EquivBEq (i.e. without LawfulBEq).

theorem Std.HashMap.getElem!_map {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [LawfulBEq α] [Inhabited γ] {f : α → β → γ} {k : α} : (map f m)[k]! = (Option.map (f k) m[k]?).get!

theorem Std.HashMap.getElem!_map' {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited γ] {f : α → β → γ} {k : α} : (map f m)[k]! = (Option.pmap (fun (v : β) (h : k ∈ m) => f (m.getKey k h) v) m[k]? ⋯).get!

Variant of getElem!_map that holds with EquivBEq (i.e. without LawfulBEq).

theorem Std.HashMap.getElem!_map_of_getKey?_eq_some {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited γ] {f : α → β → γ} {k k' : α} (h : m.getKey? k = some k') : (map f m)[k]! = (Option.map (f k') m[k]?).get!

theorem Std.HashMap.getD_map {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [LawfulBEq α] {f : α → β → γ} {k : α} {fallback : γ} : (map f m).getD k fallback = (Option.map (f k) m[k]?).getD fallback

theorem Std.HashMap.getD_map' {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → γ} {k : α} {fallback : γ} : (map f m).getD k fallback = (Option.pmap (fun (v : β) (h : k ∈ m) => f (m.getKey k h) v) m[k]? ⋯).getD fallback

Variant of getD_map that holds with EquivBEq (i.e. without LawfulBEq).

theorem Std.HashMap.getD_map_of_getKey?_eq_some {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited γ] {f : α → β → γ} {k k' : α} {fallback : γ} (h : m.getKey? k = some k') : (map f m).getD k fallback = (Option.map (f k') m[k]?).getD fallback

@[simp]

theorem Std.HashMap.getKey?_map {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → γ} {k : α} : (map f m).getKey? k = m.getKey? k

@[simp]

theorem Std.HashMap.getKey_map {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → γ} {k : α} {h' : k ∈ map f m} : (map f m).getKey k h' = m.getKey k ⋯

@[simp]

theorem Std.HashMap.getKey!_map {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] [Inhabited α] {f : α → β → γ} {k : α} : (map f m).getKey! k = m.getKey! k

@[simp]

theorem Std.HashMap.getKeyD_map {α : Type u} {β : Type v} {γ : Type w} {x✝ : BEq α} {x✝¹ : Hashable α} {m : HashMap α β} [EquivBEq α] [LawfulHashable α] {f : α → β → γ} {k fallback : α} : (map f m).getKeyD k fallback = m.getKeyD k fallback