blob: 972990cbef8485c4607c964449b7f36c83efd0c7 [file]
/-
Copyright (c) 2024 Lean FRO, LLC. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Markus Himmel
-/
prelude
import Std.Data.HashMap.Lemmas
import Std.Data.HashSet.Basic
/-!
# Hash set lemmas
This module contains lemmas about `Std.Data.HashSet`. 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 α`.
-/
set_option linter.missingDocs true
set_option autoImplicit false
universe u v
variable {α : Type u} {_ : BEq α} {_ : Hashable α}
namespace Std.HashSet
section
variable {m : HashSet α}
private theorem ext {m m' : HashSet α} : m.inner = m'.inner → m = m' := by
cases m; cases m'; rintro rfl; rfl
@[simp]
theorem isEmpty_empty {c} : (empty c : HashSet α).isEmpty :=
HashMap.isEmpty_empty
@[simp]
theorem isEmpty_emptyc : (∅ : HashSet α).isEmpty :=
HashMap.isEmpty_emptyc
@[simp]
theorem isEmpty_insert [EquivBEq α] [LawfulHashable α] {a : α} : (m.insert a).isEmpty = false :=
HashMap.isEmpty_insertIfNew
theorem mem_iff_contains {a : α} : a ∈ m ↔ m.contains a :=
HashMap.mem_iff_contains
theorem contains_congr [EquivBEq α] [LawfulHashable α] {a b : α} (hab : a == b) :
m.contains a = m.contains b :=
HashMap.contains_congr hab
theorem mem_congr [EquivBEq α] [LawfulHashable α] {a b : α} (hab : a == b) : a ∈ m ↔ b ∈ m :=
HashMap.mem_congr hab
@[simp] theorem contains_empty {a : α} {c} : (empty c : HashSet α).contains a = false :=
HashMap.contains_empty
@[simp] theorem not_mem_empty {a : α} {c} : ¬a ∈ (empty c : HashSet α) :=
HashMap.not_mem_empty
@[simp] theorem contains_emptyc {a : α} : (∅ : HashSet α).contains a = false :=
HashMap.contains_emptyc
@[simp] theorem not_mem_emptyc {a : α} : ¬a ∈ (∅ : HashSet α) :=
HashMap.not_mem_emptyc
theorem contains_of_isEmpty [EquivBEq α] [LawfulHashable α] {a : α} :
m.isEmpty → m.contains a = false :=
HashMap.contains_of_isEmpty
theorem not_mem_of_isEmpty [EquivBEq α] [LawfulHashable α] {a : α} :
m.isEmpty → ¬a ∈ m :=
HashMap.not_mem_of_isEmpty
theorem isEmpty_eq_false_iff_exists_contains_eq_true [EquivBEq α] [LawfulHashable α] :
m.isEmpty = false ↔ ∃ a, m.contains a = true :=
HashMap.isEmpty_eq_false_iff_exists_contains_eq_true
theorem isEmpty_eq_false_iff_exists_mem [EquivBEq α] [LawfulHashable α] :
m.isEmpty = false ↔ ∃ a, a ∈ m :=
HashMap.isEmpty_eq_false_iff_exists_mem
theorem isEmpty_iff_forall_contains [EquivBEq α] [LawfulHashable α] :
m.isEmpty = true ↔ ∀ a, m.contains a = false :=
HashMap.isEmpty_iff_forall_contains
theorem isEmpty_iff_forall_not_mem [EquivBEq α] [LawfulHashable α] :
m.isEmpty = true ↔ ∀ a, ¬a ∈ m :=
HashMap.isEmpty_iff_forall_not_mem
@[simp] theorem insert_eq_insert {a : α} : Insert.insert a m = m.insert a := rfl
@[simp] theorem singleton_eq_insert {a : α} : Singleton.singleton a = (∅ : HashSet α).insert a := rfl
@[simp]
theorem contains_insert [EquivBEq α] [LawfulHashable α] {k a : α} :
(m.insert k).contains a = (k == a || m.contains a) :=
HashMap.contains_insertIfNew
@[simp]
theorem mem_insert [EquivBEq α] [LawfulHashable α] {k a : α} : a ∈ m.insert k ↔ k == a ∨ a ∈ m :=
HashMap.mem_insertIfNew
theorem contains_of_contains_insert [EquivBEq α] [LawfulHashable α] {k a : α} :
(m.insert k).contains a → (k == a) = false → m.contains a :=
HashMap.contains_of_contains_insertIfNew
theorem mem_of_mem_insert [EquivBEq α] [LawfulHashable α] {k a : α} :
a ∈ m.insert k → (k == a) = false → a ∈ m :=
HashMap.mem_of_mem_insertIfNew
/-- This is a restatement of `contains_insert` that is written to exactly match the proof
obligation in the statement of `get_insert`. -/
theorem contains_of_contains_insert' [EquivBEq α] [LawfulHashable α] {k a : α} :
(m.insert k).contains a → ¬((k == a) ∧ m.contains k = false) → m.contains a :=
HashMap.contains_of_contains_insertIfNew'
/-- This is a restatement of `mem_insert` that is written to exactly match the proof obligation
in the statement of `get_insert`. -/
theorem mem_of_mem_insert' [EquivBEq α] [LawfulHashable α] {k a : α} :
a ∈ m.insert k → ¬((k == a) ∧ ¬k ∈ m) → a ∈ m :=
DHashMap.mem_of_mem_insertIfNew'
@[simp]
theorem contains_insert_self [EquivBEq α] [LawfulHashable α] {k : α} : (m.insert k).contains k :=
HashMap.contains_insertIfNew_self
@[simp]
theorem mem_insert_self [EquivBEq α] [LawfulHashable α] {k : α} : k ∈ m.insert k :=
HashMap.mem_insertIfNew_self
@[simp]
theorem size_empty {c} : (empty c : HashSet α).size = 0 :=
HashMap.size_empty
@[simp]
theorem size_emptyc : (∅ : HashSet α).size = 0 :=
HashMap.size_emptyc
theorem isEmpty_eq_size_eq_zero : m.isEmpty = (m.size == 0) :=
HashMap.isEmpty_eq_size_eq_zero
theorem size_insert [EquivBEq α] [LawfulHashable α] {k : α} :
(m.insert k).size = if k ∈ m then m.size else m.size + 1 :=
HashMap.size_insertIfNew
theorem size_le_size_insert [EquivBEq α] [LawfulHashable α] {k : α} : m.size ≤ (m.insert k).size :=
HashMap.size_le_size_insertIfNew
theorem size_insert_le [EquivBEq α] [LawfulHashable α] {k : α} :
(m.insert k).size ≤ m.size + 1 :=
HashMap.size_insertIfNew_le
@[simp]
theorem erase_empty {a : α} {c : Nat} : (empty c : HashSet α).erase a = empty c :=
ext HashMap.erase_empty
@[simp]
theorem erase_emptyc {a : α} : (∅ : HashSet α).erase a = ∅ :=
ext HashMap.erase_emptyc
@[simp]
theorem isEmpty_erase [EquivBEq α] [LawfulHashable α] {k : α} :
(m.erase k).isEmpty = (m.isEmpty || (m.size == 1 && m.contains k)) :=
HashMap.isEmpty_erase
@[simp]
theorem contains_erase [EquivBEq α] [LawfulHashable α] {k a : α} :
(m.erase k).contains a = (!(k == a) && m.contains a) :=
HashMap.contains_erase
@[simp]
theorem mem_erase [EquivBEq α] [LawfulHashable α] {k a : α} :
a ∈ m.erase k ↔ (k == a) = false ∧ a ∈ m :=
HashMap.mem_erase
theorem contains_of_contains_erase [EquivBEq α] [LawfulHashable α] {k a : α} :
(m.erase k).contains a → m.contains a :=
HashMap.contains_of_contains_erase
theorem mem_of_mem_erase [EquivBEq α] [LawfulHashable α] {k a : α} : a ∈ m.erase k → a ∈ m :=
HashMap.mem_of_mem_erase
theorem size_erase [EquivBEq α] [LawfulHashable α] {k : α} :
(m.erase k).size = if k ∈ m then m.size - 1 else m.size :=
HashMap.size_erase
theorem size_erase_le [EquivBEq α] [LawfulHashable α] {k : α} : (m.erase k).size ≤ m.size :=
HashMap.size_erase_le
theorem size_le_size_erase [EquivBEq α] [LawfulHashable α] {k : α} :
m.size ≤ (m.erase k).size + 1 :=
HashMap.size_le_size_erase
@[simp]
theorem get?_empty {a : α} {c} : (empty c : HashSet α).get? a = none :=
HashMap.getKey?_empty
@[simp]
theorem get?_emptyc {a : α} : (∅ : HashSet α).get? a = none :=
HashMap.getKey?_emptyc
theorem get?_of_isEmpty [EquivBEq α] [LawfulHashable α] {a : α} :
m.isEmpty = true → m.get? a = none :=
HashMap.getKey?_of_isEmpty
theorem get?_insert [EquivBEq α] [LawfulHashable α] {k a : α} :
(m.insert k).get? a = if k == a ∧ ¬k ∈ m then some k else m.get? a :=
HashMap.getKey?_insertIfNew
theorem contains_eq_isSome_get? [EquivBEq α] [LawfulHashable α] {a : α} :
m.contains a = (m.get? a).isSome :=
HashMap.contains_eq_isSome_getKey?
theorem get?_eq_none_of_contains_eq_false [EquivBEq α] [LawfulHashable α] {a : α} :
m.contains a = false → m.get? a = none :=
HashMap.getKey?_eq_none_of_contains_eq_false
theorem get?_eq_none [EquivBEq α] [LawfulHashable α] {a : α} : ¬a ∈ m → m.get? a = none :=
HashMap.getKey?_eq_none
theorem get?_erase [EquivBEq α] [LawfulHashable α] {k a : α} :
(m.erase k).get? a = if k == a then none else m.get? a :=
HashMap.getKey?_erase
@[simp]
theorem get?_erase_self [EquivBEq α] [LawfulHashable α] {k : α} : (m.erase k).get? k = none :=
HashMap.getKey?_erase_self
theorem get_insert [EquivBEq α] [LawfulHashable α] {k a : α} {h₁} :
(m.insert k).get a h₁ =
if h₂ : k == a ∧ ¬k ∈ m then k else m.get a (mem_of_mem_insert' h₁ h₂) :=
HashMap.getKey_insertIfNew (h₁ := h₁)
@[simp]
theorem get_erase [EquivBEq α] [LawfulHashable α] {k a : α} {h'} :
(m.erase k).get a h' = m.get a (mem_of_mem_erase h') :=
HashMap.getKey_erase (h' := h')
theorem get?_eq_some_get [EquivBEq α] [LawfulHashable α] {a : α} {h' : a ∈ m} :
m.get? a = some (m.get a h') :=
@HashMap.getKey?_eq_some_getKey _ _ _ _ _ _ _ _ h'
@[simp]
theorem get!_empty [Inhabited α] {a : α} {c} : (empty c : HashSet α).get! a = default :=
HashMap.getKey!_empty
@[simp]
theorem get!_emptyc [Inhabited α] {a : α} : (∅ : HashSet α).get! a = default :=
HashMap.getKey!_emptyc
theorem get!_of_isEmpty [Inhabited α] [EquivBEq α] [LawfulHashable α] {a : α} :
m.isEmpty = true → m.get! a = default :=
HashMap.getKey!_of_isEmpty
theorem get!_insert [Inhabited α] [EquivBEq α] [LawfulHashable α] {k a : α} :
(m.insert k).get! a = if k == a ∧ ¬k ∈ m then k else m.get! a :=
HashMap.getKey!_insertIfNew
theorem get!_eq_default_of_contains_eq_false [Inhabited α] [EquivBEq α] [LawfulHashable α] {a : α} :
m.contains a = false → m.get! a = default :=
HashMap.getKey!_eq_default_of_contains_eq_false
theorem get!_eq_default [Inhabited α] [EquivBEq α] [LawfulHashable α] {a : α} :
¬a ∈ m → m.get! a = default :=
HashMap.getKey!_eq_default
theorem get!_erase [Inhabited α] [EquivBEq α] [LawfulHashable α] {k a : α} :
(m.erase k).get! a = if k == a then default else m.get! a :=
HashMap.getKey!_erase
@[simp]
theorem get!_erase_self [Inhabited α] [EquivBEq α] [LawfulHashable α] {k : α} :
(m.erase k).get! k = default :=
HashMap.getKey!_erase_self
theorem get?_eq_some_get!_of_contains [EquivBEq α] [LawfulHashable α] [Inhabited α]
{a : α} : m.contains a = true → m.get? a = some (m.get! a) :=
HashMap.getKey?_eq_some_getKey!_of_contains
theorem get?_eq_some_get! [EquivBEq α] [LawfulHashable α] [Inhabited α] {a : α} :
a ∈ m → m.get? a = some (m.get! a) :=
HashMap.getKey?_eq_some_getKey!
theorem get!_eq_get!_get? [EquivBEq α] [LawfulHashable α] [Inhabited α] {a : α} :
m.get! a = (m.get? a).get! :=
HashMap.getKey!_eq_get!_getKey?
theorem get_eq_get! [EquivBEq α] [LawfulHashable α] [Inhabited α] {a : α} {h'} :
m.get a h' = m.get! a :=
HashMap.getKey_eq_getKey!
@[simp]
theorem getD_empty {a fallback : α} {c} : (empty c : HashSet α).getD a fallback = fallback :=
HashMap.getKeyD_empty
@[simp]
theorem getD_emptyc {a fallback : α} : (∅ : HashSet α).getD a fallback = fallback :=
HashMap.getKeyD_emptyc
theorem getD_of_isEmpty [EquivBEq α] [LawfulHashable α] {a fallback : α} :
m.isEmpty = true → m.getD a fallback = fallback :=
HashMap.getKeyD_of_isEmpty
theorem getD_insert [EquivBEq α] [LawfulHashable α] {k a fallback : α} :
(m.insert k).getD a fallback = if k == a ∧ ¬k ∈ m then k else m.getD a fallback :=
HashMap.getKeyD_insertIfNew
theorem getD_eq_fallback_of_contains_eq_false [EquivBEq α] [LawfulHashable α]
{a fallback : α} :
m.contains a = false → m.getD a fallback = fallback :=
HashMap.getKeyD_eq_fallback_of_contains_eq_false
theorem getD_eq_fallback [EquivBEq α] [LawfulHashable α] {a fallback : α} :
¬a ∈ m → m.getD a fallback = fallback :=
HashMap.getKeyD_eq_fallback
theorem getD_erase [EquivBEq α] [LawfulHashable α] {k a fallback : α} :
(m.erase k).getD a fallback = if k == a then fallback else m.getD a fallback :=
HashMap.getKeyD_erase
@[simp]
theorem getD_erase_self [EquivBEq α] [LawfulHashable α] {k fallback : α} :
(m.erase k).getD k fallback = fallback :=
HashMap.getKeyD_erase_self
theorem get?_eq_some_getD_of_contains [EquivBEq α] [LawfulHashable α] {a fallback : α} :
m.contains a = true → m.get? a = some (m.getD a fallback) :=
HashMap.getKey?_eq_some_getKeyD_of_contains
theorem get?_eq_some_getD [EquivBEq α] [LawfulHashable α] {a fallback : α} :
a ∈ m → m.get? a = some (m.getD a fallback) :=
HashMap.getKey?_eq_some_getKeyD
theorem getD_eq_getD_get? [EquivBEq α] [LawfulHashable α] {a fallback : α} :
m.getD a fallback = (m.get? a).getD fallback :=
HashMap.getKeyD_eq_getD_getKey?
theorem get_eq_getD [EquivBEq α] [LawfulHashable α] {a fallback : α} {h'} :
m.get a h' = m.getD a fallback :=
@HashMap.getKey_eq_getKeyD _ _ _ _ _ _ _ _ _ h'
theorem get!_eq_getD_default [EquivBEq α] [LawfulHashable α] [Inhabited α] {a : α} :
m.get! a = m.getD a default :=
HashMap.getKey!_eq_getKeyD_default
@[simp]
theorem containsThenInsert_fst {k : α} : (m.containsThenInsert k).1 = m.contains k :=
HashMap.containsThenInsertIfNew_fst
@[simp]
theorem containsThenInsert_snd {k : α} : (m.containsThenInsert k).2 = m.insert k :=
ext HashMap.containsThenInsertIfNew_snd
end
end Std.HashSet