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

18a5306c

(last sync)

Changes in mathlib3port

mathlib3

mathlib3port

be24ec5d

bump to nightly-2024-04-08-08

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

e7589225

Diff

@@ -137,7 +137,6 @@ theorem drop_take_succ_eq_cons_nthLe (L : List α) {i : ℕ} (hi : i < L.length)
 #align list.drop_take_succ_eq_cons_nth_le List.drop_take_succ_eq_cons_nthLe
 -/
 
-#print List.drop_take_succ_join_eq_nthLe /-
 /-- In a join of sublists, taking the slice between the indices `A` and `B - 1` gives back the
 original sublist of index `i` if `A` is the sum of the lenghts of sublists of index `< i`, and
 `B` is the sum of the lengths of sublists of index `≤ i`. -/
@@ -149,16 +148,13 @@ theorem drop_take_succ_join_eq_nthLe (L : List (List α)) {i : ℕ} (hi : i < L.
     simp [map_take, take_take]
   simp [take_sum_join, this, drop_sum_join, drop_take_succ_eq_cons_nth_le _ hi]
 #align list.drop_take_succ_join_eq_nth_le List.drop_take_succ_join_eq_nthLe
--/
 
-#print List.sum_take_map_length_lt1 /-
 /-- Auxiliary lemma to control elements in a join. -/
 theorem sum_take_map_length_lt1 (L : List (List α)) {i j : ℕ} (hi : i < L.length)
     (hj : j < (nthLe L i hi).length) :
     ((L.map length).take i).Sum + j < ((L.map length).take (i + 1)).Sum := by
   simp [hi, sum_take_succ, hj]
 #align list.sum_take_map_length_lt1 List.sum_take_map_length_lt1
--/
 
 /-- Auxiliary lemma to control elements in a join. -/
 theorem sum_take_map_length_lt2 (L : List (List α)) {i j : ℕ} (hi : i < L.length)

be24ec5d

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) 2017 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Sébastien Gouëzel, Floris van Doorn, Mario Carneiro, Martin Dvorak
 -/
-import Data.List.BigOperators.Basic
+import Algebra.BigOperators.List.Basic
 
 #align_import data.list.join from "leanprover-community/mathlib"@"be24ec5de6701447e5df5ca75400ffee19d65659"
 
@@ -160,7 +160,6 @@ theorem sum_take_map_length_lt1 (L : List (List α)) {i j : ℕ} (hi : i < L.len
 #align list.sum_take_map_length_lt1 List.sum_take_map_length_lt1
 -/
 
-#print List.sum_take_map_length_lt2 /-
 /-- Auxiliary lemma to control elements in a join. -/
 theorem sum_take_map_length_lt2 (L : List (List α)) {i j : ℕ} (hi : i < L.length)
     (hj : j < (nthLe L i hi).length) : ((L.map length).take i).Sum + j < L.join.length :=
@@ -169,9 +168,7 @@ theorem sum_take_map_length_lt2 (L : List (List α)) {i j : ℕ} (hi : i < L.len
   have : L.length = (L.map length).length := by simp
   simp [this, -length_map]
 #align list.sum_take_map_length_lt2 List.sum_take_map_length_lt2
--/
 
-#print List.nthLe_join /-
 /-- The `n`-th element in a join of sublists is the `j`-th element of the `i`th sublist,
 where `n` can be obtained in terms of `i` and `j` by adding the lengths of all the sublists
 of index `< i`, and adding `j`. -/
@@ -183,7 +180,6 @@ theorem nthLe_join (L : List (List α)) {i j : ℕ} (hi : i < L.length)
   rw [nth_le_take L.join (sum_take_map_length_lt2 L hi hj) (sum_take_map_length_lt1 L hi hj),
     nth_le_drop, nth_le_of_eq (drop_take_succ_join_eq_nth_le L hi)]
 #align list.nth_le_join List.nthLe_join
--/
 
 #print List.eq_iff_join_eq /-
 /-- Two lists of sublists are equal iff their joins coincide, as well as the lengths of the

be24ec5d

bump to nightly-2024-03-17-08

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

22f01ce4

Diff

@@ -127,10 +127,10 @@ theorem drop_take_succ_eq_cons_nthLe (L : List α) {i : ℕ} (hi : i < L.length)
     (L.take (i + 1)).drop i = [nthLe L i hi] :=
   by
   induction L generalizing i
-  · simp only [length] at hi ; exact (Nat.not_succ_le_zero i hi).elim
+  · simp only [length] at hi; exact (Nat.not_succ_le_zero i hi).elim
   cases i; · simp
   have : i < L_tl.length := by
-    simp at hi 
+    simp at hi
     exact Nat.lt_of_succ_lt_succ hi
   simp [L_ih this]
   rfl

be24ec5d

bump to nightly-2024-02-27-08

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

cca8d078

Diff

@@ -50,14 +50,14 @@ theorem join_concat (L : List (List α)) (l : List α) : join (L.push l) = join
 #align list.join_concat List.join_concat
 -/
 
-#print List.join_filter_isEmpty_eq_false /-
+#print List.join_filter_not_isEmpty /-
 @[simp]
-theorem join_filter_isEmpty_eq_false [DecidablePred fun l : List α => l.Empty = false] :
+theorem join_filter_not_isEmpty [DecidablePred fun l : List α => l.Empty = false] :
     ∀ {L : List (List α)}, join (L.filterₓ fun l => l.Empty = false) = L.join
   | [] => rfl
   | [] :: L => by simp [@join_filter_empty_eq_ff L]
   | (a :: l) :: L => by simp [@join_filter_empty_eq_ff L]
-#align list.join_filter_empty_eq_ff List.join_filter_isEmpty_eq_false
+#align list.join_filter_empty_eq_ff List.join_filter_not_isEmpty
 -/
 
 #print List.join_filter_ne_nil /-

be24ec5d

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) 2017 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Sébastien Gouëzel, Floris van Doorn, Mario Carneiro, Martin Dvorak
 -/
-import Mathbin.Data.List.BigOperators.Basic
+import Data.List.BigOperators.Basic
 
 #align_import data.list.join from "leanprover-community/mathlib"@"be24ec5de6701447e5df5ca75400ffee19d65659"

be24ec5d

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) 2017 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Sébastien Gouëzel, Floris van Doorn, Mario Carneiro, Martin Dvorak
-
-! This file was ported from Lean 3 source module data.list.join
-! leanprover-community/mathlib commit be24ec5de6701447e5df5ca75400ffee19d65659
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Data.List.BigOperators.Basic
 
+#align_import data.list.join from "leanprover-community/mathlib"@"be24ec5de6701447e5df5ca75400ffee19d65659"
+
 /-!
 # Join of a list of lists

be24ec5d

bump to nightly-2023-06-18-23

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

3b5e23dc

Diff

@@ -49,7 +49,7 @@ theorem join_append (L₁ L₂ : List (List α)) : join (L₁ ++ L₂) = join L
 -/
 
 #print List.join_concat /-
-theorem join_concat (L : List (List α)) (l : List α) : join (L.concat l) = join L ++ l := by simp
+theorem join_concat (L : List (List α)) (l : List α) : join (L.push l) = join L ++ l := by simp
 #align list.join_concat List.join_concat
 -/

be24ec5d

bump to nightly-2023-06-13-21

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

829520ac

Diff

@@ -53,6 +53,7 @@ theorem join_concat (L : List (List α)) (l : List α) : join (L.concat l) = joi
 #align list.join_concat List.join_concat
 -/
 
+#print List.join_filter_isEmpty_eq_false /-
 @[simp]
 theorem join_filter_isEmpty_eq_false [DecidablePred fun l : List α => l.Empty = false] :
     ∀ {L : List (List α)}, join (L.filterₓ fun l => l.Empty = false) = L.join
@@ -60,12 +61,15 @@ theorem join_filter_isEmpty_eq_false [DecidablePred fun l : List α => l.Empty =
   | [] :: L => by simp [@join_filter_empty_eq_ff L]
   | (a :: l) :: L => by simp [@join_filter_empty_eq_ff L]
 #align list.join_filter_empty_eq_ff List.join_filter_isEmpty_eq_false
+-/
 
+#print List.join_filter_ne_nil /-
 @[simp]
 theorem join_filter_ne_nil [DecidablePred fun l : List α => l ≠ []] {L : List (List α)} :
     join (L.filterₓ fun l => l ≠ []) = L.join := by
   simp [join_filter_empty_eq_ff, ← empty_iff_eq_nil]
 #align list.join_filter_ne_nil List.join_filter_ne_nil
+-/
 
 #print List.join_join /-
 theorem join_join (l : List (List (List α))) : l.join.join = (l.map join).join := by induction l;
@@ -80,16 +84,20 @@ theorem length_join (L : List (List α)) : length (join L) = sum (map length L)
 #align list.length_join List.length_join
 -/
 
+#print List.length_bind /-
 @[simp]
 theorem length_bind (l : List α) (f : α → List β) :
     length (List.bind l f) = sum (map (length ∘ f) l) := by rw [List.bind, length_join, map_map]
 #align list.length_bind List.length_bind
+-/
 
+#print List.bind_eq_nil /-
 @[simp]
 theorem bind_eq_nil {l : List α} {f : α → List β} : List.bind l f = [] ↔ ∀ x ∈ l, f x = [] :=
   join_eq_nil.trans <| by
     simp only [mem_map, forall_exists_index, and_imp, forall_apply_eq_imp_iff₂]
 #align list.bind_eq_nil List.bind_eq_nil
+-/
 
 #print List.take_sum_join /-
 /-- In a join, taking the first elements up to an index which is the sum of the lengths of the

be24ec5d

bump to nightly-2023-06-01-16

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

b9c87c70

Diff

@@ -44,7 +44,7 @@ theorem join_eq_nil : ∀ {L : List (List α)}, join L = [] ↔ ∀ l ∈ L, l =
 #print List.join_append /-
 @[simp]
 theorem join_append (L₁ L₂ : List (List α)) : join (L₁ ++ L₂) = join L₁ ++ join L₂ := by
-  induction L₁ <;> [rfl;simp only [*, join, cons_append, append_assoc]]
+  induction L₁ <;> [rfl; simp only [*, join, cons_append, append_assoc]]
 #align list.join_append List.join_append
 -/
 
@@ -76,7 +76,7 @@ theorem join_join (l : List (List (List α))) : l.join.join = (l.map join).join
 #print List.length_join /-
 @[simp]
 theorem length_join (L : List (List α)) : length (join L) = sum (map length L) := by
-  induction L <;> [rfl;simp only [*, join, map, sum_cons, length_append]]
+  induction L <;> [rfl; simp only [*, join, map, sum_cons, length_append]]
 #align list.length_join List.length_join
 -/
 
@@ -122,10 +122,10 @@ theorem drop_take_succ_eq_cons_nthLe (L : List α) {i : ℕ} (hi : i < L.length)
     (L.take (i + 1)).drop i = [nthLe L i hi] :=
   by
   induction L generalizing i
-  · simp only [length] at hi; exact (Nat.not_succ_le_zero i hi).elim
+  · simp only [length] at hi ; exact (Nat.not_succ_le_zero i hi).elim
   cases i; · simp
   have : i < L_tl.length := by
-    simp at hi
+    simp at hi 
     exact Nat.lt_of_succ_lt_succ hi
   simp [L_ih this]
   rfl

be24ec5d

bump to nightly-2023-05-28-06

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

ba5d8b97

Diff

@@ -53,12 +53,6 @@ theorem join_concat (L : List (List α)) (l : List α) : join (L.concat l) = joi
 #align list.join_concat List.join_concat
 -/
 
-/- warning: list.join_filter_empty_eq_ff -> List.join_filter_isEmpty_eq_false is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} [_inst_1 : DecidablePred.{succ u1} (List.{u1} α) (fun (l : List.{u1} α) => Eq.{1} Bool (List.isEmpty.{u1} α l) Bool.false)] {L : List.{u1} (List.{u1} α)}, Eq.{succ u1} (List.{u1} α) (List.join.{u1} α (List.filterₓ.{u1} (List.{u1} α) (fun (l : List.{u1} α) => Eq.{1} Bool (List.isEmpty.{u1} α l) Bool.false) (fun (a : List.{u1} α) => _inst_1 a) L)) (List.join.{u1} α L)
-but is expected to have type
-  forall {α : Type.{u1}} [_inst_1 : DecidablePred.{succ u1} (List.{u1} α) (fun (l : List.{u1} α) => Eq.{1} Bool (List.isEmpty.{u1} α l) Bool.false)] {L : List.{u1} (List.{u1} α)}, Eq.{succ u1} (List.{u1} α) (List.join.{u1} α (List.filter.{u1} (List.{u1} α) (fun (a : List.{u1} α) => Decidable.decide (Eq.{1} Bool (List.isEmpty.{u1} α a) Bool.false) (_inst_1 a)) L)) (List.join.{u1} α L)
-Case conversion may be inaccurate. Consider using '#align list.join_filter_empty_eq_ff List.join_filter_isEmpty_eq_falseₓ'. -/
 @[simp]
 theorem join_filter_isEmpty_eq_false [DecidablePred fun l : List α => l.Empty = false] :
     ∀ {L : List (List α)}, join (L.filterₓ fun l => l.Empty = false) = L.join
@@ -67,12 +61,6 @@ theorem join_filter_isEmpty_eq_false [DecidablePred fun l : List α => l.Empty =
   | (a :: l) :: L => by simp [@join_filter_empty_eq_ff L]
 #align list.join_filter_empty_eq_ff List.join_filter_isEmpty_eq_false
 
-/- warning: list.join_filter_ne_nil -> List.join_filter_ne_nil is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} [_inst_1 : DecidablePred.{succ u1} (List.{u1} α) (fun (l : List.{u1} α) => Ne.{succ u1} (List.{u1} α) l (List.nil.{u1} α))] {L : List.{u1} (List.{u1} α)}, Eq.{succ u1} (List.{u1} α) (List.join.{u1} α (List.filterₓ.{u1} (List.{u1} α) (fun (l : List.{u1} α) => Ne.{succ u1} (List.{u1} α) l (List.nil.{u1} α)) (fun (a : List.{u1} α) => _inst_1 a) L)) (List.join.{u1} α L)
-but is expected to have type
-  forall {α : Type.{u1}} [_inst_1 : DecidablePred.{succ u1} (List.{u1} α) (fun (l : List.{u1} α) => Ne.{succ u1} (List.{u1} α) l (List.nil.{u1} α))] {L : List.{u1} (List.{u1} α)}, Eq.{succ u1} (List.{u1} α) (List.join.{u1} α (List.filter.{u1} (List.{u1} α) (fun (a : List.{u1} α) => Decidable.decide (Ne.{succ u1} (List.{u1} α) a (List.nil.{u1} α)) (_inst_1 a)) L)) (List.join.{u1} α L)
-Case conversion may be inaccurate. Consider using '#align list.join_filter_ne_nil List.join_filter_ne_nilₓ'. -/
 @[simp]
 theorem join_filter_ne_nil [DecidablePred fun l : List α => l ≠ []] {L : List (List α)} :
     join (L.filterₓ fun l => l ≠ []) = L.join := by
@@ -92,23 +80,11 @@ theorem length_join (L : List (List α)) : length (join L) = sum (map length L)
 #align list.length_join List.length_join
 -/
 
-/- warning: list.length_bind -> List.length_bind is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {β : Type.{u2}} (l : List.{u1} α) (f : α -> (List.{u2} β)), Eq.{1} Nat (List.length.{u2} β (List.bind.{u1, u2} α β l f)) (List.sum.{0} Nat Nat.hasAdd Nat.hasZero (List.map.{u1, 0} α Nat (Function.comp.{succ u1, succ u2, 1} α (List.{u2} β) Nat (List.length.{u2} β) f) l))
-but is expected to have type
-  forall {α : Type.{u2}} {β : Type.{u1}} (l : List.{u2} α) (f : α -> (List.{u1} β)), Eq.{1} Nat (List.length.{u1} β (List.bind.{u2, u1} α β l f)) (List.sum.{0} Nat instAddNat (LinearOrderedCommMonoidWithZero.toZero.{0} Nat Nat.linearOrderedCommMonoidWithZero) (List.map.{u2, 0} α Nat (Function.comp.{succ u2, succ u1, 1} α (List.{u1} β) Nat (List.length.{u1} β) f) l))
-Case conversion may be inaccurate. Consider using '#align list.length_bind List.length_bindₓ'. -/
 @[simp]
 theorem length_bind (l : List α) (f : α → List β) :
     length (List.bind l f) = sum (map (length ∘ f) l) := by rw [List.bind, length_join, map_map]
 #align list.length_bind List.length_bind
 
-/- warning: list.bind_eq_nil -> List.bind_eq_nil is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {β : Type.{u2}} {l : List.{u1} α} {f : α -> (List.{u2} β)}, Iff (Eq.{succ u2} (List.{u2} β) (List.bind.{u1, u2} α β l f) (List.nil.{u2} β)) (forall (x : α), (Membership.Mem.{u1, u1} α (List.{u1} α) (List.hasMem.{u1} α) x l) -> (Eq.{succ u2} (List.{u2} β) (f x) (List.nil.{u2} β)))
-but is expected to have type
-  forall {α : Type.{u2}} {β : Type.{u1}} {l : List.{u2} α} {f : α -> (List.{u1} β)}, Iff (Eq.{succ u1} (List.{u1} β) (List.bind.{u2, u1} α β l f) (List.nil.{u1} β)) (forall (x : α), (Membership.mem.{u2, u2} α (List.{u2} α) (List.instMembershipList.{u2} α) x l) -> (Eq.{succ u1} (List.{u1} β) (f x) (List.nil.{u1} β)))
-Case conversion may be inaccurate. Consider using '#align list.bind_eq_nil List.bind_eq_nilₓ'. -/
 @[simp]
 theorem bind_eq_nil {l : List α} {f : α → List β} : List.bind l f = [] ↔ ∀ x ∈ l, f x = [] :=
   join_eq_nil.trans <| by

be24ec5d

bump to nightly-2023-05-28-04

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

6797a637

Diff

@@ -80,11 +80,8 @@ theorem join_filter_ne_nil [DecidablePred fun l : List α => l ≠ []] {L : List
 #align list.join_filter_ne_nil List.join_filter_ne_nil
 
 #print List.join_join /-
-theorem join_join (l : List (List (List α))) : l.join.join = (l.map join).join :=
-  by
-  induction l
-  simp
-  simp [l_ih]
+theorem join_join (l : List (List (List α))) : l.join.join = (l.map join).join := by induction l;
+  simp; simp [l_ih]
 #align list.join_join List.join_join
 -/
 
@@ -149,10 +146,8 @@ theorem drop_take_succ_eq_cons_nthLe (L : List α) {i : ℕ} (hi : i < L.length)
     (L.take (i + 1)).drop i = [nthLe L i hi] :=
   by
   induction L generalizing i
-  · simp only [length] at hi
-    exact (Nat.not_succ_le_zero i hi).elim
-  cases i
-  · simp
+  · simp only [length] at hi; exact (Nat.not_succ_le_zero i hi).elim
+  cases i; · simp
   have : i < L_tl.length := by
     simp at hi
     exact Nat.lt_of_succ_lt_succ hi

be24ec5d

bump to nightly-2023-05-24-06

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

fbc7b476

Diff

@@ -44,7 +44,7 @@ theorem join_eq_nil : ∀ {L : List (List α)}, join L = [] ↔ ∀ l ∈ L, l =
 #print List.join_append /-
 @[simp]
 theorem join_append (L₁ L₂ : List (List α)) : join (L₁ ++ L₂) = join L₁ ++ join L₂ := by
-  induction L₁ <;> [rfl, simp only [*, join, cons_append, append_assoc]]
+  induction L₁ <;> [rfl;simp only [*, join, cons_append, append_assoc]]
 #align list.join_append List.join_append
 -/
 
@@ -91,7 +91,7 @@ theorem join_join (l : List (List (List α))) : l.join.join = (l.map join).join
 #print List.length_join /-
 @[simp]
 theorem length_join (L : List (List α)) : length (join L) = sum (map length L) := by
-  induction L <;> [rfl, simp only [*, join, map, sum_cons, length_append]]
+  induction L <;> [rfl;simp only [*, join, map, sum_cons, length_append]]
 #align list.length_join List.length_join
 -/

be24ec5d

bump to nightly-2023-02-21-16

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

1107b979

Changes in mathlib4

mathlib3

mathlib4

18a5306c

chore(Data/List): add dates to all deprecated lemmas (#12337)

Most of them go back to the port.

9150835a

Diff

@@ -54,7 +54,7 @@ theorem join_filter_not_isEmpty  :
       simp [join_filter_not_isEmpty (L := L)]
 #align list.join_filter_empty_eq_ff List.join_filter_not_isEmpty
 
-@[deprecated] alias join_filter_isEmpty_eq_false := join_filter_not_isEmpty
+@[deprecated] alias join_filter_isEmpty_eq_false := join_filter_not_isEmpty -- 2024-02-25
 
 @[simp]
 theorem join_filter_ne_nil [DecidablePred fun l : List α => l ≠ []] {L : List (List α)} :
@@ -131,7 +131,7 @@ theorem drop_take_succ_eq_cons_get (L : List α) (i : Fin L.length) :
 set_option linter.deprecated false in
 /-- Taking only the first `i+1` elements in a list, and then dropping the first `i` ones, one is
 left with a list of length `1` made of the `i`-th element of the original list. -/
-@[deprecated drop_take_succ_eq_cons_get]
+@[deprecated drop_take_succ_eq_cons_get] -- 2023-01-10
 theorem drop_take_succ_eq_cons_nthLe (L : List α) {i : ℕ} (hi : i < L.length) :
     (L.take (i + 1)).drop i = [nthLe L i hi] := by
   induction' L with head tail generalizing i

18a5306c

chore(Data/List/Join): better notation (#11724)

Summary of changes (all changes are cosmetic):

use L for a 2D lists instead of l consistently
use dot notation more
use anonymous function argument

869214f5

Diff

@@ -188,7 +188,7 @@ theorem join_drop_length_sub_one {L : List (List α)} (h : L ≠ []) :
 /-- We can rebracket `x ++ (l₁ ++ x) ++ (l₂ ++ x) ++ ... ++ (lₙ ++ x)` to
 `(x ++ l₁) ++ (x ++ l₂) ++ ... ++ (x ++ lₙ) ++ x` where `L = [l₁, l₂, ..., lₙ]`. -/
 theorem append_join_map_append (L : List (List α)) (x : List α) :
-    x ++ (List.map (fun l => l ++ x) L).join = (List.map (fun l => x ++ l) L).join ++ x := by
+    x ++ (L.map (· ++ x)).join = (L.map (x ++ ·)).join ++ x := by
   induction' L with _ _ ih
   · rw [map_nil, join, append_nil, map_nil, join, nil_append]
   · rw [map_cons, join, map_cons, join, append_assoc, ih, append_assoc, append_assoc]
@@ -196,7 +196,7 @@ theorem append_join_map_append (L : List (List α)) (x : List α) :
 
 /-- Reversing a join is the same as reversing the order of parts and reversing all parts. -/
 theorem reverse_join (L : List (List α)) :
-    L.join.reverse = (List.map List.reverse L).reverse.join := by
+    L.join.reverse = (L.map reverse).reverse.join := by
   induction' L with _ _ ih
   · rfl
   · rw [join, reverse_append, ih, map_cons, reverse_cons', join_concat]
@@ -204,14 +204,14 @@ theorem reverse_join (L : List (List α)) :
 
 /-- Joining a reverse is the same as reversing all parts and reversing the joined result. -/
 theorem join_reverse (L : List (List α)) :
-    L.reverse.join = (List.map List.reverse L).join.reverse := by
+    L.reverse.join = (L.map reverse).join.reverse := by
   simpa [reverse_reverse, map_reverse] using congr_arg List.reverse (reverse_join L.reverse)
 #align list.join_reverse List.join_reverse
 
-/-- Any member of `l : List (List α))` is a sublist of `l.join` -/
-lemma sublist_join (l : List (List α)) {s : List α} (hs : s ∈ l) :
-    List.Sublist s (l.join) := by
-  induction l with
+/-- Any member of `L : List (List α))` is a sublist of `L.join` -/
+lemma sublist_join (L : List (List α)) {s : List α} (hs : s ∈ L) :
+    s.Sublist L.join := by
+  induction L with
   | nil =>
     exfalso
     exact not_mem_nil s hs

18a5306c

chore(Data/List): Do not depend on algebra (#11845)

Remove dependencies on algebra in the Data.List folder except for:

Data.List.EditDistance: Actually relies on algebra. Maybe should be moved?
Data.List.Card: Completely unused and redundant.
Data.List.Cycle: Relies on Fintype, which shouldn't rely on algebra but it's hard to fix right now. Maybe should be moved?
Data.List.Func: Completely unused and redundant.
Data.List.Lex: That's order theory. Could be moved.
Data.List.Prime. That's algebra. Should definitely be moved.
Data.List.Sym: Relies on Multiset, which shouldn't rely on algebra but it's hard to fix right now. Maybe should be moved?
Data.List.ToFinsupp: That's algebra. Should definitely be moved.

As a consequence, move the big operators lemmas that were in there to Algebra.BigOperators.List.Basic. For the lemmas that were Nat-specific and not about auxiliary definitions, keep a version of them in the original file but stated using Nat.sum.

Before pre_11845

After post_11845

f9e043cb

Diff

@@ -3,7 +3,7 @@ Copyright (c) 2017 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Sébastien Gouëzel, Floris van Doorn, Mario Carneiro, Martin Dvorak
 -/
-import Mathlib.Algebra.BigOperators.List.Basic
+import Mathlib.Data.List.Basic
 
 #align_import data.list.join from "leanprover-community/mathlib"@"18a5306c091183ac90884daa9373fa3b178e8607"
 
@@ -14,6 +14,8 @@ This file proves basic properties of `List.join`, which concatenates a list of l
 in `Init.Data.List.Basic`.
 -/
 
+-- Make sure we don't import algebra
+assert_not_exists Monoid
 
 variable {α β : Type*}
 
@@ -64,31 +66,31 @@ theorem join_join (l : List (List (List α))) : l.join.join = (l.map join).join
   induction l <;> simp [*]
 #align list.join_join List.join_join
 
-@[simp]
-theorem length_join (L : List (List α)) : length (join L) = sum (map length L) := by
-  induction L <;> [rfl; simp only [*, join, map, sum_cons, length_append]]
-#align list.length_join List.length_join
+/-- See `List.length_join` for the corresponding statement using `List.sum`. -/
+lemma length_join' (L : List (List α)) : length (join L) = Nat.sum (map length L) := by
+  induction L <;> [rfl; simp only [*, join, map, Nat.sum_cons, length_append]]
 
-lemma countP_join (p : α → Bool) : ∀ L : List (List α), countP p L.join = (L.map (countP p)).sum
+/-- See `List.countP_join` for the corresponding statement using `List.sum`. -/
+lemma countP_join' (p : α → Bool) :
+    ∀ L : List (List α), countP p L.join = Nat.sum (L.map (countP p))
   | [] => rfl
-  | a :: l => by rw [join, countP_append, map_cons, sum_cons, countP_join _ l]
-#align list.countp_join List.countP_join
+  | a :: l => by rw [join, countP_append, map_cons, Nat.sum_cons, countP_join' _ l]
 
-lemma count_join [BEq α] (L : List (List α)) (a : α) : L.join.count a = (L.map (count a)).sum :=
-  countP_join _ _
-#align list.count_join List.count_join
+/-- See `List.count_join` for the corresponding statement using `List.sum`. -/
+lemma count_join' [BEq α] (L : List (List α)) (a : α) :
+    L.join.count a = Nat.sum (L.map (count a)) := countP_join' _ _
 
-@[simp]
-theorem length_bind (l : List α) (f : α → List β) :
-    length (List.bind l f) = sum (map (length ∘ f) l) := by rw [List.bind, length_join, map_map]
-#align list.length_bind List.length_bind
+/-- See `List.length_bind` for the corresponding statement using `List.sum`. -/
+lemma length_bind' (l : List α) (f : α → List β) :
+    length (l.bind f) = Nat.sum (map (length ∘ f) l) := by rw [List.bind, length_join', map_map]
 
-lemma countP_bind (p : β → Bool) (l : List α) (f : α → List β) :
-    countP p (l.bind f) = sum (map (countP p ∘ f) l) := by rw [List.bind, countP_join, map_map]
+/-- See `List.countP_bind` for the corresponding statement using `List.sum`. -/
+lemma countP_bind' (p : β → Bool) (l : List α) (f : α → List β) :
+    countP p (l.bind f) = Nat.sum (map (countP p ∘ f) l) := by rw [List.bind, countP_join', map_map]
 
-lemma count_bind [BEq β] (l : List α) (f : α → List β) (x : β) :
-    count x (l.bind f) = sum (map (count x ∘ f) l) := countP_bind _ _ _
-#align list.count_bind List.count_bind
+/-- See `List.count_bind` for the corresponding statement using `List.sum`. -/
+lemma count_bind' [BEq β] (l : List α) (f : α → List β) (x : β) :
+    count x (l.bind f) = Nat.sum (map (count x ∘ f) l) := countP_bind' _ _ _
 
 @[simp]
 theorem bind_eq_nil {l : List α} {f : α → List β} : List.bind l f = [] ↔ ∀ x ∈ l, f x = [] :=
@@ -97,22 +99,24 @@ theorem bind_eq_nil {l : List α} {f : α → List β} : List.bind l f = [] ↔
 #align list.bind_eq_nil List.bind_eq_nil
 
 /-- In a join, taking the first elements up to an index which is the sum of the lengths of the
-first `i` sublists, is the same as taking the join of the first `i` sublists. -/
-theorem take_sum_join (L : List (List α)) (i : ℕ) :
-    L.join.take ((L.map length).take i).sum = (L.take i).join := by
+first `i` sublists, is the same as taking the join of the first `i` sublists.
+
+See `List.take_sum_join` for the corresponding statement using `List.sum`. -/
+theorem take_sum_join' (L : List (List α)) (i : ℕ) :
+    L.join.take (Nat.sum ((L.map length).take i)) = (L.take i).join := by
   induction L generalizing i
   · simp
   · cases i <;> simp [take_append, *]
-#align list.take_sum_join List.take_sum_join
 
 /-- In a join, dropping all the elements up to an index which is the sum of the lengths of the
-first `i` sublists, is the same as taking the join after dropping the first `i` sublists. -/
-theorem drop_sum_join (L : List (List α)) (i : ℕ) :
-    L.join.drop ((L.map length).take i).sum = (L.drop i).join := by
+first `i` sublists, is the same as taking the join after dropping the first `i` sublists.
+
+See `List.drop_sum_join` for the corresponding statement using `List.sum`. -/
+theorem drop_sum_join' (L : List (List α)) (i : ℕ) :
+    L.join.drop (Nat.sum ((L.map length).take i)) = (L.drop i).join := by
   induction L generalizing i
   · simp
   · cases i <;> simp [drop_append, *]
-#align list.drop_sum_join List.drop_sum_join
 
 /-- Taking only the first `i+1` elements in a list, and then dropping the first `i` ones, one is
 left with a list of length `1` made of the `i`-th element of the original list. -/
@@ -145,36 +149,19 @@ theorem drop_take_succ_eq_cons_nthLe (L : List α) {i : ℕ} (hi : i < L.length)
 
 /-- In a join of sublists, taking the slice between the indices `A` and `B - 1` gives back the
 original sublist of index `i` if `A` is the sum of the lengths of sublists of index `< i`, and
-`B` is the sum of the lengths of sublists of index `≤ i`. -/
-theorem drop_take_succ_join_eq_get (L : List (List α)) (i : Fin L.length) :
-    (L.join.take ((L.map length).take (i + 1)).sum).drop ((L.map length).take i).sum =
+`B` is the sum of the lengths of sublists of index `≤ i`.
+
+See `List.drop_take_succ_join_eq_get` for the corresponding statement using `List.sum`. -/
+theorem drop_take_succ_join_eq_get' (L : List (List α)) (i : Fin L.length) :
+    (L.join.take (Nat.sum ((L.map length).take (i + 1)))).drop (Nat.sum ((L.map length).take i)) =
       get L i := by
   have : (L.map length).take i = ((L.take (i + 1)).map length).take i := by
-    simp [map_take, take_take]
-  simp only [this, length_map, take_sum_join, drop_sum_join, drop_take_succ_eq_cons_get,
+    simp [map_take, take_take, Nat.min_eq_left]
+  simp only [this, length_map, take_sum_join', drop_sum_join', drop_take_succ_eq_cons_get,
     join, append_nil]
 
-set_option linter.deprecated false in
-/-- In a join of sublists, taking the slice between the indices `A` and `B - 1` gives back the
-original sublist of index `i` if `A` is the sum of the lengths of sublists of index `< i`, and
-`B` is the sum of the lengths of sublists of index `≤ i`. -/
-@[deprecated drop_take_succ_join_eq_get]
-theorem drop_take_succ_join_eq_nthLe (L : List (List α)) {i : ℕ} (hi : i < L.length) :
-    (L.join.take ((L.map length).take (i + 1)).sum).drop ((L.map length).take i).sum =
-      nthLe L i hi := by
-  have : (L.map length).take i = ((L.take (i + 1)).map length).take i := by
-    simp [map_take, take_take]
-  simp [take_sum_join, this, drop_sum_join, drop_take_succ_eq_cons_nthLe _ hi]
-#align list.drop_take_succ_join_eq_nth_le List.drop_take_succ_join_eq_nthLe
-
-/-- Auxiliary lemma to control elements in a join. -/
-@[deprecated]
-theorem sum_take_map_length_lt1 (L : List (List α)) {i j : ℕ} (hi : i < L.length)
-    (hj : j < (L.get ⟨i, hi⟩).length) :
-    ((L.map length).take i).sum + j < ((L.map length).take (i + 1)).sum := by
-  simp [hi, sum_take_succ, hj]
-#align list.sum_take_map_length_lt1 List.sum_take_map_length_lt1
-
+#noalign list.drop_take_succ_join_eq_nth_le
+#noalign list.sum_take_map_length_lt1
 #noalign list.sum_take_map_length_lt2
 #noalign list.nth_le_join
 
@@ -188,7 +175,7 @@ theorem eq_iff_join_eq (L L' : List (List α)) :
   · have : length (map length L) = length (map length L') := by rw [length_eq]
     simpa using this
   · intro n h₁ h₂
-    rw [← drop_take_succ_join_eq_get, ← drop_take_succ_join_eq_get, join_eq, length_eq]
+    rw [← drop_take_succ_join_eq_get', ← drop_take_succ_join_eq_get', join_eq, length_eq]
 #align list.eq_iff_join_eq List.eq_iff_join_eq
 
 theorem join_drop_length_sub_one {L : List (List α)} (h : L ≠ []) :

18a5306c

chore(Data/List): Depend less on big operators (#11741)

Make Data.List.Count, Data.List.Dedup, Data.List.ProdSigma, Data.List.Range, Data.List.Rotate, Data.List.Zip not depend on Data.List.BigOperators.Basic.
As a consequence, move the big operators lemmas that were in there to Data.List.BigOperators.Basic. For the lemmas that were Nat-specific, keep a version of them in the original file but stated using Nat.sum.
To help with this, add Nat.sum_eq_listSum (l : List Nat) : Nat.sum l = l.sum.

9158f323

Diff

@@ -69,11 +69,27 @@ theorem length_join (L : List (List α)) : length (join L) = sum (map length L)
   induction L <;> [rfl; simp only [*, join, map, sum_cons, length_append]]
 #align list.length_join List.length_join
 
+lemma countP_join (p : α → Bool) : ∀ L : List (List α), countP p L.join = (L.map (countP p)).sum
+  | [] => rfl
+  | a :: l => by rw [join, countP_append, map_cons, sum_cons, countP_join _ l]
+#align list.countp_join List.countP_join
+
+lemma count_join [BEq α] (L : List (List α)) (a : α) : L.join.count a = (L.map (count a)).sum :=
+  countP_join _ _
+#align list.count_join List.count_join
+
 @[simp]
 theorem length_bind (l : List α) (f : α → List β) :
     length (List.bind l f) = sum (map (length ∘ f) l) := by rw [List.bind, length_join, map_map]
 #align list.length_bind List.length_bind
 
+lemma countP_bind (p : β → Bool) (l : List α) (f : α → List β) :
+    countP p (l.bind f) = sum (map (countP p ∘ f) l) := by rw [List.bind, countP_join, map_map]
+
+lemma count_bind [BEq β] (l : List α) (f : α → List β) (x : β) :
+    count x (l.bind f) = sum (map (count x ∘ f) l) := countP_bind _ _ _
+#align list.count_bind List.count_bind
+
 @[simp]
 theorem bind_eq_nil {l : List α} {f : α → List β} : List.bind l f = [] ↔ ∀ x ∈ l, f x = [] :=
   join_eq_nil.trans <| by

18a5306c

move(Data/List/BigOperators): Move to Algebra.BigOperators.List (#11729)

This is algebra and should be foldered as such.

f09ccf67

Diff

@@ -3,7 +3,7 @@ Copyright (c) 2017 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Sébastien Gouëzel, Floris van Doorn, Mario Carneiro, Martin Dvorak
 -/
-import Mathlib.Data.List.BigOperators.Basic
+import Mathlib.Algebra.BigOperators.List.Basic
 
 #align_import data.list.join from "leanprover-community/mathlib"@"18a5306c091183ac90884daa9373fa3b178e8607"

18a5306c

chore(Data/List/Join): Delete deprecated lemmas (#11665)

These two lemmas have been deprecated for more than a year and are on my way for #11633.

c9c8738e

Diff

@@ -159,28 +159,8 @@ theorem sum_take_map_length_lt1 (L : List (List α)) {i j : ℕ} (hi : i < L.len
   simp [hi, sum_take_succ, hj]
 #align list.sum_take_map_length_lt1 List.sum_take_map_length_lt1
 
-set_option linter.deprecated false in
-/-- Auxiliary lemma to control elements in a join. -/
-@[deprecated]
-theorem sum_take_map_length_lt2 (L : List (List α)) {i j : ℕ} (hi : i < L.length)
-    (hj : j < (nthLe L i hi).length) : ((L.map length).take i).sum + j < L.join.length := by
-  convert lt_of_lt_of_le (sum_take_map_length_lt1 L hi hj) (monotone_sum_take _ hi)
-  have : L.length = (L.map length).length := by simp
-  simp [this, -length_map]
-#align list.sum_take_map_length_lt2 List.sum_take_map_length_lt2
-
-set_option linter.deprecated false in
-/-- The `n`-th element in a join of sublists is the `j`-th element of the `i`th sublist,
-where `n` can be obtained in terms of `i` and `j` by adding the lengths of all the sublists
-of index `< i`, and adding `j`. -/
-@[deprecated]
-theorem nthLe_join (L : List (List α)) {i j : ℕ} (hi : i < L.length)
-    (hj : j < (nthLe L i hi).length) :
-    nthLe L.join (((L.map length).take i).sum + j) (sum_take_map_length_lt2 L hi hj) =
-      nthLe (nthLe L i hi) j hj := by
-  have := nthLe_take L.join (sum_take_map_length_lt2 L hi hj) (sum_take_map_length_lt1 L hi hj)
-  rw [this, nthLe_drop, nthLe_of_eq (drop_take_succ_join_eq_nthLe L hi)]
-#align list.nth_le_join List.nthLe_join
+#noalign list.sum_take_map_length_lt2
+#noalign list.nth_le_join
 
 /-- Two lists of sublists are equal iff their joins coincide, as well as the lengths of the
 sublists. -/

18a5306c

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

@@ -57,7 +57,7 @@ theorem join_filter_not_isEmpty  :
 @[simp]
 theorem join_filter_ne_nil [DecidablePred fun l : List α => l ≠ []] {L : List (List α)} :
     join (L.filter fun l => l ≠ []) = L.join := by
-  simp only [Ne.def, join_filter_not_isEmpty, ← isEmpty_iff_eq_nil, decide_not, Bool.decide_coe]
+  simp [join_filter_not_isEmpty, ← isEmpty_iff_eq_nil]
 #align list.join_filter_ne_nil List.join_filter_ne_nil
 
 theorem join_join (l : List (List (List α))) : l.join.join = (l.map join).join := by

18a5306c

chore: fix port of join_filter_isEmpty_eq_false (#10951)

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

23adc289

Diff

@@ -42,23 +42,22 @@ theorem join_append (L₁ L₂ : List (List α)) : join (L₁ ++ L₂) = join L
 theorem join_concat (L : List (List α)) (l : List α) : join (L.concat l) = join L ++ l := by simp
 #align list.join_concat List.join_concat
 
--- Porting note: `ff/tt` should be translated to `false/true`.
--- Porting note: `List.filter` now takes a `Bool` not a `Prop`.
---     Should the correct spelling now be `== false` instead?
 @[simp]
-theorem join_filter_isEmpty_eq_false [DecidablePred fun l : List α => l.isEmpty = false] :
-    ∀ {L : List (List α)}, join (L.filter fun l => l.isEmpty = false) = L.join
+theorem join_filter_not_isEmpty  :
+    ∀ {L : List (List α)}, join (L.filter fun l => !l.isEmpty) = L.join
   | [] => rfl
   | [] :: L => by
-      simp [join_filter_isEmpty_eq_false (L := L), isEmpty_iff_eq_nil]
+      simp [join_filter_not_isEmpty (L := L), isEmpty_iff_eq_nil]
   | (a :: l) :: L => by
-      simp [join_filter_isEmpty_eq_false (L := L)]
-#align list.join_filter_empty_eq_ff List.join_filter_isEmpty_eq_false
+      simp [join_filter_not_isEmpty (L := L)]
+#align list.join_filter_empty_eq_ff List.join_filter_not_isEmpty
+
+@[deprecated] alias join_filter_isEmpty_eq_false := join_filter_not_isEmpty
 
 @[simp]
 theorem join_filter_ne_nil [DecidablePred fun l : List α => l ≠ []] {L : List (List α)} :
     join (L.filter fun l => l ≠ []) = L.join := by
-  simp [join_filter_isEmpty_eq_false, ← isEmpty_iff_eq_nil]
+  simp only [Ne.def, join_filter_not_isEmpty, ← isEmpty_iff_eq_nil, decide_not, Bool.decide_coe]
 #align list.join_filter_ne_nil List.join_filter_ne_nil
 
 theorem join_join (l : List (List (List α))) : l.join.join = (l.map join).join := by

18a5306c

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

@@ -21,7 +21,7 @@ namespace List
 
 attribute [simp] join
 
--- Porting note: simp can prove this
+-- Porting note (#10618): simp can prove this
 -- @[simp]
 theorem join_singleton (l : List α) : [l].join = l := by rw [join, join, append_nil]
 #align list.join_singleton List.join_singleton

18a5306c

chore: move to v4.5.0-rc1, and merge changes from bump/v4.5.0 branch. (#9188)

This PR:

bumps to lean-toolchain to v4.5.0-rc1
bumps the Std and Aesop dependencies to their versions using v4.5.0-rc1
merge the already reviewed changes from the bump/v4.5.0 branch
- adaptations for leanprover/lean4#2923 in #9011
- adaptations for leanprover/lean4#2973 in #9161
- adaptations for leanprover/lean4#2964 in #9176

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

58eef79b

Diff

@@ -52,8 +52,7 @@ theorem join_filter_isEmpty_eq_false [DecidablePred fun l : List α => l.isEmpty
   | [] :: L => by
       simp [join_filter_isEmpty_eq_false (L := L), isEmpty_iff_eq_nil]
   | (a :: l) :: L => by
-      have cons_not_empty : isEmpty (a :: l) = false := rfl
-      simp [join_filter_isEmpty_eq_false (L := L), cons_not_empty]
+      simp [join_filter_isEmpty_eq_false (L := L)]
 #align list.join_filter_empty_eq_ff List.join_filter_isEmpty_eq_false
 
 @[simp]

18a5306c

chore: Remove nonterminal simp at (#7795)

Removes nonterminal uses of simp at. Replaces most of these with instances of simp? ... says.

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Mario Carneiro <di.gama@gmail.com>

4160b2aa

Diff

@@ -123,7 +123,7 @@ theorem drop_take_succ_eq_cons_nthLe (L : List α) {i : ℕ} (hi : i < L.length)
   · simp
     rfl
   have : i < tail.length := by
-    simp at hi
+    simp? at hi says simp only [length_cons] at hi
     exact Nat.lt_of_succ_lt_succ hi
   simp [*]
   rfl

18a5306c

chore: refactor prod_take_succ to List.get (#8043)

Needed to finish what was started in #8039

Co-authored-by: Moritz Firsching <firsching@google.com>

5561bd39

Diff

@@ -153,11 +153,10 @@ theorem drop_take_succ_join_eq_nthLe (L : List (List α)) {i : ℕ} (hi : i < L.
   simp [take_sum_join, this, drop_sum_join, drop_take_succ_eq_cons_nthLe _ hi]
 #align list.drop_take_succ_join_eq_nth_le List.drop_take_succ_join_eq_nthLe
 
-set_option linter.deprecated false in
 /-- Auxiliary lemma to control elements in a join. -/
 @[deprecated]
 theorem sum_take_map_length_lt1 (L : List (List α)) {i j : ℕ} (hi : i < L.length)
-    (hj : j < (nthLe L i hi).length) :
+    (hj : j < (L.get ⟨i, hi⟩).length) :
     ((L.map length).take i).sum + j < ((L.map length).take (i + 1)).sum := by
   simp [hi, sum_take_succ, hj]
 #align list.sum_take_map_length_lt1 List.sum_take_map_length_lt1

18a5306c

feat (GroupTheory.Perm.Cycle.PossibleTypes) : cycleTypes of perm (#7433)

Characterize the possible types of permutations: given m : Multiset ℕ, there are permutations in Equiv.Perm α with cycleType m if and only if m.sumis at most Fintype.card α and the members of m are at least 2.

This result will be used in later PR which computes the cardinality of conjugacy classes in Equiv.Perm α and alternatingGroup α

Co-authored-by: Antoine Chambert-Loir <antoine.chambert-loir@math.univ-paris-diderot.fr>

645da3e5

Diff

@@ -228,4 +228,20 @@ theorem join_reverse (L : List (List α)) :
   simpa [reverse_reverse, map_reverse] using congr_arg List.reverse (reverse_join L.reverse)
 #align list.join_reverse List.join_reverse
 
+/-- Any member of `l : List (List α))` is a sublist of `l.join` -/
+lemma sublist_join (l : List (List α)) {s : List α} (hs : s ∈ l) :
+    List.Sublist s (l.join) := by
+  induction l with
+  | nil =>
+    exfalso
+    exact not_mem_nil s hs
+  | cons t m ht =>
+    cases mem_cons.mp hs with
+    | inl h =>
+      rw [h]
+      simp only [join_cons, sublist_append_left]
+    | inr h =>
+      simp only [join_cons]
+      exact sublist_append_of_sublist_right (ht h)
+
 end List

18a5306c

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

@@ -15,7 +15,7 @@ in `Init.Data.List.Basic`.
 -/
 
 
-variable {α β : Type _}
+variable {α β : Type*}
 
 namespace List

18a5306c

chore: bump to nightly-2023-07-15 (#5992)

Various adaptations to changes when Fin API was moved to Std. One notable change is that many lemmas are now stated in terms of i ≠ 0 (for i : Fin n) rather then i.1 ≠ 0, and as a consequence many Fin.vne_of_ne applications have been added or removed, mostly removed.

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

24924f96

Diff

@@ -137,7 +137,8 @@ theorem drop_take_succ_join_eq_get (L : List (List α)) (i : Fin L.length) :
       get L i := by
   have : (L.map length).take i = ((L.take (i + 1)).map length).take i := by
     simp [map_take, take_take]
-  simp [take_sum_join, this, drop_sum_join, drop_take_succ_eq_cons_get]
+  simp only [this, length_map, take_sum_join, drop_sum_join, drop_take_succ_eq_cons_get,
+    join, append_nil]
 
 set_option linter.deprecated false in
 /-- In a join of sublists, taking the slice between the indices `A` and `B - 1` gives back the

18a5306c

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) 2017 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Sébastien Gouëzel, Floris van Doorn, Mario Carneiro, Martin Dvorak
-
-! This file was ported from Lean 3 source module data.list.join
-! leanprover-community/mathlib commit 18a5306c091183ac90884daa9373fa3b178e8607
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Data.List.BigOperators.Basic
 
+#align_import data.list.join from "leanprover-community/mathlib"@"18a5306c091183ac90884daa9373fa3b178e8607"
+
 /-!
 # Join of a list of lists

18a5306c

chore: fix typos (#4518)

I ran codespell Mathlib and got tired halfway through the suggestions.

92beef58

Diff

@@ -133,7 +133,7 @@ theorem drop_take_succ_eq_cons_nthLe (L : List α) {i : ℕ} (hi : i < L.length)
 #align list.drop_take_succ_eq_cons_nth_le List.drop_take_succ_eq_cons_nthLe
 
 /-- In a join of sublists, taking the slice between the indices `A` and `B - 1` gives back the
-original sublist of index `i` if `A` is the sum of the lenghts of sublists of index `< i`, and
+original sublist of index `i` if `A` is the sum of the lengths of sublists of index `< i`, and
 `B` is the sum of the lengths of sublists of index `≤ i`. -/
 theorem drop_take_succ_join_eq_get (L : List (List α)) (i : Fin L.length) :
     (L.join.take ((L.map length).take (i + 1)).sum).drop ((L.map length).take i).sum =
@@ -144,7 +144,7 @@ theorem drop_take_succ_join_eq_get (L : List (List α)) (i : Fin L.length) :
 
 set_option linter.deprecated false in
 /-- In a join of sublists, taking the slice between the indices `A` and `B - 1` gives back the
-original sublist of index `i` if `A` is the sum of the lenghts of sublists of index `< i`, and
+original sublist of index `i` if `A` is the sum of the lengths of sublists of index `< i`, and
 `B` is the sum of the lengths of sublists of index `≤ i`. -/
 @[deprecated drop_take_succ_join_eq_get]
 theorem drop_take_succ_join_eq_nthLe (L : List (List α)) {i : ℕ} (hi : i < L.length) :

18a5306c

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

@@ -71,7 +71,7 @@ theorem join_join (l : List (List (List α))) : l.join.join = (l.map join).join
 
 @[simp]
 theorem length_join (L : List (List α)) : length (join L) = sum (map length L) := by
-  induction L <;> [rfl, simp only [*, join, map, sum_cons, length_append]]
+  induction L <;> [rfl; simp only [*, join, map, sum_cons, length_append]]
 #align list.length_join List.length_join
 
 @[simp]

18a5306c

chore: bump Std (#3113)

Notably incorporates https://github.com/leanprover/std4/pull/98 and https://github.com/leanprover/std4/pull/109.

https://github.com/leanprover/std4/pull/98 moves a number of lemmas from Mathlib to Std, so the bump requires deleting them in Mathlib. I did check on each lemma whether its attributes were kept in the move (and gave attribute markings in Mathlib if they were not present in Std), but a reviewer may wish to re-check.

List.mem_map changed statement from b ∈ l.map f ↔ ∃ a, a ∈ l ∧ b = f a to b ∈ l.map f ↔ ∃ a, a ∈ l ∧ f a = b. Similarly for List.exists_of_mem_map. This was a deliberate change, so I have simply adjusted proofs (many become simpler, which supports the change). I also deleted List.mem_map', List.exists_of_mem_map', which were temporary versions in Mathlib while waiting for this change (replacing their uses with the unprimed versions).

Also, the lemma sublist_nil_iff_eq_nil seems to have been renamed to sublist_nil during the move, so I added an alias for the old name.

(another issue fixed during review by @digama0) List.Sublist.filter had an argument change from explicit to implicit. This appears to have been an oversight (cc @JamesGallicchio). I have temporarily introduced List.Sublist.filter' with the argument explicit, and replaced Mathlib uses of Sublist.filter with Sublist.filter'. Later we can fix the argument in Std, and then delete List.Sublist.filter'.

a0733e9e

Diff

@@ -82,7 +82,7 @@ theorem length_bind (l : List α) (f : α → List β) :
 @[simp]
 theorem bind_eq_nil {l : List α} {f : α → List β} : List.bind l f = [] ↔ ∀ x ∈ l, f x = [] :=
   join_eq_nil.trans <| by
-    simp only [mem_map', forall_exists_index, and_imp, forall_apply_eq_imp_iff₂]
+    simp only [mem_map, forall_exists_index, and_imp, forall_apply_eq_imp_iff₂]
 #align list.bind_eq_nil List.bind_eq_nil
 
 /-- In a join, taking the first elements up to an index which is the sum of the lengths of the

18a5306c

chore: format by line breaks (#1523)

During porting, I usually fix the desired format we seem to want for the line breaks around by with

awk '{do {{if (match($0, "^  by$") && length(p) < 98) {p=p " by";} else {if (NR!=1) {print p}; p=$0}}} while (getline == 1) if (getline==0) print p}' Mathlib/File/Im/Working/On.lean

I noticed there are some more files that slipped through.

This pull request is the result of running this command:

grep -lr "^  by\$" Mathlib | xargs -n 1 awk -i inplace '{do {{if (match($0, "^  by$") && length(p) < 98 && not (match(p, "^[ \t]*--"))) {p=p " by";} else {if (NR!=1) {print p}; p=$0}}} while (getline == 1) if (getline==0) print p}'

Co-authored-by: Moritz Firsching <firsching@google.com>

d6d859a7

Diff

@@ -149,8 +149,7 @@ original sublist of index `i` if `A` is the sum of the lenghts of sublists of in
 @[deprecated drop_take_succ_join_eq_get]
 theorem drop_take_succ_join_eq_nthLe (L : List (List α)) {i : ℕ} (hi : i < L.length) :
     (L.join.take ((L.map length).take (i + 1)).sum).drop ((L.map length).take i).sum =
-      nthLe L i hi :=
-  by
+      nthLe L i hi := by
   have : (L.map length).take i = ((L.take (i + 1)).map length).take i := by
     simp [map_take, take_take]
   simp [take_sum_join, this, drop_sum_join, drop_take_succ_eq_cons_nthLe _ hi]

18a5306c

feat: port Data.List.Join (#1395)

depends on: #1380

Co-authored-by: ChrisHughes24 <chrishughes24@gmail.com> Co-authored-by: thirdsgames <thirdsgames2018@gmail.com> Co-authored-by: zeramorphic <zeramorphic@proton.me>

07eef429

`data.list.join` ⟷ `Mathlib.Data.List.Join`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 2 + 87

data.list.join ⟷ Mathlib.Data.List.Join

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 2 + 87

`data.list.join` ⟷ `Mathlib.Data.List.Join`