data.list.alist | 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

f808feb6

(last sync)

feat(data/list/alist): recursion on alist using insert (#15434)

Diff

@@ -205,6 +205,11 @@ theorem insert_entries_of_neg {a} {b : β a} {s : alist β} (h : a ∉ s) :
   (insert a b s).entries = ⟨a, b⟩ :: s.entries :=
 by rw [insert_entries, kerase_of_not_mem_keys h]
 
+-- Todo: rename to `insert_of_not_mem`.
+theorem insert_of_neg {a} {b : β a} {s : alist β} (h : a ∉ s) :
+  insert a b s = ⟨⟨a, b⟩ :: s.entries, nodupkeys_cons.2 ⟨h, s.2⟩⟩ :=
+ext $ insert_entries_of_neg h
+
 @[simp] theorem insert_empty (a) (b : β a) : insert a b ∅ = singleton a b := rfl
 
 @[simp] theorem mem_insert {a a'} {b' : β a'} (s : alist β) :
@@ -250,6 +255,50 @@ ext $ by simp only [alist.insert_entries, list.kerase_cons_eq, and_self, alist.s
 theorem to_alist_cons (a : α) (b : β a) (xs : list (sigma β)) :
   list.to_alist (⟨a,b⟩ :: xs) = insert a b xs.to_alist := rfl
 
+theorem mk_cons_eq_insert (c : sigma β) (l : list (sigma β)) (h : (c :: l).nodupkeys) :
+  (⟨c :: l, h⟩ : alist β) = insert c.1 c.2 ⟨l, nodupkeys_of_nodupkeys_cons h⟩ :=
+by simpa [insert] using (kerase_of_not_mem_keys $ not_mem_keys_of_nodupkeys_cons h).symm
+
+/-- Recursion on an `alist`, using `insert`. Use as `induction l using alist.insert_rec`. -/
+@[elab_as_eliminator] def insert_rec {C : alist β → Sort*} (H0 : C ∅)
+  (IH : Π (a : α) (b : β a) (l : alist β) (h : a ∉ l), C l → C (l.insert a b)) : Π l : alist β, C l
+| ⟨[], _⟩     := H0
+| ⟨c :: l, h⟩ := begin
+  rw mk_cons_eq_insert,
+  refine IH _ _ _ _ (insert_rec _),
+  exact not_mem_keys_of_nodupkeys_cons h
+end
+
+-- Test that the `induction` tactic works on `insert_rec`.
+example (l : alist β) : true := by induction l using alist.insert_rec; trivial
+
+@[simp] theorem insert_rec_empty {C : alist β → Sort*} (H0 : C ∅)
+  (IH : Π (a : α) (b : β a) (l : alist β) (h : a ∉ l), C l → C (l.insert a b)) :
+  @insert_rec α β _ C H0 IH ∅ = H0 :=
+by { change @insert_rec α β _ C H0 IH ⟨[], _⟩ = H0, rw insert_rec }
+
+theorem insert_rec_insert {C : alist β → Sort*} (H0 : C ∅)
+  (IH : Π (a : α) (b : β a) (l : alist β) (h : a ∉ l), C l → C (l.insert a b))
+  {c : sigma β} {l : alist β} (h : c.1 ∉ l) :
+  @insert_rec α β _ C H0 IH (l.insert c.1 c.2) = IH c.1 c.2 l h (@insert_rec α β _ C H0 IH l) :=
+begin
+  cases l with l hl,
+  suffices : @insert_rec α β _ C H0 IH ⟨c :: l, nodupkeys_cons.2 ⟨h, hl⟩⟩ ==
+    IH c.1 c.2 ⟨l, hl⟩ h (@insert_rec α β _ C H0 IH ⟨l, hl⟩),
+  { cases c,
+    apply eq_of_heq,
+    convert this;
+      rw insert_of_neg h },
+  rw insert_rec,
+  apply cast_heq
+end
+
+theorem recursion_insert_mk {C : alist β → Sort*} (H0 : C ∅)
+  (IH : Π (a : α) (b : β a) (l : alist β) (h : a ∉ l), C l → C (l.insert a b))
+  {a : α} (b : β a) {l : alist β} (h : a ∉ l) :
+  @insert_rec α β _ C H0 IH (l.insert a b) = IH a b l h (@insert_rec α β _ C H0 IH l) :=
+@insert_rec_insert α β _ C H0 IH ⟨a, b⟩ l h
+
 /-! ### extract -/
 
 /-- Erase a key from the map, and return the corresponding value, if found. -/

9003f287

(first ported)

Changes in mathlib3port

mathlib3

mathlib3port

f808feb6

bump to nightly-2024-04-25-08

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

ad7a2212

Diff

@@ -615,7 +615,7 @@ theorem insert_union {a} {b : β a} {s₁ s₂ : AList β} : insert a b (s₁ 
 #print AList.union_assoc /-
 theorem union_assoc {s₁ s₂ s₃ : AList β} : (s₁ ∪ s₂ ∪ s₃).entries ~ (s₁ ∪ (s₂ ∪ s₃)).entries :=
   lookup_ext (AList.nodupKeys _) (AList.nodupKeys _)
-    (by simp [Decidable.not_or_iff_and_not, or_assoc', and_or_left, and_assoc'])
+    (by simp [Decidable.not_or_iff_and_not, or_assoc, and_or_left, and_assoc])
 #align alist.union_assoc AList.union_assoc
 -/

f808feb6

bump to nightly-2023-09-24-06

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

5655435f

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 Mathbin.Data.List.Sigma
+import Data.List.Sigma
 
 #align_import data.list.alist from "leanprover-community/mathlib"@"f808feb6c18afddb25e66a71d317643cf7fb5fbb"

f808feb6

bump to nightly-2023-07-20-09

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

9c56d0dd

Diff

@@ -2,14 +2,11 @@
 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.list.alist
-! leanprover-community/mathlib commit f808feb6c18afddb25e66a71d317643cf7fb5fbb
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Data.List.Sigma
 
+#align_import data.list.alist from "leanprover-community/mathlib"@"f808feb6c18afddb25e66a71d317643cf7fb5fbb"
+
 /-!
 # Association Lists

f808feb6

bump to nightly-2023-06-13-21

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

829520ac

Diff

@@ -280,10 +280,12 @@ def erase (a : α) (s : AList β) : AList β :=
 #align alist.erase AList.erase
 -/
 
+#print AList.keys_erase /-
 @[simp]
 theorem keys_erase (a : α) (s : AList β) : (erase a s).keys = s.keys.eraseₓ a :=
   keys_kerase
 #align alist.keys_erase AList.keys_erase
+-/
 
 #print AList.mem_erase /-
 @[simp]
@@ -366,10 +368,12 @@ theorem mem_insert {a a'} {b' : β a'} (s : AList β) : a ∈ insert a' b' s ↔
 #align alist.mem_insert AList.mem_insert
 -/
 
+#print AList.keys_insert /-
 @[simp]
 theorem keys_insert {a} {b : β a} (s : AList β) : (insert a b s).keys = a :: s.keys.eraseₓ a := by
   simp [insert, keys, keys_kerase]
 #align alist.keys_insert AList.keys_insert
+-/
 
 #print AList.perm_insert /-
 theorem perm_insert {a} {b : β a} {s₁ s₂ : AList β} (p : s₁.entries ~ s₂.entries) :
@@ -463,13 +467,16 @@ def insertRec {C : AList β → Sort _} (H0 : C ∅)
 -- Test that the `induction` tactic works on `insert_rec`.
 example (l : AList β) : True := by induction l using AList.insertRec <;> trivial
 
+#print AList.insertRec_empty /-
 @[simp]
 theorem insertRec_empty {C : AList β → Sort _} (H0 : C ∅)
     (IH : ∀ (a : α) (b : β a) (l : AList β) (h : a ∉ l), C l → C (l.insert a b)) :
     @insertRec α β _ C H0 IH ∅ = H0 := by change @insert_rec α β _ C H0 IH ⟨[], _⟩ = H0;
   rw [insert_rec]
 #align alist.insert_rec_empty AList.insertRec_empty
+-/
 
+#print AList.insertRec_insert /-
 theorem insertRec_insert {C : AList β → Sort _} (H0 : C ∅)
     (IH : ∀ (a : α) (b : β a) (l : AList β) (h : a ∉ l), C l → C (l.insert a b)) {c : Sigma β}
     {l : AList β} (h : c.1 ∉ l) :
@@ -486,13 +493,16 @@ theorem insertRec_insert {C : AList β → Sort _} (H0 : C ∅)
   rw [insert_rec]
   apply cast_hEq
 #align alist.insert_rec_insert AList.insertRec_insert
+-/
 
+#print AList.insertRec_insert_mk /-
 theorem insertRec_insert_mk {C : AList β → Sort _} (H0 : C ∅)
     (IH : ∀ (a : α) (b : β a) (l : AList β) (h : a ∉ l), C l → C (l.insert a b)) {a : α} (b : β a)
     {l : AList β} (h : a ∉ l) :
     @insertRec α β _ C H0 IH (l.insert a b) = IH a b l h (@insertRec α β _ C H0 IH l) :=
   @insertRec_insert α β _ C H0 IH ⟨a, b⟩ l h
 #align alist.recursion_insert_mk AList.insertRec_insert_mk
+-/
 
 /-! ### extract -/

f808feb6

bump to nightly-2023-06-01-16

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

b9c87c70

Diff

@@ -412,7 +412,7 @@ theorem insert_insert {a} {b b' : β a} (s : AList β) : (s.insert a b).insert a
 theorem insert_insert_of_ne {a a'} {b : β a} {b' : β a'} (s : AList β) (h : a ≠ a') :
     ((s.insert a b).insert a' b').entries ~ ((s.insert a' b').insert a b).entries := by
   simp only [insert_entries] <;> rw [kerase_cons_ne, kerase_cons_ne, kerase_comm] <;>
-    [apply perm.swap;exact h;exact h.symm]
+    [apply perm.swap; exact h; exact h.symm]
 #align alist.insert_insert_of_ne AList.insert_insert_of_ne
 -/
 
@@ -631,7 +631,7 @@ theorem union_comm_of_disjoint {s₁ s₂ : AList β} (h : Disjoint s₁ s₂) :
     (s₁ ∪ s₂).entries ~ (s₂ ∪ s₁).entries :=
   lookup_ext (AList.nodupKeys _) (AList.nodupKeys _)
     (by
-      intros ; simp
+      intros; simp
       constructor <;> intro h'
       cases h'
       · right; refine' ⟨_, h'⟩

f808feb6

bump to nightly-2023-05-28-06

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

ba5d8b97

Diff

@@ -280,12 +280,6 @@ def erase (a : α) (s : AList β) : AList β :=
 #align alist.erase AList.erase
 -/
 
-/- warning: alist.keys_erase -> AList.keys_erase is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {β : α -> Type.{u2}} [_inst_1 : DecidableEq.{succ u1} α] (a : α) (s : AList.{u1, u2} α β), Eq.{succ u1} (List.{u1} α) (AList.keys.{u1, u2} α β (AList.erase.{u1, u2} α β (fun (a : α) (b : α) => _inst_1 a b) a s)) (List.eraseₓ.{u1} α (fun (a : α) (b : α) => _inst_1 a b) (AList.keys.{u1, u2} α β s) a)
-but is expected to have type
-  forall {α : Type.{u1}} {β : α -> Type.{u2}} [_inst_1 : DecidableEq.{succ u1} α] (a : α) (s : AList.{u1, u2} α β), Eq.{succ u1} (List.{u1} α) (AList.keys.{u1, u2} α β (AList.erase.{u1, u2} α β (fun (a : α) (b : α) => _inst_1 a b) a s)) (List.erase.{u1} α (instBEq.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (AList.keys.{u1, u2} α β s) a)
-Case conversion may be inaccurate. Consider using '#align alist.keys_erase AList.keys_eraseₓ'. -/
 @[simp]
 theorem keys_erase (a : α) (s : AList β) : (erase a s).keys = s.keys.eraseₓ a :=
   keys_kerase
@@ -372,12 +366,6 @@ theorem mem_insert {a a'} {b' : β a'} (s : AList β) : a ∈ insert a' b' s ↔
 #align alist.mem_insert AList.mem_insert
 -/
 
-/- warning: alist.keys_insert -> AList.keys_insert is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {β : α -> Type.{u2}} [_inst_1 : DecidableEq.{succ u1} α] {a : α} {b : β a} (s : AList.{u1, u2} α β), Eq.{succ u1} (List.{u1} α) (AList.keys.{u1, u2} α (fun {a : α} => β a) (AList.insert.{u1, u2} α (fun {a : α} => β a) (fun (a : α) (b : α) => _inst_1 a b) a b s)) (List.cons.{u1} α a (List.eraseₓ.{u1} α (fun (a : α) (b : α) => _inst_1 a b) (AList.keys.{u1, u2} α β s) a))
-but is expected to have type
-  forall {α : Type.{u1}} {β : α -> Type.{u2}} [_inst_1 : DecidableEq.{succ u1} α] {a : α} {b : β a} (s : AList.{u1, u2} α β), Eq.{succ u1} (List.{u1} α) (AList.keys.{u1, u2} α β (AList.insert.{u1, u2} α β (fun (a : α) (b : α) => _inst_1 a b) a b s)) (List.cons.{u1} α a (List.erase.{u1} α (instBEq.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (AList.keys.{u1, u2} α β s) a))
-Case conversion may be inaccurate. Consider using '#align alist.keys_insert AList.keys_insertₓ'. -/
 @[simp]
 theorem keys_insert {a} {b : β a} (s : AList β) : (insert a b s).keys = a :: s.keys.eraseₓ a := by
   simp [insert, keys, keys_kerase]
@@ -475,12 +463,6 @@ def insertRec {C : AList β → Sort _} (H0 : C ∅)
 -- Test that the `induction` tactic works on `insert_rec`.
 example (l : AList β) : True := by induction l using AList.insertRec <;> trivial
 
-/- warning: alist.insert_rec_empty -> AList.insertRec_empty is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {β : α -> Type.{u2}} [_inst_1 : DecidableEq.{succ u1} α] {C : (AList.{u1, u2} α β) -> Sort.{u3}} (H0 : C (EmptyCollection.emptyCollection.{max u1 u2} (AList.{u1, u2} α β) (AList.hasEmptyc.{u1, u2} α β))) (IH : forall (a : α) (b : β a) (l : AList.{u1, u2} α β), (Not (Membership.Mem.{u1, max u1 u2} α (AList.{u1, u2} α β) (AList.hasMem.{u1, u2} α β) a l)) -> (C l) -> (C (AList.insert.{u1, u2} α β (fun (a : α) (b : α) => _inst_1 a b) a b l))), Eq.{u3} (C (EmptyCollection.emptyCollection.{max u1 u2} (AList.{u1, u2} α β) (AList.hasEmptyc.{u1, u2} α β))) (AList.insertRec.{u1, u2, u3} α β (fun (a : α) (b : α) => _inst_1 a b) C H0 IH (EmptyCollection.emptyCollection.{max u1 u2} (AList.{u1, u2} α β) (AList.hasEmptyc.{u1, u2} α β))) H0
-but is expected to have type
-  forall {α : Type.{u2}} {β : α -> Type.{u3}} [_inst_1 : DecidableEq.{succ u2} α] {C : (AList.{u2, u3} α β) -> Sort.{u1}} (H0 : C (EmptyCollection.emptyCollection.{max u2 u3} (AList.{u2, u3} α β) (AList.instEmptyCollectionAList.{u2, u3} α β))) (IH : forall (a : α) (b : β a) (l : AList.{u2, u3} α β), (Not (Membership.mem.{u2, max u2 u3} α (AList.{u2, u3} α β) (AList.instMembershipAList.{u2, u3} α β) a l)) -> (C l) -> (C (AList.insert.{u2, u3} α β (fun (a : α) (b : α) => _inst_1 a b) a b l))), Eq.{u1} (C (EmptyCollection.emptyCollection.{max u2 u3} (AList.{u2, u3} α β) (AList.instEmptyCollectionAList.{u2, u3} α β))) (AList.insertRec.{u2, u3, u1} α β (fun (a : α) (b : α) => _inst_1 a b) C H0 IH (EmptyCollection.emptyCollection.{max u2 u3} (AList.{u2, u3} α β) (AList.instEmptyCollectionAList.{u2, u3} α β))) H0
-Case conversion may be inaccurate. Consider using '#align alist.insert_rec_empty AList.insertRec_emptyₓ'. -/
 @[simp]
 theorem insertRec_empty {C : AList β → Sort _} (H0 : C ∅)
     (IH : ∀ (a : α) (b : β a) (l : AList β) (h : a ∉ l), C l → C (l.insert a b)) :
@@ -488,12 +470,6 @@ theorem insertRec_empty {C : AList β → Sort _} (H0 : C ∅)
   rw [insert_rec]
 #align alist.insert_rec_empty AList.insertRec_empty
 
-/- warning: alist.insert_rec_insert -> AList.insertRec_insert is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {β : α -> Type.{u2}} [_inst_1 : DecidableEq.{succ u1} α] {C : (AList.{u1, u2} α β) -> Sort.{u3}} (H0 : C (EmptyCollection.emptyCollection.{max u1 u2} (AList.{u1, u2} α β) (AList.hasEmptyc.{u1, u2} α β))) (IH : forall (a : α) (b : β a) (l : AList.{u1, u2} α β), (Not (Membership.Mem.{u1, max u1 u2} α (AList.{u1, u2} α β) (AList.hasMem.{u1, u2} α β) a l)) -> (C l) -> (C (AList.insert.{u1, u2} α β (fun (a : α) (b : α) => _inst_1 a b) a b l))) {c : Sigma.{u1, u2} α β} {l : AList.{u1, u2} α β} (h : Not (Membership.Mem.{u1, max u1 u2} α (AList.{u1, u2} α β) (AList.hasMem.{u1, u2} α β) (Sigma.fst.{u1, u2} α β c) l)), Eq.{u3} (C (AList.insert.{u1, u2} α β (fun (a : α) (b : α) => _inst_1 a b) (Sigma.fst.{u1, u2} α β c) (Sigma.snd.{u1, u2} α β c) l)) (AList.insertRec.{u1, u2, u3} α β (fun (a : α) (b : α) => _inst_1 a b) C H0 IH (AList.insert.{u1, u2} α β (fun (a : α) (b : α) => _inst_1 a b) (Sigma.fst.{u1, u2} α β c) (Sigma.snd.{u1, u2} α β c) l)) (IH (Sigma.fst.{u1, u2} α β c) (Sigma.snd.{u1, u2} α β c) l h (AList.insertRec.{u1, u2, u3} α β (fun (a : α) (b : α) => _inst_1 a b) C H0 IH l))
-but is expected to have type
-  forall {α : Type.{u2}} {β : α -> Type.{u3}} [_inst_1 : DecidableEq.{succ u2} α] {C : (AList.{u2, u3} α β) -> Sort.{u1}} (H0 : C (EmptyCollection.emptyCollection.{max u2 u3} (AList.{u2, u3} α β) (AList.instEmptyCollectionAList.{u2, u3} α β))) (IH : forall (a : α) (b : β a) (l : AList.{u2, u3} α β), (Not (Membership.mem.{u2, max u2 u3} α (AList.{u2, u3} α β) (AList.instMembershipAList.{u2, u3} α β) a l)) -> (C l) -> (C (AList.insert.{u2, u3} α β (fun (a : α) (b : α) => _inst_1 a b) a b l))) {c : Sigma.{u2, u3} α β} {l : AList.{u2, u3} α β} (h : Not (Membership.mem.{u2, max u2 u3} α (AList.{u2, u3} α β) (AList.instMembershipAList.{u2, u3} α β) (Sigma.fst.{u2, u3} α β c) l)), Eq.{u1} (C (AList.insert.{u2, u3} α β (fun (a : α) (b : α) => _inst_1 a b) (Sigma.fst.{u2, u3} α β c) (Sigma.snd.{u2, u3} α β c) l)) (AList.insertRec.{u2, u3, u1} α β (fun (a : α) (b : α) => _inst_1 a b) C H0 IH (AList.insert.{u2, u3} α β (fun (a : α) (b : α) => _inst_1 a b) (Sigma.fst.{u2, u3} α β c) (Sigma.snd.{u2, u3} α β c) l)) (IH (Sigma.fst.{u2, u3} α β c) (Sigma.snd.{u2, u3} α β c) l h (AList.insertRec.{u2, u3, u1} α β (fun (a : α) (b : α) => _inst_1 a b) C H0 IH l))
-Case conversion may be inaccurate. Consider using '#align alist.insert_rec_insert AList.insertRec_insertₓ'. -/
 theorem insertRec_insert {C : AList β → Sort _} (H0 : C ∅)
     (IH : ∀ (a : α) (b : β a) (l : AList β) (h : a ∉ l), C l → C (l.insert a b)) {c : Sigma β}
     {l : AList β} (h : c.1 ∉ l) :
@@ -511,12 +487,6 @@ theorem insertRec_insert {C : AList β → Sort _} (H0 : C ∅)
   apply cast_hEq
 #align alist.insert_rec_insert AList.insertRec_insert
 
-/- warning: alist.recursion_insert_mk -> AList.insertRec_insert_mk is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {β : α -> Type.{u2}} [_inst_1 : DecidableEq.{succ u1} α] {C : (AList.{u1, u2} α β) -> Sort.{u3}} (H0 : C (EmptyCollection.emptyCollection.{max u1 u2} (AList.{u1, u2} α β) (AList.hasEmptyc.{u1, u2} α β))) (IH : forall (a : α) (b : β a) (l : AList.{u1, u2} α β), (Not (Membership.Mem.{u1, max u1 u2} α (AList.{u1, u2} α β) (AList.hasMem.{u1, u2} α β) a l)) -> (C l) -> (C (AList.insert.{u1, u2} α β (fun (a : α) (b : α) => _inst_1 a b) a b l))) {a : α} (b : β a) {l : AList.{u1, u2} α β} (h : Not (Membership.Mem.{u1, max u1 u2} α (AList.{u1, u2} α β) (AList.hasMem.{u1, u2} α β) a l)), Eq.{u3} (C (AList.insert.{u1, u2} α β (fun (a : α) (b : α) => _inst_1 a b) a b l)) (AList.insertRec.{u1, u2, u3} α β (fun (a : α) (b : α) => _inst_1 a b) C H0 IH (AList.insert.{u1, u2} α β (fun (a : α) (b : α) => _inst_1 a b) a b l)) (IH a b l h (AList.insertRec.{u1, u2, u3} α β (fun (a : α) (b : α) => _inst_1 a b) C H0 IH l))
-but is expected to have type
-  forall {α : Type.{u2}} {β : α -> Type.{u3}} [_inst_1 : DecidableEq.{succ u2} α] {C : (AList.{u2, u3} α β) -> Sort.{u1}} (H0 : C (EmptyCollection.emptyCollection.{max u2 u3} (AList.{u2, u3} α β) (AList.instEmptyCollectionAList.{u2, u3} α β))) (IH : forall (a : α) (b : β a) (l : AList.{u2, u3} α β), (Not (Membership.mem.{u2, max u2 u3} α (AList.{u2, u3} α β) (AList.instMembershipAList.{u2, u3} α β) a l)) -> (C l) -> (C (AList.insert.{u2, u3} α β (fun (a : α) (b : α) => _inst_1 a b) a b l))) {a : α} (b : β a) {l : AList.{u2, u3} α β} (h : Not (Membership.mem.{u2, max u2 u3} α (AList.{u2, u3} α β) (AList.instMembershipAList.{u2, u3} α β) a l)), Eq.{u1} (C (AList.insert.{u2, u3} α β (fun (a : α) (b : α) => _inst_1 a b) a b l)) (AList.insertRec.{u2, u3, u1} α β (fun (a : α) (b : α) => _inst_1 a b) C H0 IH (AList.insert.{u2, u3} α β (fun (a : α) (b : α) => _inst_1 a b) a b l)) (IH a b l h (AList.insertRec.{u2, u3, u1} α β (fun (a : α) (b : α) => _inst_1 a b) C H0 IH l))
-Case conversion may be inaccurate. Consider using '#align alist.recursion_insert_mk AList.insertRec_insert_mkₓ'. -/
 theorem insertRec_insert_mk {C : AList β → Sort _} (H0 : C ∅)
     (IH : ∀ (a : α) (b : β a) (l : AList β) (h : a ∉ l), C l → C (l.insert a b)) {a : α} (b : β a)
     {l : AList β} (h : a ∉ l) :

f808feb6

bump to nightly-2023-05-28-04

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

6797a637

Diff

@@ -484,9 +484,7 @@ Case conversion may be inaccurate. Consider using '#align alist.insert_rec_empty
 @[simp]
 theorem insertRec_empty {C : AList β → Sort _} (H0 : C ∅)
     (IH : ∀ (a : α) (b : β a) (l : AList β) (h : a ∉ l), C l → C (l.insert a b)) :
-    @insertRec α β _ C H0 IH ∅ = H0 :=
-  by
-  change @insert_rec α β _ C H0 IH ⟨[], _⟩ = H0
+    @insertRec α β _ C H0 IH ∅ = H0 := by change @insert_rec α β _ C H0 IH ⟨[], _⟩ = H0;
   rw [insert_rec]
 #align alist.insert_rec_empty AList.insertRec_empty
 
@@ -666,22 +664,13 @@ theorem union_comm_of_disjoint {s₁ s₂ : AList β} (h : Disjoint s₁ s₂) :
       intros ; simp
       constructor <;> intro h'
       cases h'
-      · right
-        refine' ⟨_, h'⟩
-        apply h
-        rw [keys, ← List.dlookup_isSome, h']
-        exact rfl
-      · left
-        rw [h'.2]
+      · right; refine' ⟨_, h'⟩
+        apply h; rw [keys, ← List.dlookup_isSome, h']; exact rfl
+      · left; rw [h'.2]
       cases h'
-      · right
-        refine' ⟨_, h'⟩
-        intro h''
-        apply h _ h''
-        rw [keys, ← List.dlookup_isSome, h']
-        exact rfl
-      · left
-        rw [h'.2])
+      · right; refine' ⟨_, h'⟩; intro h''
+        apply h _ h''; rw [keys, ← List.dlookup_isSome, h']; exact rfl
+      · left; rw [h'.2])
 #align alist.union_comm_of_disjoint AList.union_comm_of_disjoint
 -/

f808feb6

bump to nightly-2023-05-24-06

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

fbc7b476

Diff

@@ -424,7 +424,7 @@ theorem insert_insert {a} {b b' : β a} (s : AList β) : (s.insert a b).insert a
 theorem insert_insert_of_ne {a a'} {b : β a} {b' : β a'} (s : AList β) (h : a ≠ a') :
     ((s.insert a b).insert a' b').entries ~ ((s.insert a' b').insert a b).entries := by
   simp only [insert_entries] <;> rw [kerase_cons_ne, kerase_cons_ne, kerase_comm] <;>
-    [apply perm.swap, exact h, exact h.symm]
+    [apply perm.swap;exact h;exact h.symm]
 #align alist.insert_insert_of_ne AList.insert_insert_of_ne
 -/

f808feb6

bump to nightly-2023-03-21-22

mathlib commit https://github.com/leanprover-community/mathlib/commit/290a7ba01fbcab1b64757bdaa270d28f4dcede35

6ff56239

Diff

@@ -350,11 +350,13 @@ theorem insert_entries_of_neg {a} {b : β a} {s : AList β} (h : a ∉ s) :
 #align alist.insert_entries_of_neg AList.insert_entries_of_neg
 -/
 
+#print AList.insert_of_neg /-
 -- Todo: rename to `insert_of_not_mem`.
 theorem insert_of_neg {a} {b : β a} {s : AList β} (h : a ∉ s) :
     insert a b s = ⟨⟨a, b⟩ :: s.entries, nodupKeys_cons.2 ⟨h, s.2⟩⟩ :=
   ext <| insert_entries_of_neg h
 #align alist.insert_of_neg AList.insert_of_neg
+-/
 
 #print AList.insert_empty /-
 @[simp]
@@ -449,17 +451,14 @@ theorem toAList_cons (a : α) (b : β a) (xs : List (Sigma β)) :
 #align alist.to_alist_cons AList.toAList_cons
 -/
 
+#print AList.mk_cons_eq_insert /-
 theorem mk_cons_eq_insert (c : Sigma β) (l : List (Sigma β)) (h : (c :: l).NodupKeys) :
     (⟨c :: l, h⟩ : AList β) = insert c.1 c.2 ⟨l, nodupKeys_of_nodupKeys_cons h⟩ := by
   simpa [insert] using (kerase_of_not_mem_keys <| not_mem_keys_of_nodupkeys_cons h).symm
 #align alist.mk_cons_eq_insert AList.mk_cons_eq_insert
+-/
 
-/- warning: alist.insert_rec -> AList.insertRec is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {β : α -> Type.{u2}} [_inst_1 : DecidableEq.{succ u1} α] {C : (AList.{u1, u2} α β) -> Sort.{u3}}, (C (EmptyCollection.emptyCollection.{max u1 u2} (AList.{u1, u2} α β) (AList.hasEmptyc.{u1, u2} α β))) -> (forall (a : α) (b : β a) (l : AList.{u1, u2} α β), (Not (Membership.Mem.{u1, max u1 u2} α (AList.{u1, u2} α β) (AList.hasMem.{u1, u2} α β) a l)) -> (C l) -> (C (AList.insert.{u1, u2} α β (fun (a : α) (b : α) => _inst_1 a b) a b l))) -> (forall (l : AList.{u1, u2} α β), C l)
-but is expected to have type
-  forall {α : Type.{u2}} {β : α -> Type.{u3}} [_inst_1 : DecidableEq.{succ u2} α] {C : (AList.{u2, u3} α β) -> Sort.{u1}}, (C (EmptyCollection.emptyCollection.{max u2 u3} (AList.{u2, u3} α β) (AList.hasEmptyc.{u2, u3} α β))) -> (forall (a : α) (b : β a) (l : AList.{u2, u3} α β), (Not (Membership.Mem.{u2, max u2 u3} α (AList.{u2, u3} α β) (AList.hasMem.{u2, u3} α β) a l)) -> (C l) -> (C (AList.insert.{u2, u3} α β (fun (a : α) (b : α) => _inst_1 a b) a b l))) -> (forall (l : AList.{u2, u3} α β), C l)
-Case conversion may be inaccurate. Consider using '#align alist.insert_rec AList.insertRecₓ'. -/
+#print AList.insertRec /-
 /-- Recursion on an `alist`, using `insert`. Use as `induction l using alist.insert_rec`. -/
 @[elab_as_elim]
 def insertRec {C : AList β → Sort _} (H0 : C ∅)
@@ -471,10 +470,17 @@ def insertRec {C : AList β → Sort _} (H0 : C ∅)
     refine' IH _ _ _ _ (insert_rec _)
     exact not_mem_keys_of_nodupkeys_cons h
 #align alist.insert_rec AList.insertRec
+-/
 
 -- Test that the `induction` tactic works on `insert_rec`.
 example (l : AList β) : True := by induction l using AList.insertRec <;> trivial
 
+/- warning: alist.insert_rec_empty -> AList.insertRec_empty is a dubious translation:
+lean 3 declaration is
+  forall {α : Type.{u1}} {β : α -> Type.{u2}} [_inst_1 : DecidableEq.{succ u1} α] {C : (AList.{u1, u2} α β) -> Sort.{u3}} (H0 : C (EmptyCollection.emptyCollection.{max u1 u2} (AList.{u1, u2} α β) (AList.hasEmptyc.{u1, u2} α β))) (IH : forall (a : α) (b : β a) (l : AList.{u1, u2} α β), (Not (Membership.Mem.{u1, max u1 u2} α (AList.{u1, u2} α β) (AList.hasMem.{u1, u2} α β) a l)) -> (C l) -> (C (AList.insert.{u1, u2} α β (fun (a : α) (b : α) => _inst_1 a b) a b l))), Eq.{u3} (C (EmptyCollection.emptyCollection.{max u1 u2} (AList.{u1, u2} α β) (AList.hasEmptyc.{u1, u2} α β))) (AList.insertRec.{u1, u2, u3} α β (fun (a : α) (b : α) => _inst_1 a b) C H0 IH (EmptyCollection.emptyCollection.{max u1 u2} (AList.{u1, u2} α β) (AList.hasEmptyc.{u1, u2} α β))) H0
+but is expected to have type
+  forall {α : Type.{u2}} {β : α -> Type.{u3}} [_inst_1 : DecidableEq.{succ u2} α] {C : (AList.{u2, u3} α β) -> Sort.{u1}} (H0 : C (EmptyCollection.emptyCollection.{max u2 u3} (AList.{u2, u3} α β) (AList.instEmptyCollectionAList.{u2, u3} α β))) (IH : forall (a : α) (b : β a) (l : AList.{u2, u3} α β), (Not (Membership.mem.{u2, max u2 u3} α (AList.{u2, u3} α β) (AList.instMembershipAList.{u2, u3} α β) a l)) -> (C l) -> (C (AList.insert.{u2, u3} α β (fun (a : α) (b : α) => _inst_1 a b) a b l))), Eq.{u1} (C (EmptyCollection.emptyCollection.{max u2 u3} (AList.{u2, u3} α β) (AList.instEmptyCollectionAList.{u2, u3} α β))) (AList.insertRec.{u2, u3, u1} α β (fun (a : α) (b : α) => _inst_1 a b) C H0 IH (EmptyCollection.emptyCollection.{max u2 u3} (AList.{u2, u3} α β) (AList.instEmptyCollectionAList.{u2, u3} α β))) H0
+Case conversion may be inaccurate. Consider using '#align alist.insert_rec_empty AList.insertRec_emptyₓ'. -/
 @[simp]
 theorem insertRec_empty {C : AList β → Sort _} (H0 : C ∅)
     (IH : ∀ (a : α) (b : β a) (l : AList β) (h : a ∉ l), C l → C (l.insert a b)) :
@@ -484,6 +490,12 @@ theorem insertRec_empty {C : AList β → Sort _} (H0 : C ∅)
   rw [insert_rec]
 #align alist.insert_rec_empty AList.insertRec_empty
 
+/- warning: alist.insert_rec_insert -> AList.insertRec_insert is a dubious translation:
+lean 3 declaration is
+  forall {α : Type.{u1}} {β : α -> Type.{u2}} [_inst_1 : DecidableEq.{succ u1} α] {C : (AList.{u1, u2} α β) -> Sort.{u3}} (H0 : C (EmptyCollection.emptyCollection.{max u1 u2} (AList.{u1, u2} α β) (AList.hasEmptyc.{u1, u2} α β))) (IH : forall (a : α) (b : β a) (l : AList.{u1, u2} α β), (Not (Membership.Mem.{u1, max u1 u2} α (AList.{u1, u2} α β) (AList.hasMem.{u1, u2} α β) a l)) -> (C l) -> (C (AList.insert.{u1, u2} α β (fun (a : α) (b : α) => _inst_1 a b) a b l))) {c : Sigma.{u1, u2} α β} {l : AList.{u1, u2} α β} (h : Not (Membership.Mem.{u1, max u1 u2} α (AList.{u1, u2} α β) (AList.hasMem.{u1, u2} α β) (Sigma.fst.{u1, u2} α β c) l)), Eq.{u3} (C (AList.insert.{u1, u2} α β (fun (a : α) (b : α) => _inst_1 a b) (Sigma.fst.{u1, u2} α β c) (Sigma.snd.{u1, u2} α β c) l)) (AList.insertRec.{u1, u2, u3} α β (fun (a : α) (b : α) => _inst_1 a b) C H0 IH (AList.insert.{u1, u2} α β (fun (a : α) (b : α) => _inst_1 a b) (Sigma.fst.{u1, u2} α β c) (Sigma.snd.{u1, u2} α β c) l)) (IH (Sigma.fst.{u1, u2} α β c) (Sigma.snd.{u1, u2} α β c) l h (AList.insertRec.{u1, u2, u3} α β (fun (a : α) (b : α) => _inst_1 a b) C H0 IH l))
+but is expected to have type
+  forall {α : Type.{u2}} {β : α -> Type.{u3}} [_inst_1 : DecidableEq.{succ u2} α] {C : (AList.{u2, u3} α β) -> Sort.{u1}} (H0 : C (EmptyCollection.emptyCollection.{max u2 u3} (AList.{u2, u3} α β) (AList.instEmptyCollectionAList.{u2, u3} α β))) (IH : forall (a : α) (b : β a) (l : AList.{u2, u3} α β), (Not (Membership.mem.{u2, max u2 u3} α (AList.{u2, u3} α β) (AList.instMembershipAList.{u2, u3} α β) a l)) -> (C l) -> (C (AList.insert.{u2, u3} α β (fun (a : α) (b : α) => _inst_1 a b) a b l))) {c : Sigma.{u2, u3} α β} {l : AList.{u2, u3} α β} (h : Not (Membership.mem.{u2, max u2 u3} α (AList.{u2, u3} α β) (AList.instMembershipAList.{u2, u3} α β) (Sigma.fst.{u2, u3} α β c) l)), Eq.{u1} (C (AList.insert.{u2, u3} α β (fun (a : α) (b : α) => _inst_1 a b) (Sigma.fst.{u2, u3} α β c) (Sigma.snd.{u2, u3} α β c) l)) (AList.insertRec.{u2, u3, u1} α β (fun (a : α) (b : α) => _inst_1 a b) C H0 IH (AList.insert.{u2, u3} α β (fun (a : α) (b : α) => _inst_1 a b) (Sigma.fst.{u2, u3} α β c) (Sigma.snd.{u2, u3} α β c) l)) (IH (Sigma.fst.{u2, u3} α β c) (Sigma.snd.{u2, u3} α β c) l h (AList.insertRec.{u2, u3, u1} α β (fun (a : α) (b : α) => _inst_1 a b) C H0 IH l))
+Case conversion may be inaccurate. Consider using '#align alist.insert_rec_insert AList.insertRec_insertₓ'. -/
 theorem insertRec_insert {C : AList β → Sort _} (H0 : C ∅)
     (IH : ∀ (a : α) (b : β a) (l : AList β) (h : a ∉ l), C l → C (l.insert a b)) {c : Sigma β}
     {l : AList β} (h : c.1 ∉ l) :
@@ -501,12 +513,18 @@ theorem insertRec_insert {C : AList β → Sort _} (H0 : C ∅)
   apply cast_hEq
 #align alist.insert_rec_insert AList.insertRec_insert
 
-theorem recursion_insert_mk {C : AList β → Sort _} (H0 : C ∅)
+/- warning: alist.recursion_insert_mk -> AList.insertRec_insert_mk is a dubious translation:
+lean 3 declaration is
+  forall {α : Type.{u1}} {β : α -> Type.{u2}} [_inst_1 : DecidableEq.{succ u1} α] {C : (AList.{u1, u2} α β) -> Sort.{u3}} (H0 : C (EmptyCollection.emptyCollection.{max u1 u2} (AList.{u1, u2} α β) (AList.hasEmptyc.{u1, u2} α β))) (IH : forall (a : α) (b : β a) (l : AList.{u1, u2} α β), (Not (Membership.Mem.{u1, max u1 u2} α (AList.{u1, u2} α β) (AList.hasMem.{u1, u2} α β) a l)) -> (C l) -> (C (AList.insert.{u1, u2} α β (fun (a : α) (b : α) => _inst_1 a b) a b l))) {a : α} (b : β a) {l : AList.{u1, u2} α β} (h : Not (Membership.Mem.{u1, max u1 u2} α (AList.{u1, u2} α β) (AList.hasMem.{u1, u2} α β) a l)), Eq.{u3} (C (AList.insert.{u1, u2} α β (fun (a : α) (b : α) => _inst_1 a b) a b l)) (AList.insertRec.{u1, u2, u3} α β (fun (a : α) (b : α) => _inst_1 a b) C H0 IH (AList.insert.{u1, u2} α β (fun (a : α) (b : α) => _inst_1 a b) a b l)) (IH a b l h (AList.insertRec.{u1, u2, u3} α β (fun (a : α) (b : α) => _inst_1 a b) C H0 IH l))
+but is expected to have type
+  forall {α : Type.{u2}} {β : α -> Type.{u3}} [_inst_1 : DecidableEq.{succ u2} α] {C : (AList.{u2, u3} α β) -> Sort.{u1}} (H0 : C (EmptyCollection.emptyCollection.{max u2 u3} (AList.{u2, u3} α β) (AList.instEmptyCollectionAList.{u2, u3} α β))) (IH : forall (a : α) (b : β a) (l : AList.{u2, u3} α β), (Not (Membership.mem.{u2, max u2 u3} α (AList.{u2, u3} α β) (AList.instMembershipAList.{u2, u3} α β) a l)) -> (C l) -> (C (AList.insert.{u2, u3} α β (fun (a : α) (b : α) => _inst_1 a b) a b l))) {a : α} (b : β a) {l : AList.{u2, u3} α β} (h : Not (Membership.mem.{u2, max u2 u3} α (AList.{u2, u3} α β) (AList.instMembershipAList.{u2, u3} α β) a l)), Eq.{u1} (C (AList.insert.{u2, u3} α β (fun (a : α) (b : α) => _inst_1 a b) a b l)) (AList.insertRec.{u2, u3, u1} α β (fun (a : α) (b : α) => _inst_1 a b) C H0 IH (AList.insert.{u2, u3} α β (fun (a : α) (b : α) => _inst_1 a b) a b l)) (IH a b l h (AList.insertRec.{u2, u3, u1} α β (fun (a : α) (b : α) => _inst_1 a b) C H0 IH l))
+Case conversion may be inaccurate. Consider using '#align alist.recursion_insert_mk AList.insertRec_insert_mkₓ'. -/
+theorem insertRec_insert_mk {C : AList β → Sort _} (H0 : C ∅)
     (IH : ∀ (a : α) (b : β a) (l : AList β) (h : a ∉ l), C l → C (l.insert a b)) {a : α} (b : β a)
     {l : AList β} (h : a ∉ l) :
     @insertRec α β _ C H0 IH (l.insert a b) = IH a b l h (@insertRec α β _ C H0 IH l) :=
   @insertRec_insert α β _ C H0 IH ⟨a, b⟩ l h
-#align alist.recursion_insert_mk AList.recursion_insert_mk
+#align alist.recursion_insert_mk AList.insertRec_insert_mk
 
 /-! ### extract -/

f808feb6

bump to nightly-2023-02-21-16

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

1107b979

Changes in mathlib4

mathlib3

mathlib4

f808feb6

chore: classify new theorem / theorem porting notes (#11432)

Classifies by adding issue number #10756 to porting notes claiming anything equivalent to:

"added theorem"
"added theorems"
"new theorem"
"new theorems"
"added lemma"
"new lemma"
"new lemmas"

55fe4027

Diff

@@ -480,7 +480,7 @@ theorem mem_lookup_union {a} {b : β a} {s₁ s₂ : AList β} :
   mem_dlookup_kunion
 #align alist.mem_lookup_union AList.mem_lookup_union
 
--- Porting note: new theorem, version of `mem_lookup_union` with LHS in simp-normal form
+-- Porting note (#10756): new theorem, version of `mem_lookup_union` with LHS in simp-normal form
 @[simp]
 theorem lookup_union_eq_some {a} {b : β a} {s₁ s₂ : AList β} :
     lookup a (s₁ ∪ s₂) = some b ↔ lookup a s₁ = some b ∨ a ∉ s₁ ∧ lookup a s₂ = some b :=

f808feb6

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

@@ -317,6 +317,12 @@ theorem lookup_insert_ne {a a'} {b' : β a'} {s : AList β} (h : a ≠ a') :
   dlookup_kinsert_ne h
 #align alist.lookup_insert_ne AList.lookup_insert_ne
 
+@[simp] theorem lookup_insert_eq_none {l : AList β} {k k' : α} {v : β k} :
+    (l.insert k v).lookup k' = none ↔ (k' ≠ k) ∧ l.lookup k' = none := by
+  by_cases h : k' = k
+  · subst h; simp
+  · simp_all [lookup_insert_ne h]
+
 @[simp]
 theorem lookup_to_alist {a} (s : List (Sigma β)) : lookup a s.toAList = s.dlookup a := by
   rw [List.toAList, lookup, dlookup_dedupKeys]

f808feb6

style: homogenise porting notes (#11145)

Homogenises porting notes via capitalisation and addition of whitespace.

It makes the following changes:

converts "--porting note" into "-- Porting note";
converts "porting note" into "Porting note".

8be0b69c

Diff

@@ -468,13 +468,13 @@ theorem lookup_union_right {a} {s₁ s₂ : AList β} : a ∉ s₁ → lookup a
   dlookup_kunion_right
 #align alist.lookup_union_right AList.lookup_union_right
 
---Porting note: removing simp, LHS not in SNF, new theorem added instead.
+-- Porting note: removing simp, LHS not in SNF, new theorem added instead.
 theorem mem_lookup_union {a} {b : β a} {s₁ s₂ : AList β} :
     b ∈ lookup a (s₁ ∪ s₂) ↔ b ∈ lookup a s₁ ∨ a ∉ s₁ ∧ b ∈ lookup a s₂ :=
   mem_dlookup_kunion
 #align alist.mem_lookup_union AList.mem_lookup_union
 
---Porting note: new theorem, version of `mem_lookup_union` with LHS in simp-normal form
+-- Porting note: new theorem, version of `mem_lookup_union` with LHS in simp-normal form
 @[simp]
 theorem lookup_union_eq_some {a} {b : β a} {s₁ s₂ : AList β} :
     lookup a (s₁ ∪ s₂) = some b ↔ lookup a s₁ = some b ∨ a ∉ s₁ ∧ lookup a s₂ = some b :=

f808feb6

chore: banish Type _ and Sort _ (#6499)

We remove all possible occurences of Type _ and Sort _ in favor of Type* and Sort*.

This has nice performance benefits.

32de3f67

Diff

@@ -358,7 +358,7 @@ theorem mk_cons_eq_insert (c : Sigma β) (l : List (Sigma β)) (h : (c :: l).Nod
 
 /-- Recursion on an `AList`, using `insert`. Use as `induction l using AList.insertRec`. -/
 @[elab_as_elim]
-def insertRec {C : AList β → Sort _} (H0 : C ∅)
+def insertRec {C : AList β → Sort*} (H0 : C ∅)
     (IH : ∀ (a : α) (b : β a) (l : AList β), a ∉ l → C l → C (l.insert a b)) :
     ∀ l : AList β, C l
   | ⟨[], _⟩ => H0
@@ -372,14 +372,14 @@ def insertRec {C : AList β → Sort _} (H0 : C ∅)
 example (l : AList β) : True := by induction l using AList.insertRec <;> trivial
 
 @[simp]
-theorem insertRec_empty {C : AList β → Sort _} (H0 : C ∅)
+theorem insertRec_empty {C : AList β → Sort*} (H0 : C ∅)
     (IH : ∀ (a : α) (b : β a) (l : AList β), a ∉ l → C l → C (l.insert a b)) :
     @insertRec α β _ C H0 IH ∅ = H0 := by
   change @insertRec α β _ C H0 IH ⟨[], _⟩ = H0
   rw [insertRec]
 #align alist.insert_rec_empty AList.insertRec_empty
 
-theorem insertRec_insert {C : AList β → Sort _} (H0 : C ∅)
+theorem insertRec_insert {C : AList β → Sort*} (H0 : C ∅)
     (IH : ∀ (a : α) (b : β a) (l : AList β), a ∉ l → C l → C (l.insert a b)) {c : Sigma β}
     {l : AList β} (h : c.1 ∉ l) :
     @insertRec α β _ C H0 IH (l.insert c.1 c.2) = IH c.1 c.2 l h (@insertRec α β _ C H0 IH l) := by
@@ -393,7 +393,7 @@ theorem insertRec_insert {C : AList β → Sort _} (H0 : C ∅)
   apply cast_heq
 #align alist.insert_rec_insert AList.insertRec_insert
 
-theorem insertRec_insert_mk {C : AList β → Sort _} (H0 : C ∅)
+theorem insertRec_insert_mk {C : AList β → Sort*} (H0 : C ∅)
     (IH : ∀ (a : α) (b : β a) (l : AList β), a ∉ l → C l → C (l.insert a b)) {a : α} (b : β a)
     {l : AList β} (h : a ∉ l) :
     @insertRec α β _ C H0 IH (l.insert a b) = IH a b l h (@insertRec α β _ C H0 IH l) :=

f808feb6

feat: AList.keys_subset_keys_of_entries_subset_entries (#6150)

fa24f8ff

Diff

@@ -180,6 +180,15 @@ theorem perm_lookup {a : α} {s₁ s₂ : AList β} (p : s₁.entries ~ s₂.ent
 instance (a : α) (s : AList β) : Decidable (a ∈ s) :=
   decidable_of_iff _ lookup_isSome
 
+theorem keys_subset_keys_of_entries_subset_entries
+    {s₁ s₂ : AList β} (h : s₁.entries ⊆ s₂.entries) : s₁.keys ⊆ s₂.keys := by
+  intro k hk
+  letI : DecidableEq α := Classical.decEq α
+  have := h (mem_lookup_iff.1 (Option.get_mem (lookup_isSome.2 hk)))
+  rw [← mem_lookup_iff, Option.mem_def] at this
+  rw [← mem_keys, ← lookup_isSome, this]
+  exact Option.isSome_some
+
 /-! ### replace -/

f808feb6

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,14 +2,11 @@
 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.list.alist
-! leanprover-community/mathlib commit f808feb6c18afddb25e66a71d317643cf7fb5fbb
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Data.List.Sigma
 
+#align_import data.list.alist from "leanprover-community/mathlib"@"f808feb6c18afddb25e66a71d317643cf7fb5fbb"
+
 /-!
 # Association Lists

f808feb6

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

@@ -319,7 +319,7 @@ theorem lookup_to_alist {a} (s : List (Sigma β)) : lookup a s.toAList = s.dlook
 @[simp]
 theorem insert_insert {a} {b b' : β a} (s : AList β) :
     (s.insert a b).insert a b' = s.insert a b' := by
-  ext : 1 ; simp only [AList.insert_entries, List.kerase_cons_eq]
+  ext : 1; simp only [AList.insert_entries, List.kerase_cons_eq]
 #align alist.insert_insert AList.insert_insert
 
 theorem insert_insert_of_ne {a a'} {b : β a} {b' : β a'} (s : AList β) (h : a ≠ a') :
@@ -504,7 +504,7 @@ theorem union_comm_of_disjoint {s₁ s₂ : AList β} (h : Disjoint s₁ s₂) :
     (s₁ ∪ s₂).entries ~ (s₂ ∪ s₁).entries :=
   lookup_ext (AList.nodupKeys _) (AList.nodupKeys _)
     (by
-      intros ; simp
+      intros; simp
       constructor <;> intro h'
       · cases' h' with h' h'
         · right

f808feb6

chore: fix focusing dots (#5708)

This PR is the result of running

find . -type f -name "*.lean" -exec sed -i -E 's/^( +)\. /\1· /' {} \;
find . -type f -name "*.lean" -exec sed -i -E 'N;s/^( +·)\n +(.*)$/\1 \2/;P;D' {} \;

which firstly replaces . focusing dots with · and secondly removes isolated instances of such dots, unifying them with the following line. A new rule is placed in the style linter to verify this.

cb02d09e

Diff

@@ -506,7 +506,7 @@ theorem union_comm_of_disjoint {s₁ s₂ : AList β} (h : Disjoint s₁ s₂) :
     (by
       intros ; simp
       constructor <;> intro h'
-      . cases' h' with h' h'
+      · cases' h' with h' h'
         · right
           refine' ⟨_, h'⟩
           apply h
@@ -514,7 +514,7 @@ theorem union_comm_of_disjoint {s₁ s₂ : AList β} (h : Disjoint s₁ s₂) :
           exact rfl
         · left
           rw [h'.2]
-      . cases' h' with h' h'
+      · cases' h' with h' h'
         · right
           refine' ⟨_, h'⟩
           intro h''

f808feb6

chore: fix upper/lowercase in comments (#4360)

Run a non-interactive version of fix-comments.py on all files.
Go through the diff and manually add/discard/edit chunks.

27d257fc

Diff

@@ -54,7 +54,7 @@ structure AList (β : α → Type v) : Type max u v where
   nodupKeys : entries.NodupKeys
 #align alist AList
 
-/-- Given `l : List (sigma β)`, create a term of type `alist β` by removing
+/-- Given `l : List (Sigma β)`, create a term of type `AList β` by removing
 entries with duplicate keys. -/
 def List.toAList [DecidableEq α] {β : α → Type v} (l : List (Sigma β)) : AList β where
   entries := _
@@ -350,7 +350,7 @@ theorem mk_cons_eq_insert (c : Sigma β) (l : List (Sigma β)) (h : (c :: l).Nod
   simpa [insert] using (kerase_of_not_mem_keys <| not_mem_keys_of_nodupKeys_cons h).symm
 #align alist.mk_cons_eq_insert AList.mk_cons_eq_insert
 
-/-- Recursion on an `alist`, using `insert`. Use as `induction l using alist.insert_rec`. -/
+/-- Recursion on an `AList`, using `insert`. Use as `induction l using AList.insertRec`. -/
 @[elab_as_elim]
 def insertRec {C : AList β → Sort _} (H0 : C ∅)
     (IH : ∀ (a : α) (b : β a) (l : AList β), a ∉ l → C l → C (l.insert a b)) :

f808feb6

chore: update std 05-22 (#4248)

The main breaking change is that tac <;> [t1, t2] is now written tac <;> [t1; t2], to avoid clashing with tactics like cases and use that take comma-separated lists.

ac36b28e

Diff

@@ -325,7 +325,7 @@ theorem insert_insert {a} {b b' : β a} (s : AList β) :
 theorem insert_insert_of_ne {a a'} {b : β a} {b' : β a'} (s : AList β) (h : a ≠ a') :
     ((s.insert a b).insert a' b').entries ~ ((s.insert a' b').insert a b).entries := by
   simp only [insert_entries]; rw [kerase_cons_ne, kerase_cons_ne, kerase_comm] <;>
-    [apply Perm.swap, exact h, exact h.symm]
+    [apply Perm.swap; exact h; exact h.symm]
 #align alist.insert_insert_of_ne AList.insert_insert_of_ne
 
 @[simp]

f808feb6

chore: bye-bye, solo bys! (#3825)

This PR puts, with one exception, every single remaining by that lies all by itself on its own line to the previous line, thus matching the current behaviour of start-port.sh. The exception is when the by begins the second or later argument to a tuple or anonymous constructor; see https://github.com/leanprover-community/mathlib4/pull/3825#discussion_r1186702599.

Essentially this is s/\n *by$/ by/g, but with manual editing to satisfy the linter's max-100-char-line requirement. The Python style linter is also modified to catch these "isolated bys".

14167e48

Diff

@@ -317,8 +317,8 @@ theorem lookup_to_alist {a} (s : List (Sigma β)) : lookup a s.toAList = s.dlook
 #align alist.lookup_to_alist AList.lookup_to_alist
 
 @[simp]
-theorem insert_insert {a} {b b' : β a} (s : AList β) : (s.insert a b).insert a b' = s.insert a b' :=
-  by
+theorem insert_insert {a} {b b' : β a} (s : AList β) :
+    (s.insert a b).insert a b' = s.insert a b' := by
   ext : 1 ; simp only [AList.insert_entries, List.kerase_cons_eq]
 #align alist.insert_insert AList.insert_insert
 
@@ -378,10 +378,8 @@ theorem insertRec_insert {C : AList β → Sort _} (H0 : C ∅)
     {l : AList β} (h : c.1 ∉ l) :
     @insertRec α β _ C H0 IH (l.insert c.1 c.2) = IH c.1 c.2 l h (@insertRec α β _ C H0 IH l) := by
   cases' l with l hl
-  suffices
-    HEq (@insertRec α β _ C H0 IH ⟨c :: l, nodupKeys_cons.2 ⟨h, hl⟩⟩)
-      (IH c.1 c.2 ⟨l, hl⟩ h (@insertRec α β _ C H0 IH ⟨l, hl⟩))
-    by
+  suffices HEq (@insertRec α β _ C H0 IH ⟨c :: l, nodupKeys_cons.2 ⟨h, hl⟩⟩)
+      (IH c.1 c.2 ⟨l, hl⟩ h (@insertRec α β _ C H0 IH ⟨l, hl⟩)) by
     cases c
     apply eq_of_heq
     convert this <;> rw [insert_of_neg h]

f808feb6

feat(data/list/alist): recursion on alist using insert (#1724)

Mathlib4 pair for https://github.com/leanprover-community/mathlib/pull/15434

Co-authored-by: Parcly Taxel <reddeloostw@gmail.com> Co-authored-by: Eric Wieser <wieser.eric@gmail.com>

daef2b6c

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.list.alist
-! leanprover-community/mathlib commit 9003f28797c0664a49e4179487267c494477d853
+! leanprover-community/mathlib commit f808feb6c18afddb25e66a71d317643cf7fb5fbb
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -274,6 +274,12 @@ theorem insert_entries_of_neg {a} {b : β a} {s : AList β} (h : a ∉ s) :
     (insert a b s).entries = ⟨a, b⟩ :: s.entries := by rw [insert_entries, kerase_of_not_mem_keys h]
 #align alist.insert_entries_of_neg AList.insert_entries_of_neg
 
+-- Todo: rename to `insert_of_not_mem`.
+theorem insert_of_neg {a} {b : β a} {s : AList β} (h : a ∉ s) :
+    insert a b s = ⟨⟨a, b⟩ :: s.entries, nodupKeys_cons.2 ⟨h, s.2⟩⟩ :=
+  ext <| insert_entries_of_neg h
+#align alist.insert_of_neg AList.insert_of_neg
+
 @[simp]
 theorem insert_empty (a) (b : β a) : insert a b ∅ = singleton a b :=
   rfl
@@ -339,6 +345,57 @@ theorem toAList_cons (a : α) (b : β a) (xs : List (Sigma β)) :
   rfl
 #align alist.to_alist_cons AList.toAList_cons
 
+theorem mk_cons_eq_insert (c : Sigma β) (l : List (Sigma β)) (h : (c :: l).NodupKeys) :
+    (⟨c :: l, h⟩ : AList β) = insert c.1 c.2 ⟨l, nodupKeys_of_nodupKeys_cons h⟩ := by
+  simpa [insert] using (kerase_of_not_mem_keys <| not_mem_keys_of_nodupKeys_cons h).symm
+#align alist.mk_cons_eq_insert AList.mk_cons_eq_insert
+
+/-- Recursion on an `alist`, using `insert`. Use as `induction l using alist.insert_rec`. -/
+@[elab_as_elim]
+def insertRec {C : AList β → Sort _} (H0 : C ∅)
+    (IH : ∀ (a : α) (b : β a) (l : AList β), a ∉ l → C l → C (l.insert a b)) :
+    ∀ l : AList β, C l
+  | ⟨[], _⟩ => H0
+  | ⟨c :: l, h⟩ => by
+    rw [mk_cons_eq_insert]
+    refine' IH _ _ _ _ (insertRec H0 IH _)
+    exact not_mem_keys_of_nodupKeys_cons h
+#align alist.insert_rec AList.insertRec
+
+-- Test that the `induction` tactic works on `insert_rec`.
+example (l : AList β) : True := by induction l using AList.insertRec <;> trivial
+
+@[simp]
+theorem insertRec_empty {C : AList β → Sort _} (H0 : C ∅)
+    (IH : ∀ (a : α) (b : β a) (l : AList β), a ∉ l → C l → C (l.insert a b)) :
+    @insertRec α β _ C H0 IH ∅ = H0 := by
+  change @insertRec α β _ C H0 IH ⟨[], _⟩ = H0
+  rw [insertRec]
+#align alist.insert_rec_empty AList.insertRec_empty
+
+theorem insertRec_insert {C : AList β → Sort _} (H0 : C ∅)
+    (IH : ∀ (a : α) (b : β a) (l : AList β), a ∉ l → C l → C (l.insert a b)) {c : Sigma β}
+    {l : AList β} (h : c.1 ∉ l) :
+    @insertRec α β _ C H0 IH (l.insert c.1 c.2) = IH c.1 c.2 l h (@insertRec α β _ C H0 IH l) := by
+  cases' l with l hl
+  suffices
+    HEq (@insertRec α β _ C H0 IH ⟨c :: l, nodupKeys_cons.2 ⟨h, hl⟩⟩)
+      (IH c.1 c.2 ⟨l, hl⟩ h (@insertRec α β _ C H0 IH ⟨l, hl⟩))
+    by
+    cases c
+    apply eq_of_heq
+    convert this <;> rw [insert_of_neg h]
+  rw [insertRec]
+  apply cast_heq
+#align alist.insert_rec_insert AList.insertRec_insert
+
+theorem insertRec_insert_mk {C : AList β → Sort _} (H0 : C ∅)
+    (IH : ∀ (a : α) (b : β a) (l : AList β), a ∉ l → C l → C (l.insert a b)) {a : α} (b : β a)
+    {l : AList β} (h : a ∉ l) :
+    @insertRec α β _ C H0 IH (l.insert a b) = IH a b l h (@insertRec α β _ C H0 IH l) :=
+  @insertRec_insert α β _ C H0 IH ⟨a, b⟩ l h
+#align alist.recursion_insert_mk AList.insertRec_insert_mk
+
 /-! ### extract -/

9003f287

chore: fix casing errors per naming scheme (#1670)

526ab32a

Diff

@@ -26,7 +26,7 @@ Association lists are represented by the `AList` structure. This file defines th
 provides ways to access, modify, and combine `AList`s.
 
 * `AList.keys` returns a list of keys of the alist.
-* `AList.has_mem` returns membership in the set of keys.
+* `AList.membership` returns membership in the set of keys.
 * `AList.erase` removes a certain key.
 * `AList.insert` adds a key-value mapping to the list.
 * `AList.union` combines two association lists.

9003f287

chore: tidy various files (#1595)

6fe10b88

Diff

@@ -162,9 +162,9 @@ theorem lookup_empty (a) : lookup a (∅ : AList β) = none :=
   rfl
 #align alist.lookup_empty AList.lookup_empty
 
-theorem lookup_is_some {a : α} {s : AList β} : (s.lookup a).isSome ↔ a ∈ s :=
-  dlookup_is_some
-#align alist.lookup_is_some AList.lookup_is_some
+theorem lookup_isSome {a : α} {s : AList β} : (s.lookup a).isSome ↔ a ∈ s :=
+  dlookup_isSome
+#align alist.lookup_is_some AList.lookup_isSome
 
 theorem lookup_eq_none {a : α} {s : AList β} : lookup a s = none ↔ a ∉ s :=
   dlookup_eq_none
@@ -181,7 +181,7 @@ theorem perm_lookup {a : α} {s₁ s₂ : AList β} (p : s₁.entries ~ s₂.ent
 #align alist.perm_lookup AList.perm_lookup
 
 instance (a : α) (s : AList β) : Decidable (a ∈ s) :=
-  decidable_of_iff _ lookup_is_some
+  decidable_of_iff _ lookup_isSome
 
 /-! ### replace -/
 
@@ -330,14 +330,14 @@ theorem insert_singleton_eq {a : α} {b b' : β a} : insert a b (singleton a b')
 #align alist.insert_singleton_eq AList.insert_singleton_eq
 
 @[simp]
-theorem entries_to_alist (xs : List (Sigma β)) : (List.toAList xs).entries = dedupKeys xs :=
+theorem entries_toAList (xs : List (Sigma β)) : (List.toAList xs).entries = dedupKeys xs :=
   rfl
-#align alist.entries_to_alist AList.entries_to_alist
+#align alist.entries_to_alist AList.entries_toAList
 
-theorem to_alist_cons (a : α) (b : β a) (xs : List (Sigma β)) :
+theorem toAList_cons (a : α) (b : β a) (xs : List (Sigma β)) :
     List.toAList (⟨a, b⟩ :: xs) = insert a b xs.toAList :=
   rfl
-#align alist.to_alist_cons AList.to_alist_cons
+#align alist.to_alist_cons AList.toAList_cons
 
 /-! ### extract -/
 
@@ -455,7 +455,7 @@ theorem union_comm_of_disjoint {s₁ s₂ : AList β} (h : Disjoint s₁ s₂) :
         · right
           refine' ⟨_, h'⟩
           apply h
-          rw [keys, ← List.dlookup_is_some, h']
+          rw [keys, ← List.dlookup_isSome, h']
           exact rfl
         · left
           rw [h'.2]
@@ -464,7 +464,7 @@ theorem union_comm_of_disjoint {s₁ s₂ : AList β} (h : Disjoint s₁ s₂) :
           refine' ⟨_, h'⟩
           intro h''
           apply h _ h''
-          rw [keys, ← List.dlookup_is_some, h']
+          rw [keys, ← List.dlookup_isSome, h']
           exact rfl
         · left
           rw [h'.2])

9003f287

style: Nodupkeys -> no/NodupKeys dedupkeys -> dedupKeys (#1592)

As per the comments here.

5f2a4636

Diff

@@ -51,15 +51,14 @@ structure AList (β : α → Type v) : Type max u v where
   /-- The underlying `List` of an `AList` -/
   entries : List (Sigma β)
   /-- There are no duplicate keys in `entries` -/
-  Nodupkeys : entries.Nodupkeys
+  nodupKeys : entries.NodupKeys
 #align alist AList
 
 /-- Given `l : List (sigma β)`, create a term of type `alist β` by removing
 entries with duplicate keys. -/
-def List.toAList [DecidableEq α] {β : α → Type v} (l : List (Sigma β)) : AList β
-    where
+def List.toAList [DecidableEq α] {β : α → Type v} (l : List (Sigma β)) : AList β where
   entries := _
-  Nodupkeys := nodupkeys_dedupkeys l
+  nodupKeys := nodupKeys_dedupKeys l
 #align list.to_alist List.toAList
 
 namespace AList
@@ -85,7 +84,7 @@ def keys (s : AList β) : List α :=
 #align alist.keys AList.keys
 
 theorem keys_nodup (s : AList β) : s.keys.Nodup :=
-  s.Nodupkeys
+  s.nodupKeys
 #align alist.keys_nodup AList.keys_nodup
 
 /-! ### mem -/
@@ -108,7 +107,7 @@ theorem mem_of_perm {a : α} {s₁ s₂ : AList β} (p : s₁.entries ~ s₂.ent
 
 /-- The empty association list. -/
 instance : EmptyCollection (AList β) :=
-  ⟨⟨[], nodupkeys_nil⟩⟩
+  ⟨⟨[], nodupKeys_nil⟩⟩
 
 instance : Inhabited (AList β) :=
   ⟨∅⟩
@@ -133,7 +132,7 @@ theorem keys_empty : (∅ : AList β).keys = [] :=
 
 /-- The singleton association list. -/
 def singleton (a : α) (b : β a) : AList β :=
-  ⟨[⟨a, b⟩], nodupkeys_singleton _⟩
+  ⟨[⟨a, b⟩], nodupKeys_singleton _⟩
 #align alist.singleton AList.singleton
 
 @[simp]
@@ -173,12 +172,12 @@ theorem lookup_eq_none {a : α} {s : AList β} : lookup a s = none ↔ a ∉ s :
 
 theorem mem_lookup_iff {a : α} {b : β a} {s : AList β} :
     b ∈ lookup a s ↔ Sigma.mk a b ∈ s.entries :=
-  mem_dlookup_iff s.Nodupkeys
+  mem_dlookup_iff s.nodupKeys
 #align alist.mem_lookup_iff AList.mem_lookup_iff
 
 theorem perm_lookup {a : α} {s₁ s₂ : AList β} (p : s₁.entries ~ s₂.entries) :
     s₁.lookup a = s₂.lookup a :=
-  perm_dlookup _ s₁.Nodupkeys s₂.Nodupkeys p
+  perm_dlookup _ s₁.nodupKeys s₂.nodupKeys p
 #align alist.perm_lookup AList.perm_lookup
 
 instance (a : α) (s : AList β) : Decidable (a ∈ s) :=
@@ -190,7 +189,7 @@ instance (a : α) (s : AList β) : Decidable (a ∈ s) :=
 /-- Replace a key with a given value in an association list.
   If the key is not present it does nothing. -/
 def replace (a : α) (b : β a) (s : AList β) : AList β :=
-  ⟨kreplace a b s.entries, (kreplace_nodupkeys a b).2 s.Nodupkeys⟩
+  ⟨kreplace a b s.entries, (kreplace_nodupKeys a b).2 s.nodupKeys⟩
 #align alist.replace AList.replace
 
 @[simp]
@@ -205,7 +204,7 @@ theorem mem_replace {a a' : α} {b : β a} {s : AList β} : a' ∈ replace a b s
 
 theorem perm_replace {a : α} {b : β a} {s₁ s₂ : AList β} :
     s₁.entries ~ s₂.entries → (replace a b s₁).entries ~ (replace a b s₂).entries :=
-  Perm.kreplace s₁.Nodupkeys
+  Perm.kreplace s₁.nodupKeys
 #align alist.perm_replace AList.perm_replace
 
 end
@@ -224,7 +223,7 @@ variable [DecidableEq α]
 
 /-- Erase a key from the map. If the key is not present, do nothing. -/
 def erase (a : α) (s : AList β) : AList β :=
-  ⟨s.entries.kerase a, s.Nodupkeys.kerase a⟩
+  ⟨s.entries.kerase a, s.nodupKeys.kerase a⟩
 #align alist.erase AList.erase
 
 @[simp]
@@ -239,12 +238,12 @@ theorem mem_erase {a a' : α} {s : AList β} : a' ∈ erase a s ↔ a' ≠ a ∧
 
 theorem perm_erase {a : α} {s₁ s₂ : AList β} :
     s₁.entries ~ s₂.entries → (erase a s₁).entries ~ (erase a s₂).entries :=
-  Perm.kerase s₁.Nodupkeys
+  Perm.kerase s₁.nodupKeys
 #align alist.perm_erase AList.perm_erase
 
 @[simp]
 theorem lookup_erase (a) (s : AList β) : lookup a (erase a s) = none :=
-  dlookup_kerase a s.Nodupkeys
+  dlookup_kerase a s.nodupKeys
 #align alist.lookup_erase AList.lookup_erase
 
 @[simp]
@@ -262,7 +261,7 @@ theorem erase_erase (a a' : α) (s : AList β) : (s.erase a).erase a' = (s.erase
 /-- Insert a key-value pair into an association list and erase any existing pair
   with the same key. -/
 def insert (a : α) (b : β a) (s : AList β) : AList β :=
-  ⟨kinsert a b s.entries, kinsert_nodupkeys a b s.Nodupkeys⟩
+  ⟨kinsert a b s.entries, kinsert_nodupKeys a b s.nodupKeys⟩
 #align alist.insert AList.insert
 
 @[simp]
@@ -292,7 +291,7 @@ theorem keys_insert {a} {b : β a} (s : AList β) : (insert a b s).keys = a :: s
 
 theorem perm_insert {a} {b : β a} {s₁ s₂ : AList β} (p : s₁.entries ~ s₂.entries) :
     (insert a b s₁).entries ~ (insert a b s₂).entries := by
-  simp only [insert_entries]; exact p.kinsert s₁.Nodupkeys
+  simp only [insert_entries]; exact p.kinsert s₁.nodupKeys
 #align alist.perm_insert AList.perm_insert
 
 @[simp]
@@ -308,7 +307,7 @@ theorem lookup_insert_ne {a a'} {b' : β a'} {s : AList β} (h : a ≠ a') :
 
 @[simp]
 theorem lookup_to_alist {a} (s : List (Sigma β)) : lookup a s.toAList = s.dlookup a := by
-  rw [List.toAList, lookup, dlookup_dedupkeys]
+  rw [List.toAList, lookup, dlookup_dedupKeys]
 #align alist.lookup_to_alist AList.lookup_to_alist
 
 @[simp]
@@ -331,7 +330,7 @@ theorem insert_singleton_eq {a : α} {b b' : β a} : insert a b (singleton a b')
 #align alist.insert_singleton_eq AList.insert_singleton_eq
 
 @[simp]
-theorem entries_to_alist (xs : List (Sigma β)) : (List.toAList xs).entries = dedupkeys xs :=
+theorem entries_to_alist (xs : List (Sigma β)) : (List.toAList xs).entries = dedupKeys xs :=
   rfl
 #align alist.entries_to_alist AList.entries_to_alist
 
@@ -345,8 +344,8 @@ theorem to_alist_cons (a : α) (b : β a) (xs : List (Sigma β)) :
 
 /-- Erase a key from the map, and return the corresponding value, if found. -/
 def extract (a : α) (s : AList β) : Option (β a) × AList β :=
-  have : (kextract a s.entries).2.Nodupkeys := by
-    rw [kextract_eq_dlookup_kerase]; exact s.Nodupkeys.kerase _
+  have : (kextract a s.entries).2.NodupKeys := by
+    rw [kextract_eq_dlookup_kerase]; exact s.nodupKeys.kerase _
   match kextract a s.entries, this with
   | (b, l), h => (b, ⟨l, h⟩)
 #align alist.extract AList.extract
@@ -363,7 +362,7 @@ theorem extract_eq_lookup_erase (a : α) (s : AList β) : extract a s = (lookup
 left-biased: if there exists an `a ∈ s₁`, `lookup a (s₁ ∪ s₂) = lookup a s₁`.
 -/
 def union (s₁ s₂ : AList β) : AList β :=
-  ⟨s₁.entries.kunion s₂.entries, s₁.Nodupkeys.kunion s₂.Nodupkeys⟩
+  ⟨s₁.entries.kunion s₂.entries, s₁.nodupKeys.kunion s₂.nodupKeys⟩
 #align alist.union AList.union
 
 instance : Union (AList β) :=
@@ -391,7 +390,7 @@ theorem mem_union {a} {s₁ s₂ : AList β} : a ∈ s₁ ∪ s₂ ↔ a ∈ s
 
 theorem perm_union {s₁ s₂ s₃ s₄ : AList β} (p₁₂ : s₁.entries ~ s₂.entries)
     (p₃₄ : s₃.entries ~ s₄.entries) : (s₁ ∪ s₃).entries ~ (s₂ ∪ s₄).entries := by
-  simp [p₁₂.kunion s₃.Nodupkeys p₃₄]
+  simp [p₁₂.kunion s₃.nodupKeys p₃₄]
 #align alist.perm_union AList.perm_union
 
 theorem union_erase (a : α) (s₁ s₂ : AList β) : erase a (s₁ ∪ s₂) = erase a s₁ ∪ erase a s₂ :=
@@ -430,7 +429,7 @@ theorem insert_union {a} {b : β a} {s₁ s₂ : AList β} : insert a b (s₁ 
 #align alist.insert_union AList.insert_union
 
 theorem union_assoc {s₁ s₂ s₃ : AList β} : (s₁ ∪ s₂ ∪ s₃).entries ~ (s₁ ∪ (s₂ ∪ s₃)).entries :=
-  lookup_ext (AList.Nodupkeys _) (AList.Nodupkeys _)
+  lookup_ext (AList.nodupKeys _) (AList.nodupKeys _)
     (by simp [not_or, or_assoc, and_or_left, and_assoc])
 #align alist.union_assoc AList.union_assoc
 
@@ -448,7 +447,7 @@ variable [DecidableEq α]
 
 theorem union_comm_of_disjoint {s₁ s₂ : AList β} (h : Disjoint s₁ s₂) :
     (s₁ ∪ s₂).entries ~ (s₂ ∪ s₁).entries :=
-  lookup_ext (AList.Nodupkeys _) (AList.Nodupkeys _)
+  lookup_ext (AList.nodupKeys _) (AList.nodupKeys _)
     (by
       intros ; simp
       constructor <;> intro h'

9003f287

feat: port Data.List.AList (#1530)

40d6bcd5

`data.list.alist` ⟷ `Mathlib.Data.List.AList`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 2 + 140

data.list.alist ⟷ Mathlib.Data.List.AList

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 2 + 140

`data.list.alist` ⟷ `Mathlib.Data.List.AList`