data.finmap | Mathlib porting status

Changes since the initial port

The following section lists changes to this file in mathlib3 and mathlib4 that occured after the initial port. Most recent changes are shown first. Hovering over a commit will show all commits associated with the same mathlib3 commit.

Changes in mathlib3

cea83e19

(last sync)

feat(data/finmap): add an equivalence with pairs (keys, lookup) (#18151)

A non-dependent version of the equivalence requested on Zulip.

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Sean Leather, Mario Carneiro
 -/
 import data.list.alist
-import data.finset.basic
+import data.finset.sigma
 import data.part
 /-!
 # Finite maps over `multiset`
@@ -35,6 +35,14 @@ quot.lift_on s list.nodupkeys (λ s t p, propext $ perm_nodupkeys p)
 
 @[simp] theorem coe_nodupkeys {l : list (sigma β)} : @nodupkeys α β l ↔ l.nodupkeys := iff.rfl
 
+lemma nodup_keys {m : multiset (Σ a, β a)} : m.keys.nodup ↔ m.nodupkeys :=
+by { rcases m with ⟨l⟩, refl }
+
+alias nodup_keys ↔ _ nodupkeys.nodup_keys
+
+lemma nodupkeys.nodup {m : multiset (Σ a, β a)} (h : m.nodupkeys) : m.nodup :=
+h.nodup_keys.of_map _
+
 end multiset
 
 /-! ### finmap -/
@@ -63,6 +71,8 @@ def list.to_finmap [decidable_eq α] (s : list (sigma β)) : finmap β := s.to_a
 namespace finmap
 open alist
 
+lemma nodup_entries (f : finmap β) : f.entries.nodup := f.nodupkeys.nodup
+
 /-! ### lifting from alist -/
 
 /-- Lift a permutation-respecting function on `alist` to `finmap`. -/
@@ -129,7 +139,7 @@ theorem mem_def {a : α} {s : finmap β} :
 
 /-- The set of keys of a finite map. -/
 def keys (s : finmap β) : finset α :=
-⟨s.entries.keys, induction_on s keys_nodup⟩
+⟨s.entries.keys, s.nodupkeys.nodup_keys⟩
 
 @[simp] theorem keys_val (s : alist β) : (keys ⟦s⟧).val = s.keys := rfl
 
@@ -197,6 +207,23 @@ induction_on s $ λ s, alist.lookup_is_some
 theorem lookup_eq_none {a} {s : finmap β} : lookup a s = none ↔ a ∉ s :=
 induction_on s $ λ s, alist.lookup_eq_none
 
+lemma mem_lookup_iff {f : finmap β} {a : α} {b : β a} :
+  b ∈ f.lookup a ↔ sigma.mk a b ∈ f.entries :=
+by { rcases f with ⟨⟨l⟩, hl⟩, exact list.mem_lookup_iff hl }
+
+/-- A version of `finmap.mem_lookup_iff` with LHS in the simp-normal form. -/
+lemma lookup_eq_some_iff {f : finmap β} {a : α} {b : β a} :
+  f.lookup a = some b ↔ sigma.mk a b ∈ f.entries :=
+mem_lookup_iff
+
+@[simp] lemma sigma_keys_lookup (f : finmap β) :
+  f.keys.sigma (λ i, (f.lookup i).to_finset) = ⟨f.entries, f.nodup_entries⟩ :=
+begin
+  ext x,
+  have : x ∈ f.entries → x.fst ∈ f.keys, from multiset.mem_map_of_mem _,
+  simpa [lookup_eq_some_iff]
+end
+
 @[simp] lemma lookup_singleton_eq {a : α} {b : β a} : (singleton a b).lookup a = some b :=
 by rw [singleton, lookup_to_finmap, alist.singleton, alist.lookup, lookup_cons_eq]
 
@@ -206,7 +233,7 @@ decidable_of_iff _ lookup_is_some
 lemma mem_iff {a : α} {s : finmap β} : a ∈ s ↔ ∃ b, s.lookup a = some b :=
 induction_on s $ λ s,
 iff.trans list.mem_keys $ exists_congr $ λ b,
-(mem_lookup_iff s.nodupkeys).symm
+(list.mem_lookup_iff s.nodupkeys).symm
 
 lemma mem_of_lookup_eq_some {a : α} {b : β a} {s : finmap β} (h : s.lookup a = some b) : a ∈ s :=
 mem_iff.mpr ⟨_, h⟩
@@ -221,6 +248,46 @@ begin
   rw h,
 end
 
+/-- An equivalence between `finmap β` and pairs `(keys : finset α, lookup : Π a, option (β a))` such
+that `(lookup a).is_some ↔ a ∈ keys`. -/
+@[simps apply_coe_fst apply_coe_snd]
+def keys_lookup_equiv :
+  finmap β ≃ {f : finset α × (Π a, option (β a)) // ∀ i, (f.2 i).is_some ↔ i ∈ f.1} :=
+{ to_fun := λ f, ⟨(f.keys, λ i, f.lookup i), λ i, lookup_is_some⟩,
+  inv_fun := λ f, ⟨(f.1.1.sigma $ λ i, (f.1.2 i).to_finset).val,
+    begin
+      refine multiset.nodup_keys.1 ((finset.nodup _).map_on _),
+      simp only [finset.mem_val, finset.mem_sigma, option.mem_to_finset, option.mem_def],
+      rintro ⟨i, x⟩ ⟨hi, hx⟩ ⟨j, y⟩ ⟨hj, hy⟩ (rfl : i = j),
+      obtain rfl : x = y, from option.some.inj (hx.symm.trans hy),
+      refl
+    end⟩,
+  left_inv := λ f, ext $ by simp,
+  right_inv := λ ⟨⟨s, f⟩, hf⟩,
+    begin
+      ext : 2; dsimp [keys],
+      { ext1 i,
+        have : i ∈ s → (∃ x, f i = some x),
+          from λ hi, ⟨option.get _, option.get_mem $ (hf i).2 hi⟩,
+        simpa [multiset.keys] },
+      { ext i x : 2,
+        simp only [option.mem_def, lookup_eq_some_iff, finset.mem_val, finset.mem_sigma,
+          option.mem_to_finset, and_iff_right_iff_imp, ← hf],
+        exact λ h, option.is_some_iff_exists.2 ⟨_, h⟩ }
+    end }
+
+@[simp] lemma keys_lookup_equiv_symm_apply_keys :
+  ∀ f : {f : finset α × (Π a, option (β a)) // ∀ i, (f.2 i).is_some ↔ i ∈ f.1},
+    (keys_lookup_equiv.symm f).keys = (f : finset α × Π a, option (β a)).1 :=
+keys_lookup_equiv.surjective.forall.2 $ λ f,
+  by simp only [equiv.symm_apply_apply, keys_lookup_equiv_apply_coe_fst]
+
+@[simp] lemma keys_lookup_equiv_symm_apply_lookup :
+  ∀ (f : {f : finset α × (Π a, option (β a)) // ∀ i, (f.2 i).is_some ↔ i ∈ f.1}) a,
+    (keys_lookup_equiv.symm f).lookup a = (f : finset α × Π a, option (β a)).2 a :=
+keys_lookup_equiv.surjective.forall.2 $ λ f a,
+  by simp only [equiv.symm_apply_apply, keys_lookup_equiv_apply_coe_snd]
+
 /-! ### replace -/
 
 /-- Replace a key with a given value in a finite map.

c3fc15b2

fix(data/finmap): finmap.all should not always be ff (#18432)

Also removes some unnecesary back and forth between bool and Prop.

Diff

@@ -252,11 +252,11 @@ m.entries.foldl (λ d s, f d s.1 s.2) (λ d s t, H _ _ _ _ _) d
 
 /-- `any f s` returns `tt` iff there exists a value `v` in `s` such that `f v = tt`. -/
 def any (f : Π x, β x → bool) (s : finmap β) : bool :=
-s.foldl (λ x y z, x ∨ f y z) (by { intros,  simp [or.right_comm] }) ff
+s.foldl (λ x y z, x || f y z) (by { intros, simp_rw [bool.bor_assoc, bool.bor_comm] }) ff
 
 /-- `all f s` returns `tt` iff `f v = tt` for all values `v` in `s`. -/
 def all (f : Π x, β x → bool) (s : finmap β) : bool :=
-s.foldl (λ x y z, x ∧ f y z) (by { intros, simp [and.right_comm] }) ff
+s.foldl (λ x y z, x && f y z) (by { intros, simp_rw [bool.band_assoc, bool.band_comm] }) tt
 
 /-! ### erase -/

9003f287

(first ported)

Changes in mathlib3port

mathlib3

mathlib3port

cea83e19

bump to nightly-2024-04-06-08

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

e34029c9

Diff

@@ -3,7 +3,7 @@ Copyright (c) 2018 Sean Leather. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Sean Leather, Mario Carneiro
 -/
-import Data.List.Alist
+import Data.List.AList
 import Data.Finset.Sigma
 import Data.Part

cea83e19

bump to nightly-2024-03-17-08

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

22f01ce4

Diff

@@ -433,7 +433,7 @@ theorem mem_of_lookup_eq_some {a : α} {b : β a} {s : Finmap β} (h : s.dlookup
 theorem ext_lookup {s₁ s₂ : Finmap β} : (∀ x, s₁.dlookup x = s₂.dlookup x) → s₁ = s₂ :=
   induction_on₂ s₁ s₂ fun s₁ s₂ h =>
     by
-    simp only [AList.lookup, lookup_to_finmap] at h 
+    simp only [AList.lookup, lookup_to_finmap] at h
     rw [AList.toFinmap_eq]
     apply lookup_ext s₁.nodupkeys s₂.nodupkeys
     intro x y
@@ -918,9 +918,9 @@ theorem union_cancel {s₁ s₂ s₃ : Finmap β} (h : Disjoint s₁ s₃) (h' :
     apply ext_lookup; intro x
     have : (s₁ ∪ s₃).dlookup x = (s₂ ∪ s₃).dlookup x := h'' ▸ rfl
     by_cases hs₁ : x ∈ s₁
-    · rwa [lookup_union_left hs₁, lookup_union_left_of_not_in (h _ hs₁)] at this 
+    · rwa [lookup_union_left hs₁, lookup_union_left_of_not_in (h _ hs₁)] at this
     · by_cases hs₂ : x ∈ s₂
-      · rwa [lookup_union_left_of_not_in (h' _ hs₂), lookup_union_left hs₂] at this 
+      · rwa [lookup_union_left_of_not_in (h' _ hs₂), lookup_union_left hs₂] at this
       · rw [lookup_eq_none.mpr hs₁, lookup_eq_none.mpr hs₂], fun h => h ▸ rfl⟩
 #align finmap.union_cancel Finmap.union_cancel
 -/

cea83e19

bump to nightly-2023-09-24-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451

5655435f

Diff

@@ -3,9 +3,9 @@ Copyright (c) 2018 Sean Leather. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Sean Leather, Mario Carneiro
 -/
-import Mathbin.Data.List.Alist
-import Mathbin.Data.Finset.Sigma
-import Mathbin.Data.Part
+import Data.List.Alist
+import Data.Finset.Sigma
+import Data.Part
 
 #align_import data.finmap from "leanprover-community/mathlib"@"cea83e192eae2d368ab2b500a0975667da42c920"

cea83e19

bump to nightly-2023-08-23-23

mathlib commit https://github.com/leanprover-community/mathlib/commit/32a7e535287f9c73f2e4d2aef306a39190f0b504

f612b9e0

Diff

@@ -62,7 +62,7 @@ theorem nodup_keys {m : Multiset (Σ a, β a)} : m.keys.Nodup ↔ m.NodupKeys :=
 #align multiset.nodup_keys Multiset.nodup_keys
 -/
 
-alias nodup_keys ↔ _ nodupkeys.nodup_keys
+alias ⟨_, nodupkeys.nodup_keys⟩ := nodup_keys
 #align multiset.nodupkeys.nodup_keys Multiset.NodupKeys.nodup_keys
 
 #print Multiset.NodupKeys.nodup /-

cea83e19

bump to nightly-2023-07-20-09

mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345

9c56d0dd

Diff

@@ -2,16 +2,13 @@
 Copyright (c) 2018 Sean Leather. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Sean Leather, Mario Carneiro
-
-! This file was ported from Lean 3 source module data.finmap
-! leanprover-community/mathlib commit cea83e192eae2d368ab2b500a0975667da42c920
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Data.List.Alist
 import Mathbin.Data.Finset.Sigma
 import Mathbin.Data.Part
 
+#align_import data.finmap from "leanprover-community/mathlib"@"cea83e192eae2d368ab2b500a0975667da42c920"
+
 /-!
 # Finite maps over `multiset`

cea83e19

bump to nightly-2023-06-20-01

mathlib commit https://github.com/leanprover-community/mathlib/commit/2a0ce625dbb0ffbc7d1316597de0b25c1ec75303

9b351f8c

Diff

@@ -466,7 +466,7 @@ def keysLookupEquiv :
     · ext1 i
       have : i ∈ s → ∃ x, f i = some x := fun hi => ⟨Option.get _, Option.get_mem <| (hf i).2 hi⟩
       simpa [Multiset.keys]
-    · ext (i x) : 2
+    · ext i x : 2
       simp only [Option.mem_def, lookup_eq_some_iff, Finset.mem_val, Finset.mem_sigma,
         Option.mem_toFinset, and_iff_right_iff_imp, ← hf]
       exact fun h => Option.isSome_iff_exists.2 ⟨_, h⟩

cea83e19

bump to nightly-2023-06-13-21

mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423

829520ac

Diff

@@ -95,7 +95,6 @@ def AList.toFinmap (s : AList β) : Finmap β :=
 #align alist.to_finmap AList.toFinmap
 -/
 
--- mathport name: to_finmap
 local notation:arg "⟦" a "⟧" => AList.toFinmap a
 
 #print AList.toFinmap_eq /-
@@ -148,10 +147,12 @@ def liftOn {γ} (s : Finmap β) (f : AList β → γ)
 #align finmap.lift_on Finmap.liftOn
 -/
 
+#print Finmap.liftOn_toFinmap /-
 @[simp]
 theorem liftOn_toFinmap {γ} (s : AList β) (f : AList β → γ) (H) : liftOn ⟦s⟧ f H = f s := by
   cases s <;> rfl
 #align finmap.lift_on_to_finmap Finmap.liftOn_toFinmap
+-/
 
 #print Finmap.liftOn₂ /-
 /-- Lift a permutation-respecting function on 2 `alist`s to 2 `finmap`s. -/
@@ -168,10 +169,12 @@ def liftOn₂ {γ} (s₁ s₂ : Finmap β) (f : AList β → AList β → γ)
 #align finmap.lift_on₂ Finmap.liftOn₂
 -/
 
+#print Finmap.liftOn₂_toFinmap /-
 @[simp]
 theorem liftOn₂_toFinmap {γ} (s₁ s₂ : AList β) (f : AList β → AList β → γ) (H) :
     liftOn₂ ⟦s₁⟧ ⟦s₂⟧ f H = f s₁ s₂ := by cases s₁ <;> cases s₂ <;> rfl
 #align finmap.lift_on₂_to_finmap Finmap.liftOn₂_toFinmap
+-/
 
 /-! ### induction -/

cea83e19

bump to nightly-2023-06-01-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb

b9c87c70

Diff

@@ -60,7 +60,7 @@ theorem coe_nodupKeys {l : List (Sigma β)} : @NodupKeys α β l ↔ l.NodupKeys
 -/
 
 #print Multiset.nodup_keys /-
-theorem nodup_keys {m : Multiset (Σa, β a)} : m.keys.Nodup ↔ m.NodupKeys := by rcases m with ⟨l⟩;
+theorem nodup_keys {m : Multiset (Σ a, β a)} : m.keys.Nodup ↔ m.NodupKeys := by rcases m with ⟨l⟩;
   rfl
 #align multiset.nodup_keys Multiset.nodup_keys
 -/
@@ -69,7 +69,7 @@ alias nodup_keys ↔ _ nodupkeys.nodup_keys
 #align multiset.nodupkeys.nodup_keys Multiset.NodupKeys.nodup_keys
 
 #print Multiset.NodupKeys.nodup /-
-theorem NodupKeys.nodup {m : Multiset (Σa, β a)} (h : m.NodupKeys) : m.Nodup :=
+theorem NodupKeys.nodup {m : Multiset (Σ a, β a)} (h : m.NodupKeys) : m.Nodup :=
   h.nodup_keys.of_map _
 #align multiset.nodupkeys.nodup Multiset.NodupKeys.nodup
 -/
@@ -433,7 +433,7 @@ theorem mem_of_lookup_eq_some {a : α} {b : β a} {s : Finmap β} (h : s.dlookup
 theorem ext_lookup {s₁ s₂ : Finmap β} : (∀ x, s₁.dlookup x = s₂.dlookup x) → s₁ = s₂ :=
   induction_on₂ s₁ s₂ fun s₁ s₂ h =>
     by
-    simp only [AList.lookup, lookup_to_finmap] at h
+    simp only [AList.lookup, lookup_to_finmap] at h 
     rw [AList.toFinmap_eq]
     apply lookup_ext s₁.nodupkeys s₂.nodupkeys
     intro x y
@@ -538,14 +538,14 @@ def foldl {δ : Type w} (f : δ → ∀ a, β a → δ)
 #print Finmap.any /-
 /-- `any f s` returns `tt` iff there exists a value `v` in `s` such that `f v = tt`. -/
 def any (f : ∀ x, β x → Bool) (s : Finmap β) : Bool :=
-  s.foldl (fun x y z => x || f y z) (by intros ; simp_rw [Bool.or_assoc, Bool.or_comm]) false
+  s.foldl (fun x y z => x || f y z) (by intros; simp_rw [Bool.or_assoc, Bool.or_comm]) false
 #align finmap.any Finmap.any
 -/
 
 #print Finmap.all /-
 /-- `all f s` returns `tt` iff `f v = tt` for all values `v` in `s`. -/
 def all (f : ∀ x, β x → Bool) (s : Finmap β) : Bool :=
-  s.foldl (fun x y z => x && f y z) (by intros ; simp_rw [Bool.and_assoc, Bool.and_comm]) true
+  s.foldl (fun x y z => x && f y z) (by intros; simp_rw [Bool.and_assoc, Bool.and_comm]) true
 #align finmap.all Finmap.all
 -/
 
@@ -704,7 +704,7 @@ theorem toFinmap_cons (a : α) (b : β a) (xs : List (Sigma β)) :
 theorem mem_list_toFinmap (a : α) (xs : List (Sigma β)) :
     a ∈ xs.toFinmap ↔ ∃ b : β a, Sigma.mk a b ∈ xs :=
   by
-  induction' xs with x xs <;> [skip;cases x] <;>
+  induction' xs with x xs <;> [skip; cases x] <;>
       simp only [to_finmap_cons, *, not_mem_empty, exists_or, not_mem_nil, to_finmap_nil,
         exists_false, mem_cons_iff, mem_insert, exists_and_left] <;>
     apply or_congr _ Iff.rfl
@@ -918,9 +918,9 @@ theorem union_cancel {s₁ s₂ s₃ : Finmap β} (h : Disjoint s₁ s₃) (h' :
     apply ext_lookup; intro x
     have : (s₁ ∪ s₃).dlookup x = (s₂ ∪ s₃).dlookup x := h'' ▸ rfl
     by_cases hs₁ : x ∈ s₁
-    · rwa [lookup_union_left hs₁, lookup_union_left_of_not_in (h _ hs₁)] at this
+    · rwa [lookup_union_left hs₁, lookup_union_left_of_not_in (h _ hs₁)] at this 
     · by_cases hs₂ : x ∈ s₂
-      · rwa [lookup_union_left_of_not_in (h' _ hs₂), lookup_union_left hs₂] at this
+      · rwa [lookup_union_left_of_not_in (h' _ hs₂), lookup_union_left hs₂] at this 
       · rw [lookup_eq_none.mpr hs₁, lookup_eq_none.mpr hs₂], fun h => h ▸ rfl⟩
 #align finmap.union_cancel Finmap.union_cancel
 -/

cea83e19

bump to nightly-2023-05-28-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

ba5d8b97

Diff

@@ -148,12 +148,6 @@ def liftOn {γ} (s : Finmap β) (f : AList β → γ)
 #align finmap.lift_on Finmap.liftOn
 -/
 
-/- warning: finmap.lift_on_to_finmap -> Finmap.liftOn_toFinmap is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {β : α -> Type.{u2}} {γ : Type.{u3}} (s : AList.{u1, u2} α β) (f : (AList.{u1, u2} α β) -> γ) (H : forall (a : AList.{u1, u2} α β) (b : AList.{u1, u2} α β), (List.Perm.{max u1 u2} (Sigma.{u1, u2} α β) (AList.entries.{u1, u2} α β a) (AList.entries.{u1, u2} α β b)) -> (Eq.{succ u3} γ (f a) (f b))), Eq.{succ u3} γ (Finmap.liftOn.{u1, u2, u3} α β γ (AList.toFinmap.{u1, u2} α β s) f H) (f s)
-but is expected to have type
-  forall {α : Type.{u2}} {β : α -> Type.{u3}} {γ : Type.{u1}} (s : AList.{u2, u3} α β) (f : (AList.{u2, u3} α β) -> γ) (H : forall (a : AList.{u2, u3} α β) (b : AList.{u2, u3} α β), (List.Perm.{max u2 u3} (Sigma.{u2, u3} α β) (AList.entries.{u2, u3} α β a) (AList.entries.{u2, u3} α β b)) -> (Eq.{succ u1} γ (f a) (f b))), Eq.{succ u1} γ (Finmap.liftOn.{u2, u3, u1} α β γ (AList.toFinmap.{u2, u3} α β s) f H) (f s)
-Case conversion may be inaccurate. Consider using '#align finmap.lift_on_to_finmap Finmap.liftOn_toFinmapₓ'. -/
 @[simp]
 theorem liftOn_toFinmap {γ} (s : AList β) (f : AList β → γ) (H) : liftOn ⟦s⟧ f H = f s := by
   cases s <;> rfl
@@ -174,12 +168,6 @@ def liftOn₂ {γ} (s₁ s₂ : Finmap β) (f : AList β → AList β → γ)
 #align finmap.lift_on₂ Finmap.liftOn₂
 -/
 
-/- warning: finmap.lift_on₂_to_finmap -> Finmap.liftOn₂_toFinmap is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {β : α -> Type.{u2}} {γ : Type.{u3}} (s₁ : AList.{u1, u2} α β) (s₂ : AList.{u1, u2} α β) (f : (AList.{u1, u2} α β) -> (AList.{u1, u2} α β) -> γ) (H : forall (a₁ : AList.{u1, u2} α β) (b₁ : AList.{u1, u2} α β) (a₂ : AList.{u1, u2} α β) (b₂ : AList.{u1, u2} α β), (List.Perm.{max u1 u2} (Sigma.{u1, u2} α β) (AList.entries.{u1, u2} α β a₁) (AList.entries.{u1, u2} α β a₂)) -> (List.Perm.{max u1 u2} (Sigma.{u1, u2} α β) (AList.entries.{u1, u2} α β b₁) (AList.entries.{u1, u2} α β b₂)) -> (Eq.{succ u3} γ (f a₁ b₁) (f a₂ b₂))), Eq.{succ u3} γ (Finmap.liftOn₂.{u1, u2, u3} α β γ (AList.toFinmap.{u1, u2} α β s₁) (AList.toFinmap.{u1, u2} α β s₂) f H) (f s₁ s₂)
-but is expected to have type
-  forall {α : Type.{u2}} {β : α -> Type.{u3}} {γ : Type.{u1}} (s₁ : AList.{u2, u3} α β) (s₂ : AList.{u2, u3} α β) (f : (AList.{u2, u3} α β) -> (AList.{u2, u3} α β) -> γ) (H : forall (a₁ : AList.{u2, u3} α β) (b₁ : AList.{u2, u3} α β) (a₂ : AList.{u2, u3} α β) (b₂ : AList.{u2, u3} α β), (List.Perm.{max u2 u3} (Sigma.{u2, u3} α β) (AList.entries.{u2, u3} α β a₁) (AList.entries.{u2, u3} α β a₂)) -> (List.Perm.{max u2 u3} (Sigma.{u2, u3} α β) (AList.entries.{u2, u3} α β b₁) (AList.entries.{u2, u3} α β b₂)) -> (Eq.{succ u1} γ (f a₁ b₁) (f a₂ b₂))), Eq.{succ u1} γ (Finmap.liftOn₂.{u2, u3, u1} α β γ (AList.toFinmap.{u2, u3} α β s₁) (AList.toFinmap.{u2, u3} α β s₂) f H) (f s₁ s₂)
-Case conversion may be inaccurate. Consider using '#align finmap.lift_on₂_to_finmap Finmap.liftOn₂_toFinmapₓ'. -/
 @[simp]
 theorem liftOn₂_toFinmap {γ} (s₁ s₂ : AList β) (f : AList β → AList β → γ) (H) :
     liftOn₂ ⟦s₁⟧ ⟦s₂⟧ f H = f s₁ s₂ := by cases s₁ <;> cases s₂ <;> rfl

cea83e19

bump to nightly-2023-05-28-04

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

6797a637

Diff

@@ -60,9 +60,7 @@ theorem coe_nodupKeys {l : List (Sigma β)} : @NodupKeys α β l ↔ l.NodupKeys
 -/
 
 #print Multiset.nodup_keys /-
-theorem nodup_keys {m : Multiset (Σa, β a)} : m.keys.Nodup ↔ m.NodupKeys :=
-  by
-  rcases m with ⟨l⟩
+theorem nodup_keys {m : Multiset (Σa, β a)} : m.keys.Nodup ↔ m.NodupKeys := by rcases m with ⟨l⟩;
   rfl
 #align multiset.nodup_keys Multiset.nodup_keys
 -/
@@ -146,9 +144,7 @@ def liftOn {γ} (s : Finmap β) (f : AList β → γ)
           Part γ).get
       _
   · exact fun h₁ h₂ => H _ _ p
-  · have := s.nodupkeys
-    rcases s.entries with ⟨l⟩
-    exact id
+  · have := s.nodupkeys; rcases s.entries with ⟨l⟩; exact id
 #align finmap.lift_on Finmap.liftOn
 -/
 
@@ -398,9 +394,7 @@ theorem lookup_eq_none {a} {s : Finmap β} : lookup a s = none ↔ a ∉ s :=
 
 #print Finmap.mem_lookup_iff /-
 theorem mem_lookup_iff {f : Finmap β} {a : α} {b : β a} :
-    b ∈ f.dlookup a ↔ Sigma.mk a b ∈ f.entries :=
-  by
-  rcases f with ⟨⟨l⟩, hl⟩
+    b ∈ f.dlookup a ↔ Sigma.mk a b ∈ f.entries := by rcases f with ⟨⟨l⟩, hl⟩;
   exact List.mem_dlookup_iff hl
 #align finmap.mem_lookup_iff Finmap.mem_lookup_iff
 -/
@@ -556,22 +550,14 @@ def foldl {δ : Type w} (f : δ → ∀ a, β a → δ)
 #print Finmap.any /-
 /-- `any f s` returns `tt` iff there exists a value `v` in `s` such that `f v = tt`. -/
 def any (f : ∀ x, β x → Bool) (s : Finmap β) : Bool :=
-  s.foldl (fun x y z => x || f y z)
-    (by
-      intros
-      simp_rw [Bool.or_assoc, Bool.or_comm])
-    false
+  s.foldl (fun x y z => x || f y z) (by intros ; simp_rw [Bool.or_assoc, Bool.or_comm]) false
 #align finmap.any Finmap.any
 -/
 
 #print Finmap.all /-
 /-- `all f s` returns `tt` iff `f v = tt` for all values `v` in `s`. -/
 def all (f : ∀ x, β x → Bool) (s : Finmap β) : Bool :=
-  s.foldl (fun x y z => x && f y z)
-    (by
-      intros
-      simp_rw [Bool.and_assoc, Bool.and_comm])
-    true
+  s.foldl (fun x y z => x && f y z) (by intros ; simp_rw [Bool.and_assoc, Bool.and_comm]) true
 #align finmap.all Finmap.all
 -/
 
@@ -737,9 +723,7 @@ theorem mem_list_toFinmap (a : α) (xs : List (Sigma β)) :
   conv =>
     lhs
     rw [← and_true_iff (a = x_fst)]
-  apply and_congr_right
-  rintro ⟨⟩
-  simp only [exists_eq, heq_iff_eq]
+  apply and_congr_right; rintro ⟨⟩; simp only [exists_eq, heq_iff_eq]
 #align finmap.mem_list_to_finmap Finmap.mem_list_toFinmap
 -/
 
@@ -877,8 +861,7 @@ theorem erase_union_singleton (a : α) (b : β a) (s : Finmap β) (h : s.dlookup
     s.eraseₓ a ∪ singleton a b = s :=
   ext_lookup fun x => by
     by_cases h' : x = a
-    · subst a
-      rw [lookup_union_right not_mem_erase_self, lookup_singleton_eq, h]
+    · subst a; rw [lookup_union_right not_mem_erase_self, lookup_singleton_eq, h]
     · have : x ∉ singleton a b := by rwa [mem_singleton]
       rw [lookup_union_left_of_not_in this, lookup_erase_ne h']
 #align finmap.erase_union_singleton Finmap.erase_union_singleton
@@ -935,8 +918,7 @@ theorem disjoint_union_right (x y z : Finmap β) :
 
 #print Finmap.union_comm_of_disjoint /-
 theorem union_comm_of_disjoint {s₁ s₂ : Finmap β} : Disjoint s₁ s₂ → s₁ ∪ s₂ = s₂ ∪ s₁ :=
-  induction_on₂ s₁ s₂ fun s₁ s₂ => by
-    intro h
+  induction_on₂ s₁ s₂ fun s₁ s₂ => by intro h;
     simp only [AList.toFinmap_eq, union_to_finmap, AList.union_comm_of_disjoint h]
 #align finmap.union_comm_of_disjoint Finmap.union_comm_of_disjoint
 -/
@@ -945,8 +927,7 @@ theorem union_comm_of_disjoint {s₁ s₂ : Finmap β} : Disjoint s₁ s₂ →
 theorem union_cancel {s₁ s₂ s₃ : Finmap β} (h : Disjoint s₁ s₃) (h' : Disjoint s₂ s₃) :
     s₁ ∪ s₃ = s₂ ∪ s₃ ↔ s₁ = s₂ :=
   ⟨fun h'' => by
-    apply ext_lookup
-    intro x
+    apply ext_lookup; intro x
     have : (s₁ ∪ s₃).dlookup x = (s₂ ∪ s₃).dlookup x := h'' ▸ rfl
     by_cases hs₁ : x ∈ s₁
     · rwa [lookup_union_left hs₁, lookup_union_left_of_not_in (h _ hs₁)] at this

cea83e19

bump to nightly-2023-05-24-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/8d33f09cd7089ecf074b4791907588245aec5d1b

fbc7b476

Diff

@@ -730,7 +730,7 @@ theorem toFinmap_cons (a : α) (b : β a) (xs : List (Sigma β)) :
 theorem mem_list_toFinmap (a : α) (xs : List (Sigma β)) :
     a ∈ xs.toFinmap ↔ ∃ b : β a, Sigma.mk a b ∈ xs :=
   by
-  induction' xs with x xs <;> [skip, cases x] <;>
+  induction' xs with x xs <;> [skip;cases x] <;>
       simp only [to_finmap_cons, *, not_mem_empty, exists_or, not_mem_nil, to_finmap_nil,
         exists_false, mem_cons_iff, mem_insert, exists_and_left] <;>
     apply or_congr _ Iff.rfl

cea83e19

bump to nightly-2023-03-27-02

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce86f4e05e9a9b8da5e316b22c76ce76440c56a1

0e4ebd8c

Diff

@@ -4,12 +4,12 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Sean Leather, Mario Carneiro
 
 ! This file was ported from Lean 3 source module data.finmap
-! leanprover-community/mathlib commit c3fc15b26b3ff8958ec3e5711177a9ae3d5c45b7
+! leanprover-community/mathlib commit cea83e192eae2d368ab2b500a0975667da42c920
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
 import Mathbin.Data.List.Alist
-import Mathbin.Data.Finset.Basic
+import Mathbin.Data.Finset.Sigma
 import Mathbin.Data.Part
 
 /-!
@@ -59,6 +59,23 @@ theorem coe_nodupKeys {l : List (Sigma β)} : @NodupKeys α β l ↔ l.NodupKeys
 #align multiset.coe_nodupkeys Multiset.coe_nodupKeys
 -/
 
+#print Multiset.nodup_keys /-
+theorem nodup_keys {m : Multiset (Σa, β a)} : m.keys.Nodup ↔ m.NodupKeys :=
+  by
+  rcases m with ⟨l⟩
+  rfl
+#align multiset.nodup_keys Multiset.nodup_keys
+-/
+
+alias nodup_keys ↔ _ nodupkeys.nodup_keys
+#align multiset.nodupkeys.nodup_keys Multiset.NodupKeys.nodup_keys
+
+#print Multiset.NodupKeys.nodup /-
+theorem NodupKeys.nodup {m : Multiset (Σa, β a)} (h : m.NodupKeys) : m.Nodup :=
+  h.nodup_keys.of_map _
+#align multiset.nodupkeys.nodup Multiset.NodupKeys.nodup
+-/
+
 end Multiset
 
 /-! ### finmap -/
@@ -108,6 +125,12 @@ namespace Finmap
 
 open AList
 
+#print Finmap.nodup_entries /-
+theorem nodup_entries (f : Finmap β) : f.entries.Nodup :=
+  f.NodupKeys.Nodup
+#align finmap.nodup_entries Finmap.nodup_entries
+-/
+
 /-! ### lifting from alist -/
 
 
@@ -235,7 +258,7 @@ theorem mem_toFinmap {a : α} {s : AList β} : a ∈ ⟦s⟧ ↔ a ∈ s :=
 #print Finmap.keys /-
 /-- The set of keys of a finite map. -/
 def keys (s : Finmap β) : Finset α :=
-  ⟨s.entries.keys, induction_on s keys_nodup⟩
+  ⟨s.entries.keys, s.NodupKeys.nodup_keys⟩
 #align finmap.keys Finmap.keys
 -/
 
@@ -373,6 +396,34 @@ theorem lookup_eq_none {a} {s : Finmap β} : lookup a s = none ↔ a ∉ s :=
 #align finmap.lookup_eq_none Finmap.lookup_eq_none
 -/
 
+#print Finmap.mem_lookup_iff /-
+theorem mem_lookup_iff {f : Finmap β} {a : α} {b : β a} :
+    b ∈ f.dlookup a ↔ Sigma.mk a b ∈ f.entries :=
+  by
+  rcases f with ⟨⟨l⟩, hl⟩
+  exact List.mem_dlookup_iff hl
+#align finmap.mem_lookup_iff Finmap.mem_lookup_iff
+-/
+
+#print Finmap.lookup_eq_some_iff /-
+/-- A version of `finmap.mem_lookup_iff` with LHS in the simp-normal form. -/
+theorem lookup_eq_some_iff {f : Finmap β} {a : α} {b : β a} :
+    f.dlookup a = some b ↔ Sigma.mk a b ∈ f.entries :=
+  mem_lookup_iff
+#align finmap.lookup_eq_some_iff Finmap.lookup_eq_some_iff
+-/
+
+#print Finmap.sigma_keys_lookup /-
+@[simp]
+theorem sigma_keys_lookup (f : Finmap β) :
+    (f.keys.Sigma fun i => (f.dlookup i).toFinset) = ⟨f.entries, f.nodup_entries⟩ :=
+  by
+  ext x
+  have : x ∈ f.entries → x.fst ∈ f.keys := Multiset.mem_map_of_mem _
+  simpa [lookup_eq_some_iff]
+#align finmap.sigma_keys_lookup Finmap.sigma_keys_lookup
+-/
+
 #print Finmap.lookup_singleton_eq /-
 @[simp]
 theorem lookup_singleton_eq {a : α} {b : β a} : (singleton a b).dlookup a = some b := by
@@ -386,7 +437,7 @@ instance (a : α) (s : Finmap β) : Decidable (a ∈ s) :=
 #print Finmap.mem_iff /-
 theorem mem_iff {a : α} {s : Finmap β} : a ∈ s ↔ ∃ b, s.dlookup a = some b :=
   induction_on s fun s =>
-    Iff.trans List.mem_keys <| exists_congr fun b => (mem_lookup_iff s.NodupKeys).symm
+    Iff.trans List.mem_keys <| exists_congr fun b => (List.mem_dlookup_iff s.NodupKeys).symm
 #align finmap.mem_iff Finmap.mem_iff
 -/
 
@@ -408,6 +459,55 @@ theorem ext_lookup {s₁ s₂ : Finmap β} : (∀ x, s₁.dlookup x = s₂.dlook
 #align finmap.ext_lookup Finmap.ext_lookup
 -/
 
+#print Finmap.keysLookupEquiv /-
+/-- An equivalence between `finmap β` and pairs `(keys : finset α, lookup : Π a, option (β a))` such
+that `(lookup a).is_some ↔ a ∈ keys`. -/
+@[simps apply_coe_fst apply_coe_snd]
+def keysLookupEquiv :
+    Finmap β ≃ { f : Finset α × ∀ a, Option (β a) // ∀ i, (f.2 i).isSome ↔ i ∈ f.1 }
+    where
+  toFun f := ⟨(f.keys, fun i => f.dlookup i), fun i => lookup_isSome⟩
+  invFun f :=
+    ⟨(f.1.1.Sigma fun i => (f.1.2 i).toFinset).val,
+      by
+      refine' Multiset.nodup_keys.1 ((Finset.nodup _).map_onₓ _)
+      simp only [Finset.mem_val, Finset.mem_sigma, Option.mem_toFinset, Option.mem_def]
+      rintro ⟨i, x⟩ ⟨hi, hx⟩ ⟨j, y⟩ ⟨hj, hy⟩ (rfl : i = j)
+      obtain rfl : x = y; exact Option.some.inj (hx.symm.trans hy)
+      rfl⟩
+  left_inv f := ext <| by simp
+  right_inv := fun ⟨⟨s, f⟩, hf⟩ => by
+    ext : 2 <;> dsimp [keys]
+    · ext1 i
+      have : i ∈ s → ∃ x, f i = some x := fun hi => ⟨Option.get _, Option.get_mem <| (hf i).2 hi⟩
+      simpa [Multiset.keys]
+    · ext (i x) : 2
+      simp only [Option.mem_def, lookup_eq_some_iff, Finset.mem_val, Finset.mem_sigma,
+        Option.mem_toFinset, and_iff_right_iff_imp, ← hf]
+      exact fun h => Option.isSome_iff_exists.2 ⟨_, h⟩
+#align finmap.keys_lookup_equiv Finmap.keysLookupEquiv
+-/
+
+#print Finmap.keysLookupEquiv_symm_apply_keys /-
+@[simp]
+theorem keysLookupEquiv_symm_apply_keys :
+    ∀ f : { f : Finset α × ∀ a, Option (β a) // ∀ i, (f.2 i).isSome ↔ i ∈ f.1 },
+      (keysLookupEquiv.symm f).keys = (f : Finset α × ∀ a, Option (β a)).1 :=
+  keysLookupEquiv.Surjective.forall.2 fun f => by
+    simp only [Equiv.symm_apply_apply, keys_lookup_equiv_apply_coe_fst]
+#align finmap.keys_lookup_equiv_symm_apply_keys Finmap.keysLookupEquiv_symm_apply_keys
+-/
+
+#print Finmap.keysLookupEquiv_symm_apply_lookup /-
+@[simp]
+theorem keysLookupEquiv_symm_apply_lookup :
+    ∀ (f : { f : Finset α × ∀ a, Option (β a) // ∀ i, (f.2 i).isSome ↔ i ∈ f.1 }) (a),
+      (keysLookupEquiv.symm f).dlookup a = (f : Finset α × ∀ a, Option (β a)).2 a :=
+  keysLookupEquiv.Surjective.forall.2 fun f a => by
+    simp only [Equiv.symm_apply_apply, keys_lookup_equiv_apply_coe_snd]
+#align finmap.keys_lookup_equiv_symm_apply_lookup Finmap.keysLookupEquiv_symm_apply_lookup
+-/
+
 /-! ### replace -/

c3fc15b2

bump to nightly-2023-02-28-03

mathlib commit https://github.com/leanprover-community/mathlib/commit/9da1b3534b65d9661eb8f42443598a92bbb49211

ead5cda8

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Sean Leather, Mario Carneiro
 
 ! This file was ported from Lean 3 source module data.finmap
-! leanprover-community/mathlib commit 4c19a16e4b705bf135cf9a80ac18fcc99c438514
+! leanprover-community/mathlib commit c3fc15b26b3ff8958ec3e5711177a9ae3d5c45b7
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -456,10 +456,10 @@ def foldl {δ : Type w} (f : δ → ∀ a, β a → δ)
 #print Finmap.any /-
 /-- `any f s` returns `tt` iff there exists a value `v` in `s` such that `f v = tt`. -/
 def any (f : ∀ x, β x → Bool) (s : Finmap β) : Bool :=
-  s.foldl (fun x y z => x ∨ f y z)
+  s.foldl (fun x y z => x || f y z)
     (by
       intros
-      simp [or_right_comm])
+      simp_rw [Bool.or_assoc, Bool.or_comm])
     false
 #align finmap.any Finmap.any
 -/
@@ -467,11 +467,11 @@ def any (f : ∀ x, β x → Bool) (s : Finmap β) : Bool :=
 #print Finmap.all /-
 /-- `all f s` returns `tt` iff `f v = tt` for all values `v` in `s`. -/
 def all (f : ∀ x, β x → Bool) (s : Finmap β) : Bool :=
-  s.foldl (fun x y z => x ∧ f y z)
+  s.foldl (fun x y z => x && f y z)
     (by
       intros
-      simp [and_right_comm])
-    false
+      simp_rw [Bool.and_assoc, Bool.and_comm])
+    true
 #align finmap.all Finmap.all
 -/

4c19a16e

bump to nightly-2023-02-21-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc

1107b979

Changes in mathlib4

mathlib3

mathlib4

cea83e19

chore: move Mathlib to v4.7.0-rc1 (#11162)

This is a very large PR, but it has been reviewed piecemeal already in PRs to the bump/v4.7.0 branch as we update to intermediate nightlies.

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Kyle Miller <kmill31415@gmail.com> Co-authored-by: damiano <adomani@gmail.com>

fa48894a

Diff

@@ -650,7 +650,7 @@ def Disjoint (s₁ s₂ : Finmap β) : Prop :=
 #align finmap.disjoint Finmap.Disjoint
 
 theorem disjoint_empty (x : Finmap β) : Disjoint ∅ x :=
-  fun.
+  nofun
 #align finmap.disjoint_empty Finmap.disjoint_empty
 
 @[symm]

cea83e19

chore: classify simp can do this porting notes (#10619)

Classify by adding issue number (#10618) to porting notes claiming anything semantically equivalent to simp can prove this or simp can simplify this.

de765f60

Diff

@@ -596,7 +596,7 @@ theorem lookup_union_left_of_not_in {a} {s₁ s₂ : Finmap β} (h : a ∉ s₂)
   · rw [lookup_union_right h', lookup_eq_none.mpr h, lookup_eq_none.mpr h']
 #align finmap.lookup_union_left_of_not_in Finmap.lookup_union_left_of_not_in
 
--- @[simp] -- Porting note: simp can prove this
+-- @[simp] -- Porting note (#10618): simp can prove this
 theorem mem_lookup_union {a} {b : β a} {s₁ s₂ : Finmap β} :
     b ∈ lookup a (s₁ ∪ s₂) ↔ b ∈ lookup a s₁ ∨ a ∉ s₁ ∧ b ∈ lookup a s₂ :=
   induction_on₂ s₁ s₂ fun _ _ => AList.mem_lookup_union

cea83e19

chore(*): drop $/<| before fun (#9361)

Subset of #9319

3694e27d

Diff

@@ -332,7 +332,7 @@ that `(lookup a).isSome ↔ a ∈ keys`. -/
 def keysLookupEquiv :
     Finmap β ≃ { f : Finset α × (∀ a, Option (β a)) // ∀ i, (f.2 i).isSome ↔ i ∈ f.1 } where
   toFun s := ⟨(s.keys, fun i => s.lookup i), fun _ => lookup_isSome⟩
-  invFun f := mk (f.1.1.sigma <| fun i => (f.1.2 i).toFinset).val <| by
+  invFun f := mk (f.1.1.sigma fun i => (f.1.2 i).toFinset).val <| by
     refine Multiset.nodup_keys.1 ((Finset.nodup _).map_on ?_)
     simp only [Finset.mem_val, Finset.mem_sigma, Option.mem_toFinset, Option.mem_def]
     rintro ⟨i, x⟩ ⟨_, hx⟩ ⟨j, y⟩ ⟨_, hy⟩ (rfl : i = j)
@@ -347,13 +347,13 @@ def keysLookupEquiv :
 @[simp] lemma keysLookupEquiv_symm_apply_keys :
     ∀ f : {f : Finset α × (∀ a, Option (β a)) // ∀ i, (f.2 i).isSome ↔ i ∈ f.1},
       (keysLookupEquiv.symm f).keys = f.1.1 :=
-  keysLookupEquiv.surjective.forall.2 $ fun _ => by
+  keysLookupEquiv.surjective.forall.2 fun _ => by
     simp only [Equiv.symm_apply_apply, keysLookupEquiv_apply_coe_fst]
 
 @[simp] lemma keysLookupEquiv_symm_apply_lookup :
     ∀ (f : {f : Finset α × (∀ a, Option (β a)) // ∀ i, (f.2 i).isSome ↔ i ∈ f.1}) a,
       (keysLookupEquiv.symm f).lookup a = f.1.2 a :=
-  keysLookupEquiv.surjective.forall.2 $ fun _ _ => by
+  keysLookupEquiv.surjective.forall.2 fun _ _ => by
     simp only [Equiv.symm_apply_apply, keysLookupEquiv_apply_coe_snd]
 
 /-! ### replace -/

cea83e19

style: a linter for colons (#6761)

A linter that throws on seeing a colon at the start of a line, according to the style guideline that says these operators should go before linebreaks.

69a3de31

Diff

@@ -477,8 +477,8 @@ def insert (a : α) (b : β a) (s : Finmap β) : Finmap β :=
 #align finmap.insert Finmap.insert
 
 @[simp]
-theorem insert_toFinmap (a : α) (b : β a) (s : AList β)
-  : insert a b (AList.toFinmap s) = AList.toFinmap (s.insert a b) := by
+theorem insert_toFinmap (a : α) (b : β a) (s : AList β) :
+    insert a b (AList.toFinmap s) = AList.toFinmap (s.insert a b) := by
   simp [insert]
 #align finmap.insert_to_finmap Finmap.insert_toFinmap
 
@@ -571,8 +571,8 @@ theorem mem_union {a} {s₁ s₂ : Finmap β} : a ∈ s₁ ∪ s₂ ↔ a ∈ s
 #align finmap.mem_union Finmap.mem_union
 
 @[simp]
-theorem union_toFinmap (s₁ s₂ : AList β)
-  : (toFinmap s₁) ∪ (toFinmap s₂) = toFinmap (s₁ ∪ s₂) := by simp [(· ∪ ·), union]
+theorem union_toFinmap (s₁ s₂ : AList β) : (toFinmap s₁) ∪ (toFinmap s₂) = toFinmap (s₁ ∪ s₂) := by
+  simp [(· ∪ ·), union]
 #align finmap.union_to_finmap Finmap.union_toFinmap
 
 theorem keys_union {s₁ s₂ : Finmap β} : (s₁ ∪ s₂).keys = s₁.keys ∪ s₂.keys :=

cea83e19

feat: patch for new alias command (#6172)

19e0ba92

Diff

@@ -47,7 +47,7 @@ theorem coe_nodupKeys {l : List (Sigma β)} : @NodupKeys α β l ↔ l.NodupKeys
 lemma nodup_keys {m : Multiset (Σ a, β a)} : m.keys.Nodup ↔ m.NodupKeys := by
   rcases m with ⟨l⟩; rfl
 
-alias nodup_keys ↔ _ NodupKeys.nodup_keys
+alias ⟨_, NodupKeys.nodup_keys⟩ := nodup_keys
 
 protected lemma NodupKeys.nodup {m : Multiset (Σ a, β a)} (h : m.NodupKeys) : m.Nodup :=
   h.nodup_keys.of_map _

cea83e19

chore: script to replace headers with #align_import statements (#5979)

depends on: #5966

Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

89aa3a3b

Diff

@@ -2,16 +2,13 @@
 Copyright (c) 2018 Sean Leather. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Sean Leather, Mario Carneiro
-
-! This file was ported from Lean 3 source module data.finmap
-! leanprover-community/mathlib commit cea83e192eae2d368ab2b500a0975667da42c920
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Data.List.AList
 import Mathlib.Data.Finset.Sigma
 import Mathlib.Data.Part
 
+#align_import data.finmap from "leanprover-community/mathlib"@"cea83e192eae2d368ab2b500a0975667da42c920"
+
 /-!
 # Finite maps over `Multiset`
 -/

cea83e19

chore: remove occurrences of semicolon after space (#5713)

This is the second half of the changes originally in #5699, removing all occurrences of ; after a space and implementing a linter rule to enforce it.

In most cases this 2-character substring has a space after it, so the following command was run first:

find . -type f -name "*.lean" -exec sed -i -E 's/ ; /; /g' {} \;

The remaining cases were few enough in number that they were done manually.

c795bd35

Diff

@@ -136,14 +136,14 @@ def liftOn₂ {γ} (s₁ s₂ : Finmap β) (f : AList β → AList β → γ)
 @[simp]
 theorem liftOn₂_toFinmap {γ} (s₁ s₂ : AList β) (f : AList β → AList β → γ) (H) :
     liftOn₂ ⟦s₁⟧ ⟦s₂⟧ f H = f s₁ s₂ :=
-      by cases s₁ ; cases s₂ ; rfl
+      by cases s₁; cases s₂; rfl
 #align finmap.lift_on₂_to_finmap Finmap.liftOn₂_toFinmap
 
 /-! ### Induction -/
 
 @[elab_as_elim]
 theorem induction_on {C : Finmap β → Prop} (s : Finmap β) (H : ∀ a : AList β, C ⟦a⟧) : C s := by
-  rcases s with ⟨⟨a⟩, h⟩ ; exact H ⟨a, h⟩
+  rcases s with ⟨⟨a⟩, h⟩; exact H ⟨a, h⟩
 #align finmap.induction_on Finmap.induction_on
 
 @[elab_as_elim]
@@ -248,7 +248,7 @@ theorem keys_singleton (a : α) (b : β a) : (singleton a b).keys = {a} :=
 
 @[simp]
 theorem mem_singleton (x y : α) (b : β y) : x ∈ singleton y b ↔ x = y := by
-  simp only [singleton] ; erw [mem_cons, mem_nil_iff, or_false_iff]
+  simp only [singleton]; erw [mem_cons, mem_nil_iff, or_false_iff]
 #align finmap.mem_singleton Finmap.mem_singleton
 
 section

cea83e19

chore: fix grammar 2/3 (#5002)

Part 2 of #5001

9e80ae3b

Diff

@@ -62,7 +62,7 @@ end Multiset
 /-- `Finmap β` is the type of finite maps over a multiset. It is effectively
   a quotient of `AList β` by permutation of the underlying list. -/
 structure Finmap (β : α → Type v) : Type max u v where
-  /-- The underlying `Multiset` of an `Finmap` -/
+  /-- The underlying `Multiset` of a `Finmap` -/
   entries : Multiset (Sigma β)
   /-- There are no duplicate keys in `entries` -/
   nodupKeys : entries.NodupKeys

cea83e19

chore: fix #align lines (#3640)

This PR fixes two things:

Most align statements for definitions and theorems and instances that are separated by two newlines from the relevant declaration (s/\n\n#align/\n#align). This is often seen in the mathport output after ending calc blocks.
All remaining more-than-one-line #align statements. (This was needed for a script I wrote for #3630.)

2b42dc7c

Diff

@@ -115,7 +115,6 @@ def liftOn {γ} (s : Finmap β) (f : AList β → γ)
     revert this
     rcases s.entries with ⟨l⟩
     exact id
-
 #align finmap.lift_on Finmap.liftOn
 
 @[simp]

cea83e19

chore: tidy various files (#3530)

8cf71b01

Diff

@@ -528,16 +528,14 @@ theorem toFinmap_cons (a : α) (b : β a) (xs : List (Sigma β)) :
 
 theorem mem_list_toFinmap (a : α) (xs : List (Sigma β)) :
     a ∈ xs.toFinmap ↔ ∃ b : β a, Sigma.mk a b ∈ xs := by
-  induction' xs with x xs <;> [skip, cases' x with fst_i snd_i] <;>
-      -- Porting note: `Sigma.mk.inj_iff` required because `simp` behaves differently
-      simp only [toFinmap_cons, *, not_mem_empty, exists_or, not_mem_nil, toFinmap_nil,
-        exists_false, mem_cons, mem_insert, exists_and_left, Sigma.mk.inj_iff];
-      apply or_congr _ Iff.rfl
-  conv =>
-    lhs
-    rw [← and_true_iff (a = fst_i)]
-  apply and_congr_right
-  rintro ⟨⟩
+  -- Porting note: golfed
+  induction' xs with x xs
+  · simp only [toFinmap_nil, not_mem_empty, find?, not_mem_nil, exists_false]
+  cases' x with fst_i snd_i
+  -- Porting note: `Sigma.mk.inj_iff` required because `simp` behaves differently
+  simp only [toFinmap_cons, *, exists_or, mem_cons, mem_insert, exists_and_left, Sigma.mk.inj_iff]
+  refine (or_congr_left <| and_iff_left_of_imp ?_).symm
+  rintro rfl
   simp only [exists_eq, heq_iff_eq]
 #align finmap.mem_list_to_finmap Finmap.mem_list_toFinmap

cea83e19

Refactor uses to rename_i that have easy fixes (#2429)

ffbbaaae

Diff

@@ -528,12 +528,11 @@ theorem toFinmap_cons (a : α) (b : β a) (xs : List (Sigma β)) :
 
 theorem mem_list_toFinmap (a : α) (xs : List (Sigma β)) :
     a ∈ xs.toFinmap ↔ ∃ b : β a, Sigma.mk a b ∈ xs := by
-  induction' xs with x xs <;> [skip, cases x] <;>
+  induction' xs with x xs <;> [skip, cases' x with fst_i snd_i] <;>
       -- Porting note: `Sigma.mk.inj_iff` required because `simp` behaves differently
       simp only [toFinmap_cons, *, not_mem_empty, exists_or, not_mem_nil, toFinmap_nil,
         exists_false, mem_cons, mem_insert, exists_and_left, Sigma.mk.inj_iff];
       apply or_congr _ Iff.rfl
-  rename_i tail_ih fst_i snd_i
   conv =>
     lhs
     rw [← and_true_iff (a = fst_i)]

cea83e19

feat: add Finmap.keysLookupEquiv (#2359)

This is a forward-port of leanprover-community/mathlib#18151

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

4545ac2a

Diff

@@ -4,12 +4,12 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Sean Leather, Mario Carneiro
 
 ! This file was ported from Lean 3 source module data.finmap
-! leanprover-community/mathlib commit c3fc15b26b3ff8958ec3e5711177a9ae3d5c45b7
+! leanprover-community/mathlib commit cea83e192eae2d368ab2b500a0975667da42c920
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
 import Mathlib.Data.List.AList
-import Mathlib.Data.Finset.Basic
+import Mathlib.Data.Finset.Sigma
 import Mathlib.Data.Part
 
 /-!
@@ -47,6 +47,14 @@ theorem coe_nodupKeys {l : List (Sigma β)} : @NodupKeys α β l ↔ l.NodupKeys
   Iff.rfl
 #align multiset.coe_nodupkeys Multiset.coe_nodupKeys
 
+lemma nodup_keys {m : Multiset (Σ a, β a)} : m.keys.Nodup ↔ m.NodupKeys := by
+  rcases m with ⟨l⟩; rfl
+
+alias nodup_keys ↔ _ NodupKeys.nodup_keys
+
+protected lemma NodupKeys.nodup {m : Multiset (Σ a, β a)} (h : m.NodupKeys) : m.Nodup :=
+  h.nodup_keys.of_map _
+
 end Multiset
 
 /-! ### Finmap -/
@@ -89,6 +97,8 @@ namespace Finmap
 
 open AList
 
+lemma nodup_entries (f : Finmap β) : f.entries.Nodup := f.nodupKeys.nodup
+
 /-! ### Lifting from AList -/
 
 /-- Lift a permutation-respecting function on `AList` to `Finmap`. -/
@@ -180,7 +190,7 @@ theorem mem_toFinmap {a : α} {s : AList β} : a ∈ toFinmap s ↔ a ∈ s :=
 
 /-- The set of keys of a finite map. -/
 def keys (s : Finmap β) : Finset α :=
-  ⟨s.entries.keys, induction_on s keys_nodup⟩
+  ⟨s.entries.keys, s.nodupKeys.nodup_keys⟩
 #align finmap.keys Finmap.keys
 
 @[simp]
@@ -281,6 +291,19 @@ theorem lookup_eq_none {a} {s : Finmap β} : lookup a s = none ↔ a ∉ s :=
   induction_on s fun _ => AList.lookup_eq_none
 #align finmap.lookup_eq_none Finmap.lookup_eq_none
 
+lemma mem_lookup_iff {s : Finmap β} {a : α} {b : β a} :
+    b ∈ s.lookup a ↔ Sigma.mk a b ∈ s.entries := by
+  rcases s with ⟨⟨l⟩, hl⟩; exact List.mem_dlookup_iff hl
+
+lemma lookup_eq_some_iff {s : Finmap β} {a : α} {b : β a} :
+    s.lookup a = b ↔ Sigma.mk a b ∈ s.entries := mem_lookup_iff
+
+@[simp] lemma sigma_keys_lookup (s : Finmap β) :
+    s.keys.sigma (fun i => (s.lookup i).toFinset) = ⟨s.entries, s.nodup_entries⟩ := by
+  ext x
+  have : x ∈ s.entries → x.1 ∈ s.keys := Multiset.mem_map_of_mem _
+  simpa [lookup_eq_some_iff]
+
 @[simp]
 theorem lookup_singleton_eq {a : α} {b : β a} : (singleton a b).lookup a = some b := by
   rw [singleton, lookup_toFinmap, AList.singleton, AList.lookup, dlookup_cons_eq]
@@ -307,6 +330,36 @@ theorem ext_lookup {s₁ s₂ : Finmap β} : (∀ x, s₁.lookup x = s₂.lookup
     rw [h]
 #align finmap.ext_lookup Finmap.ext_lookup
 
+/-- An equivalence between `Finmap β` and pairs `(keys : Finset α, lookup : ∀ a, Option (β a))` such
+that `(lookup a).isSome ↔ a ∈ keys`. -/
+@[simps apply_coe_fst apply_coe_snd]
+def keysLookupEquiv :
+    Finmap β ≃ { f : Finset α × (∀ a, Option (β a)) // ∀ i, (f.2 i).isSome ↔ i ∈ f.1 } where
+  toFun s := ⟨(s.keys, fun i => s.lookup i), fun _ => lookup_isSome⟩
+  invFun f := mk (f.1.1.sigma <| fun i => (f.1.2 i).toFinset).val <| by
+    refine Multiset.nodup_keys.1 ((Finset.nodup _).map_on ?_)
+    simp only [Finset.mem_val, Finset.mem_sigma, Option.mem_toFinset, Option.mem_def]
+    rintro ⟨i, x⟩ ⟨_, hx⟩ ⟨j, y⟩ ⟨_, hy⟩ (rfl : i = j)
+    simpa using hx.symm.trans hy
+  left_inv f := ext <| by simp
+  right_inv := fun ⟨(s, f), hf⟩ => by
+    dsimp only at hf
+    ext
+    · simp [keys, Multiset.keys, ← hf, Option.isSome_iff_exists]
+    · simp (config := { contextual := true }) [lookup_eq_some_iff, ← hf]
+
+@[simp] lemma keysLookupEquiv_symm_apply_keys :
+    ∀ f : {f : Finset α × (∀ a, Option (β a)) // ∀ i, (f.2 i).isSome ↔ i ∈ f.1},
+      (keysLookupEquiv.symm f).keys = f.1.1 :=
+  keysLookupEquiv.surjective.forall.2 $ fun _ => by
+    simp only [Equiv.symm_apply_apply, keysLookupEquiv_apply_coe_fst]
+
+@[simp] lemma keysLookupEquiv_symm_apply_lookup :
+    ∀ (f : {f : Finset α × (∀ a, Option (β a)) // ∀ i, (f.2 i).isSome ↔ i ∈ f.1}) a,
+      (keysLookupEquiv.symm f).lookup a = f.1.2 a :=
+  keysLookupEquiv.surjective.forall.2 $ fun _ _ => by
+    simp only [Equiv.symm_apply_apply, keysLookupEquiv_apply_coe_snd]
+
 /-! ### replace -/
 
 /-- Replace a key with a given value in a finite map.

c3fc15b2

fix: forward-port leanprover-community/mathlib#18432 (#3006)

ade63fc3

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Sean Leather, Mario Carneiro
 
 ! This file was ported from Lean 3 source module data.finmap
-! leanprover-community/mathlib commit 9003f28797c0664a49e4179487267c494477d853
+! leanprover-community/mathlib commit c3fc15b26b3ff8958ec3e5711177a9ae3d5c45b7
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -345,13 +345,15 @@ def foldl {δ : Type w} (f : δ → ∀ a, β a → δ)
 
 /-- `any f s` returns `true` iff there exists a value `v` in `s` such that `f v = true`. -/
 def any (f : ∀ x, β x → Bool) (s : Finmap β) : Bool :=
-  s.foldl (fun x y z => x ∨ f y z) (fun _ _ _ _ => by simp [or_right_comm]) false
+  s.foldl (fun x y z => x || f y z)
+    (fun _ _ _ _ => by simp_rw [Bool.or_assoc, Bool.or_comm, imp_true_iff]) false
 #align finmap.any Finmap.any
 
 -- TODO: should this really return `false` if `s` is empty?
 /-- `all f s` returns `true` iff `f v = true` for all values `v` in `s`. -/
 def all (f : ∀ x, β x → Bool) (s : Finmap β) : Bool :=
-  s.foldl (fun x y z => x ∧ f y z) (fun _ _ _ _ => by simp [and_right_comm]) false
+  s.foldl (fun x y z => x && f y z)
+    (fun _ _ _ _ => by simp_rw [Bool.and_assoc, Bool.and_comm, imp_true_iff]) true
 #align finmap.all Finmap.all
 
 /-! ### erase -/

9003f287

chore: tidy various files (#2236)

a2ebfa0b

Diff

@@ -65,7 +65,6 @@ def AList.toFinmap (s : AList β) : Finmap β :=
   ⟨s.entries, s.nodupKeys⟩
 #align alist.to_finmap AList.toFinmap
 
--- mathport name: to_finmap
 local notation:arg "⟦" a "⟧" => AList.toFinmap a
 
 theorem AList.toFinmap_eq {s₁ s₂ : AList β} :
@@ -95,8 +94,7 @@ open AList
 /-- Lift a permutation-respecting function on `AList` to `Finmap`. -/
 -- @[elab_as_elim] Porting note: we can't add `elab_as_elim` attr in this type
 def liftOn {γ} (s : Finmap β) (f : AList β → γ)
-    (H : ∀ a b : AList β, a.entries ~ b.entries → f a = f b) : γ :=
-  by
+    (H : ∀ a b : AList β, a.entries ~ b.entries → f a = f b) : γ := by
   refine'
     (Quotient.liftOn s.entries
       (fun (l : List (Sigma β)) => (⟨_, fun nd => f ⟨l, nd⟩⟩ : Part γ))
@@ -248,9 +246,9 @@ section
 
 variable [DecidableEq α]
 
-instance hasDecidableEq [∀ a, DecidableEq (β a)] : DecidableEq (Finmap β)
+instance decidableEq [∀ a, DecidableEq (β a)] : DecidableEq (Finmap β)
   | _, _ => decidable_of_iff _ ext_iff
-#align finmap.has_decidable_eq Finmap.hasDecidableEq
+#align finmap.has_decidable_eq Finmap.decidableEq
 
 /-! ### lookup -/
 
@@ -301,8 +299,7 @@ theorem mem_of_lookup_eq_some {a : α} {b : β a} {s : Finmap β} (h : s.lookup
 #align finmap.mem_of_lookup_eq_some Finmap.mem_of_lookup_eq_some
 
 theorem ext_lookup {s₁ s₂ : Finmap β} : (∀ x, s₁.lookup x = s₂.lookup x) → s₁ = s₂ :=
-  induction_on₂ s₁ s₂ fun s₁ s₂ h =>
-    by
+  induction_on₂ s₁ s₂ fun s₁ s₂ h => by
     simp only [AList.lookup, lookup_toFinmap] at h
     rw [AList.toFinmap_eq]
     apply lookup_ext s₁.nodupKeys s₂.nodupKeys
@@ -348,20 +345,13 @@ def foldl {δ : Type w} (f : δ → ∀ a, β a → δ)
 
 /-- `any f s` returns `true` iff there exists a value `v` in `s` such that `f v = true`. -/
 def any (f : ∀ x, β x → Bool) (s : Finmap β) : Bool :=
-  s.foldl (fun x y z => x ∨ f y z)
-    (by
-      intros
-      simp [or_right_comm])
-    false
+  s.foldl (fun x y z => x ∨ f y z) (fun _ _ _ _ => by simp [or_right_comm]) false
 #align finmap.any Finmap.any
 
+-- TODO: should this really return `false` if `s` is empty?
 /-- `all f s` returns `true` iff `f v = true` for all values `v` in `s`. -/
 def all (f : ∀ x, β x → Bool) (s : Finmap β) : Bool :=
-  s.foldl (fun x y z => x ∧ f y z)
-    (by
-      intros
-      simp [and_right_comm])
-    false
+  s.foldl (fun x y z => x ∧ f y z) (fun _ _ _ _ => by simp [and_right_comm]) false
 #align finmap.all Finmap.all
 
 /-! ### erase -/
@@ -482,8 +472,7 @@ theorem toFinmap_cons (a : α) (b : β a) (xs : List (Sigma β)) :
 #align finmap.to_finmap_cons Finmap.toFinmap_cons
 
 theorem mem_list_toFinmap (a : α) (xs : List (Sigma β)) :
-    a ∈ xs.toFinmap ↔ ∃ b : β a, Sigma.mk a b ∈ xs :=
-  by
+    a ∈ xs.toFinmap ↔ ∃ b : β a, Sigma.mk a b ∈ xs := by
   induction' xs with x xs <;> [skip, cases x] <;>
       -- Porting note: `Sigma.mk.inj_iff` required because `simp` behaves differently
       simp only [toFinmap_cons, *, not_mem_empty, exists_or, not_mem_nil, toFinmap_nil,
@@ -553,8 +542,7 @@ theorem lookup_union_right {a} {s₁ s₂ : Finmap β} : a ∉ s₁ → lookup a
 #align finmap.lookup_union_right Finmap.lookup_union_right
 
 theorem lookup_union_left_of_not_in {a} {s₁ s₂ : Finmap β} (h : a ∉ s₂) :
-    lookup a (s₁ ∪ s₂) = lookup a s₁ :=
-  by
+    lookup a (s₁ ∪ s₂) = lookup a s₁ := by
   by_cases h' : a ∈ s₁
   · rw [lookup_union_left h']
   · rw [lookup_union_right h', lookup_eq_none.mpr h, lookup_eq_none.mpr h']
@@ -583,15 +571,15 @@ theorem union_assoc {s₁ s₂ s₃ : Finmap β} : s₁ ∪ s₂ ∪ s₃ = s₁
 @[simp]
 theorem empty_union {s₁ : Finmap β} : ∅ ∪ s₁ = s₁ :=
   induction_on s₁ fun s₁ => by
-    rw [← empty_toFinmap];
-      simp [-empty_toFinmap, AList.toFinmap_eq, union_toFinmap, AList.union_assoc]
+    rw [← empty_toFinmap]
+    simp [-empty_toFinmap, AList.toFinmap_eq, union_toFinmap, AList.union_assoc]
 #align finmap.empty_union Finmap.empty_union
 
 @[simp]
 theorem union_empty {s₁ : Finmap β} : s₁ ∪ ∅ = s₁ :=
   induction_on s₁ fun s₁ => by
-    rw [← empty_toFinmap];
-      simp [-empty_toFinmap, AList.toFinmap_eq, union_toFinmap, AList.union_assoc]
+    rw [← empty_toFinmap]
+    simp [-empty_toFinmap, AList.toFinmap_eq, union_toFinmap, AList.union_assoc]
 #align finmap.union_empty Finmap.union_empty
 
 theorem erase_union_singleton (a : α) (b : β a) (s : Finmap β) (h : s.lookup a = some b) :

9003f287

feat: port Data.Finmap (#1591)

Co-authored-by: Arien Malec <arien.malec@gmail.com> Co-authored-by: qawbecrdtey <qawbecrdtey@naver.com> Co-authored-by: Komyyy <pol_tta@outlook.jp>

70430c95

`data.finmap` ⟷ `Mathlib.Data.Finmap`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 2 + 172

data.finmap ⟷ Mathlib.Data.Finmap

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 2 + 172

`data.finmap` ⟷ `Mathlib.Data.Finmap`