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

f694c7de

(last sync)

refactor(*): define list.replicate and migrate to it (#18127)

This definition differs from list.repeat by the order of arguments. The new order is in sync with the Lean 4 version.

Diff

@@ -99,10 +99,9 @@ by rw [rotate_eq_rotate', rotate_eq_rotate', rotate'_cons_succ]
 @[simp] lemma length_rotate (l : list α) (n : ℕ) : (l.rotate n).length = l.length :=
 by rw [rotate_eq_rotate', length_rotate']
 
-lemma rotate_repeat (a : α) (n : ℕ) (k : ℕ) :
-  (repeat a n).rotate k = repeat a n :=
-eq_repeat.2 ⟨by rw [length_rotate, length_repeat],
-  λ b hb, eq_of_mem_repeat $ mem_rotate.1 hb⟩
+lemma rotate_replicate (a : α) (n : ℕ) (k : ℕ) : (replicate n a).rotate k = replicate n a :=
+eq_replicate.2 ⟨by rw [length_rotate, length_replicate],
+  λ b hb, eq_of_mem_replicate $ mem_rotate.1 hb⟩
 
 lemma rotate_eq_drop_append_take {l : list α} {n : ℕ} : n ≤ l.length →
   l.rotate n = l.drop n ++ l.take n :=
@@ -170,7 +169,7 @@ by rw [eq_comm, rotate_eq_nil_iff, eq_comm]
 
 @[simp] lemma rotate_singleton (x : α) (n : ℕ) :
   [x].rotate n = [x] :=
-rotate_repeat x 1 n
+rotate_replicate x 1 n
 
 lemma zip_with_rotate_distrib {α β γ : Type*} (f : α → β → γ) (l : list α) (l' : list β) (n : ℕ)
   (h : l.length = l'.length) :
@@ -241,22 +240,22 @@ lemma head'_rotate {l : list α} {n : ℕ} (h : n < l.length) :
   head' (l.rotate n) = l.nth n :=
 by rw [← nth_zero, nth_rotate (n.zero_le.trans_lt h), zero_add, nat.mod_eq_of_lt h]
 
-lemma rotate_eq_self_iff_eq_repeat [hα : nonempty α] :
-  ∀ {l : list α}, (∀ n, l.rotate n = l) ↔ ∃ a, l = repeat a l.length
+lemma rotate_eq_self_iff_eq_replicate [hα : nonempty α] :
+  ∀ {l : list α}, (∀ n, l.rotate n = l) ↔ ∃ a, l = replicate l.length a
 | [] := by simp
-| (a :: l) := ⟨λ h, ⟨a, ext_le (length_repeat _ _).symm $ λ n h₁ h₂,
+| (a :: l) := ⟨λ h, ⟨a, ext_le (length_replicate _ _).symm $ λ n h₁ h₂,
   begin
     inhabit α,
-    rw [nth_le_repeat, ← option.some_inj, ← nth_le_nth, ← head'_rotate h₁, h, head']
-  end⟩, λ ⟨b, hb⟩ n, by rw [hb, rotate_repeat]⟩
+    rw [nth_le_replicate, ← option.some_inj, ← nth_le_nth, ← head'_rotate h₁, h, head']
+  end⟩, λ ⟨b, hb⟩ n, by rw [hb, rotate_replicate]⟩
 
-lemma rotate_one_eq_self_iff_eq_repeat [nonempty α] {l : list α} :
-  l.rotate 1 = l ↔ ∃ a : α, l = repeat a l.length :=
-⟨λ h, rotate_eq_self_iff_eq_repeat.mp (λ n, nat.rec l.rotate_zero
+lemma rotate_one_eq_self_iff_eq_replicate [nonempty α] {l : list α} :
+  l.rotate 1 = l ↔ ∃ a : α, l = list.replicate l.length a :=
+⟨λ h, rotate_eq_self_iff_eq_replicate.mp (λ n, nat.rec l.rotate_zero
   (λ n hn, by rwa [nat.succ_eq_add_one, ←l.rotate_rotate, hn]) n),
-    λ h, rotate_eq_self_iff_eq_repeat.mpr h 1⟩
+    λ h, rotate_eq_self_iff_eq_replicate.mpr h 1⟩
 
-lemma rotate_injective (n : ℕ) : injective (λ l : list α, l.rotate n) :=
+lemma rotate_injective (n : ℕ) : function.injective (λ l : list α, l.rotate n) :=
 begin
   rintro l₁ l₂ (h : l₁.rotate n = l₂.rotate n),
   have : length l₁ = length l₂, by simpa only [length_rotate] using congr_arg length h,
@@ -282,7 +281,7 @@ begin
 end
 
 @[simp] lemma rotate_eq_singleton_iff {l : list α} {n : ℕ} {x : α} : l.rotate n = [x] ↔ l = [x] :=
-⟨λ h, by rw [rotate_eq_iff.1 h, rotate_singleton], λ h, h.symm ▸ rotate_singleton _ _⟩
+by rw [rotate_eq_iff, rotate_singleton]
 
 @[simp] lemma singleton_eq_rotate_iff {l : list α} {n : ℕ} {x : α} : [x] = l.rotate n ↔ [x] = l :=
 by rw [eq_comm, rotate_eq_singleton_iff, eq_comm]

527e406f

chore(data/list): golf, merge 2 files (#18120)

merge data.list.modeq into data.list.rotate;
mark list.rotate_eq_rotate as @[simp];
golf some proofs.

Diff

@@ -24,7 +24,7 @@ rotated, rotation, permutation, cycle
 universe u
 variables {α : Type u}
 
-open nat
+open nat function
 
 namespace list
 
@@ -99,6 +99,11 @@ by rw [rotate_eq_rotate', rotate_eq_rotate', rotate'_cons_succ]
 @[simp] lemma length_rotate (l : list α) (n : ℕ) : (l.rotate n).length = l.length :=
 by rw [rotate_eq_rotate', length_rotate']
 
+lemma rotate_repeat (a : α) (n : ℕ) (k : ℕ) :
+  (repeat a n).rotate k = repeat a n :=
+eq_repeat.2 ⟨by rw [length_rotate, length_repeat],
+  λ b hb, eq_of_mem_repeat $ mem_rotate.1 hb⟩
+
 lemma rotate_eq_drop_append_take {l : list α} {n : ℕ} : n ≤ l.length →
   l.rotate n = l.drop n ++ l.take n :=
 by rw rotate_eq_rotate'; exact rotate'_eq_drop_append_take
@@ -165,23 +170,7 @@ by rw [eq_comm, rotate_eq_nil_iff, eq_comm]
 
 @[simp] lemma rotate_singleton (x : α) (n : ℕ) :
   [x].rotate n = [x] :=
-begin
-  induction n with n hn,
-  { simp },
-  { rwa [rotate_cons_succ] }
-end
-
-@[simp] lemma rotate_eq_singleton_iff {l : list α} {n : ℕ} {x : α} : l.rotate n = [x] ↔ l = [x] :=
-begin
-  induction n with n hn generalizing l,
-  { simp },
-  { cases l with hd tl,
-    { simp },
-    { simp [rotate_cons_succ, hn, append_eq_cons_iff, and_comm] } }
-end
-
-@[simp] lemma singleton_eq_rotate_iff {l : list α} {n : ℕ} {x : α} : [x] = l.rotate n ↔ [x] = l :=
-by rw [eq_comm, rotate_eq_singleton_iff, eq_comm]
+rotate_repeat x 1 n
 
 lemma zip_with_rotate_distrib {α β γ : Type*} (f : α → β → γ) (l : list α) (l' : list β) (n : ℕ)
   (h : l.length = l'.length) :
@@ -241,18 +230,42 @@ begin
     simpa [mod_eq_of_lt hm, tsub_add_cancel_of_le hn'.le] using nat.mod_eq_of_lt hk }
 end
 
-lemma rotate_injective (n : ℕ) : function.injective (λ l : list α, l.rotate n) :=
+lemma nth_rotate {l : list α} {n m : ℕ} (hml : m < l.length) :
+  (l.rotate n).nth m = l.nth ((m + n) % l.length) :=
 begin
-  rintros l l' (h : l.rotate n = l'.rotate n),
-  have hle : l.length = l'.length := (l.length_rotate n).symm.trans (h.symm ▸ l'.length_rotate n),
-  rw [rotate_eq_drop_append_take_mod, rotate_eq_drop_append_take_mod] at h,
-  obtain ⟨hd, ht⟩ := append_inj h _,
-  { rw [←take_append_drop _ l, ht, hd, take_append_drop] },
-  { rw [length_drop, length_drop, hle] }
+  rw [nth_le_nth, nth_le_nth (nat.mod_lt _ _), nth_le_rotate],
+  rwa [length_rotate]
 end
 
--- possibly easier to find in doc-gen, otherwise not that useful.
-lemma rotate_eq_rotate {l l' : list α} {n : ℕ} :
+lemma head'_rotate {l : list α} {n : ℕ} (h : n < l.length) :
+  head' (l.rotate n) = l.nth n :=
+by rw [← nth_zero, nth_rotate (n.zero_le.trans_lt h), zero_add, nat.mod_eq_of_lt h]
+
+lemma rotate_eq_self_iff_eq_repeat [hα : nonempty α] :
+  ∀ {l : list α}, (∀ n, l.rotate n = l) ↔ ∃ a, l = repeat a l.length
+| [] := by simp
+| (a :: l) := ⟨λ h, ⟨a, ext_le (length_repeat _ _).symm $ λ n h₁ h₂,
+  begin
+    inhabit α,
+    rw [nth_le_repeat, ← option.some_inj, ← nth_le_nth, ← head'_rotate h₁, h, head']
+  end⟩, λ ⟨b, hb⟩ n, by rw [hb, rotate_repeat]⟩
+
+lemma rotate_one_eq_self_iff_eq_repeat [nonempty α] {l : list α} :
+  l.rotate 1 = l ↔ ∃ a : α, l = repeat a l.length :=
+⟨λ h, rotate_eq_self_iff_eq_repeat.mp (λ n, nat.rec l.rotate_zero
+  (λ n hn, by rwa [nat.succ_eq_add_one, ←l.rotate_rotate, hn]) n),
+    λ h, rotate_eq_self_iff_eq_repeat.mpr h 1⟩
+
+lemma rotate_injective (n : ℕ) : injective (λ l : list α, l.rotate n) :=
+begin
+  rintro l₁ l₂ (h : l₁.rotate n = l₂.rotate n),
+  have : length l₁ = length l₂, by simpa only [length_rotate] using congr_arg length h,
+  refine ext_le this (λ k h₁ h₂, _),
+  rw [← nth_le_rotate' l₁ n, ← nth_le_rotate' l₂ n],
+  congr' 1; simp only [h, this]
+end
+
+@[simp] lemma rotate_eq_rotate {l l' : list α} {n : ℕ} :
   l.rotate n = l'.rotate n ↔ l = l' :=
 (rotate_injective n).eq_iff
 
@@ -268,6 +281,12 @@ begin
       exact (nat.mod_lt _ hl).le } }
 end
 
+@[simp] lemma rotate_eq_singleton_iff {l : list α} {n : ℕ} {x : α} : l.rotate n = [x] ↔ l = [x] :=
+⟨λ h, by rw [rotate_eq_iff.1 h, rotate_singleton], λ h, h.symm ▸ rotate_singleton _ _⟩
+
+@[simp] lemma singleton_eq_rotate_iff {l : list α} {n : ℕ} {x : α} : [x] = l.rotate n ↔ [x] = l :=
+by rw [eq_comm, rotate_eq_singleton_iff, eq_comm]
+
 lemma reverse_rotate (l : list α) (n : ℕ) :
   (l.rotate n).reverse = l.reverse.rotate (l.length - (n % l.length)) :=
 begin

ccad6d50

(first ported)

Changes in mathlib3port

mathlib3

mathlib3port

f2f413b9

bump to nightly-2024-04-26-08

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

ab3b6a0f

Diff

@@ -749,9 +749,9 @@ theorem length_cyclicPermutations_of_ne_nil (l : List α) (h : l ≠ []) :
 #align list.length_cyclic_permutations_of_ne_nil List.length_cyclicPermutations_of_ne_nil
 -/
 
-#print List.nthLe_cyclicPermutations /-
+#print List.get_cyclicPermutations /-
 @[simp]
-theorem nthLe_cyclicPermutations (l : List α) (n : ℕ) (hn : n < length (cyclicPermutations l)) :
+theorem get_cyclicPermutations (l : List α) (n : ℕ) (hn : n < length (cyclicPermutations l)) :
     nthLe (cyclicPermutations l) n hn = l.rotate n :=
   by
   obtain rfl | h := eq_or_ne l []
@@ -759,7 +759,7 @@ theorem nthLe_cyclicPermutations (l : List α) (n : ℕ) (hn : n < length (cycli
   · rw [length_cyclic_permutations_of_ne_nil _ h] at hn
     simp [init_eq_take, cyclic_permutations_of_ne_nil _ h, nth_le_take',
       rotate_eq_drop_append_take hn.le]
-#align list.nth_le_cyclic_permutations List.nthLe_cyclicPermutations
+#align list.nth_le_cyclic_permutations List.get_cyclicPermutations
 -/
 
 #print List.mem_cyclicPermutations_self /-

f2f413b9

bump to nightly-2024-03-17-08

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

22f01ce4

Diff

@@ -228,7 +228,7 @@ theorem prod_rotate_eq_one_of_prod_eq_one [Group α] :
   | a :: l, hl, n =>
     by
     have : n % List.length (a :: l) ≤ List.length (a :: l) := le_of_lt (Nat.mod_lt _ (by decide))
-    rw [← List.take_append_drop (n % List.length (a :: l)) (a :: l)] at hl  <;>
+    rw [← List.take_append_drop (n % List.length (a :: l)) (a :: l)] at hl <;>
       rw [← rotate_mod, rotate_eq_drop_append_take this, List.prod_append, mul_eq_one_iff_inv_eq, ←
         one_mul (List.prod _)⁻¹, ← hl, List.prod_append, mul_assoc, mul_inv_self, mul_one]
 #align list.prod_rotate_eq_one_of_prod_eq_one List.prod_rotate_eq_one_of_prod_eq_one
@@ -490,7 +490,7 @@ theorem Nodup.rotate_eq_self_iff {l : List α} (hl : l.Nodup) {n : ℕ} :
     cases' l.length.zero_le.eq_or_lt with hl' hl'
     · simp [← length_eq_zero, ← hl']
     left
-    rw [nodup_iff_nth_le_inj] at hl 
+    rw [nodup_iff_nth_le_inj] at hl
     refine' hl _ _ (mod_lt _ hl') hl' _
     rw [← nth_le_rotate' _ n]
     simp_rw [h, tsub_add_cancel_of_le (mod_lt _ hl').le, mod_self]
@@ -756,7 +756,7 @@ theorem nthLe_cyclicPermutations (l : List α) (n : ℕ) (hn : n < length (cycli
   by
   obtain rfl | h := eq_or_ne l []
   · simp
-  · rw [length_cyclic_permutations_of_ne_nil _ h] at hn 
+  · rw [length_cyclic_permutations_of_ne_nil _ h] at hn
     simp [init_eq_take, cyclic_permutations_of_ne_nil _ h, nth_le_take',
       rotate_eq_drop_append_take hn.le]
 #align list.nth_le_cyclic_permutations List.nthLe_cyclicPermutations
@@ -827,7 +827,7 @@ theorem Nodup.cyclicPermutations {l : List α} (hn : Nodup l) : Nodup (cyclicPer
   · simp
   rw [nodup_iff_nth_le_inj]
   intro i j hi hj h
-  simp only [length_cyclic_permutations_cons] at hi hj 
+  simp only [length_cyclic_permutations_cons] at hi hj
   rw [← mod_eq_of_lt hi, ← mod_eq_of_lt hj, ← length_cons x l]
   apply hn.rotate_congr
   · simp

f2f413b9

bump to nightly-2023-09-24-06

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

5655435f

Diff

@@ -3,8 +3,8 @@ Copyright (c) 2019 Chris Hughes. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Chris Hughes, Yakov Pechersky
 -/
-import Mathbin.Data.List.Perm
-import Mathbin.Data.List.Range
+import Data.List.Perm
+import Data.List.Range
 
 #align_import data.list.rotate from "leanprover-community/mathlib"@"f2f413b9d4be3a02840d0663dace76e8fe3da053"

f2f413b9

bump to nightly-2023-08-02-01

mathlib commit https://github.com/leanprover-community/mathlib/commit/63721b2c3eba6c325ecf8ae8cca27155a4f6306f

7aca3f15

Diff

@@ -543,7 +543,7 @@ theorem IsRotated.symm (h : l ~r l') : l' ~r l :=
   obtain ⟨n, rfl⟩ := h
   cases' l with hd tl
   · simp
-  · use (hd :: tl).length * n - n
+  · use(hd :: tl).length * n - n
     rw [rotate_rotate, add_tsub_cancel_of_le, rotate_length_mul]
     exact Nat.le_mul_of_pos_left (by simp)
 #align list.is_rotated.symm List.IsRotated.symm

f2f413b9

bump to nightly-2023-07-20-09

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

9c56d0dd

Diff

@@ -2,15 +2,12 @@
 Copyright (c) 2019 Chris Hughes. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Chris Hughes, Yakov Pechersky
-
-! This file was ported from Lean 3 source module data.list.rotate
-! leanprover-community/mathlib commit f2f413b9d4be3a02840d0663dace76e8fe3da053
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Data.List.Perm
 import Mathbin.Data.List.Range
 
+#align_import data.list.rotate from "leanprover-community/mathlib"@"f2f413b9d4be3a02840d0663dace76e8fe3da053"
+
 /-!
 # List rotation

f2f413b9

bump to nightly-2023-06-13-21

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

829520ac

Diff

@@ -224,6 +224,7 @@ theorem rotate_length_mul (l : List α) (n : ℕ) : l.rotate (l.length * n) = l
 #align list.rotate_length_mul List.rotate_length_mul
 -/
 
+#print List.prod_rotate_eq_one_of_prod_eq_one /-
 theorem prod_rotate_eq_one_of_prod_eq_one [Group α] :
     ∀ {l : List α} (hl : l.Prod = 1) (n : ℕ), (l.rotate n).Prod = 1
   | [], _, _ => by simp
@@ -234,6 +235,7 @@ theorem prod_rotate_eq_one_of_prod_eq_one [Group α] :
       rw [← rotate_mod, rotate_eq_drop_append_take this, List.prod_append, mul_eq_one_iff_inv_eq, ←
         one_mul (List.prod _)⁻¹, ← hl, List.prod_append, mul_assoc, mul_inv_self, mul_one]
 #align list.prod_rotate_eq_one_of_prod_eq_one List.prod_rotate_eq_one_of_prod_eq_one
+-/
 
 #print List.rotate_perm /-
 theorem rotate_perm (l : List α) (n : ℕ) : l.rotate n ~ l :=
@@ -281,6 +283,7 @@ theorem rotate_singleton (x : α) (n : ℕ) : [x].rotate n = [x] :=
 #align list.rotate_singleton List.rotate_singleton
 -/
 
+#print List.zipWith_rotate_distrib /-
 theorem zipWith_rotate_distrib {α β γ : Type _} (f : α → β → γ) (l : List α) (l' : List β) (n : ℕ)
     (h : l.length = l'.length) : (zipWith f l l').rotate n = zipWith f (l.rotate n) (l'.rotate n) :=
   by
@@ -289,14 +292,17 @@ theorem zipWith_rotate_distrib {α β γ : Type _} (f : α → β → γ) (l : L
     zip_with_distrib_take, List.length_zipWith, h, min_self]
   rw [length_drop, length_drop, h]
 #align list.zip_with_rotate_distrib List.zipWith_rotate_distrib
+-/
 
 attribute [local simp] rotate_cons_succ
 
+#print List.zipWith_rotate_one /-
 @[simp]
 theorem zipWith_rotate_one {β : Type _} (f : α → α → β) (x y : α) (l : List α) :
     zipWith f (x :: y :: l) ((x :: y :: l).rotate 1) = f x y :: zipWith f (y :: l) (l ++ [x]) := by
   simp
 #align list.zip_with_rotate_one List.zipWith_rotate_one
+-/
 
 #print List.nthLe_rotate_one /-
 theorem nthLe_rotate_one (l : List α) (k : ℕ) (hk : k < (l.rotate 1).length) :
@@ -466,6 +472,7 @@ theorem rotate_reverse (l : List α) (n : ℕ) :
 #align list.rotate_reverse List.rotate_reverse
 -/
 
+#print List.map_rotate /-
 theorem map_rotate {β : Type _} (f : α → β) (l : List α) (n : ℕ) :
     map f (l.rotate n) = (map f l).rotate n :=
   by
@@ -475,6 +482,7 @@ theorem map_rotate {β : Type _} (f : α → β) (l : List α) (n : ℕ) :
     · simp
     · simp [hn]
 #align list.map_rotate List.map_rotate
+-/
 
 #print List.Nodup.rotate_eq_self_iff /-
 theorem Nodup.rotate_eq_self_iff {l : List α} (hl : l.Nodup) {n : ℕ} :
@@ -520,7 +528,6 @@ def IsRotated : Prop :=
 #align list.is_rotated List.IsRotated
 -/
 
--- mathport name: «expr ~r »
 infixr:1000 " ~r " => IsRotated
 
 variable {l l'}
@@ -661,6 +668,7 @@ theorem isRotated_reverse_iff : l.reverse ~r l'.reverse ↔ l ~r l' := by
 #align list.is_rotated_reverse_iff List.isRotated_reverse_iff
 -/
 
+#print List.isRotated_iff_mod /-
 theorem isRotated_iff_mod : l ~r l' ↔ ∃ n ≤ l.length, l.rotate n = l' :=
   by
   refine' ⟨fun h => _, fun ⟨n, _, h⟩ => ⟨n, h⟩⟩
@@ -671,6 +679,7 @@ theorem isRotated_iff_mod : l ~r l' ↔ ∃ n ≤ l.length, l.rotate n = l' :=
     refine' (Nat.mod_lt _ _).le
     simp
 #align list.is_rotated_iff_mod List.isRotated_iff_mod
+-/
 
 #print List.isRotated_iff_mem_map_range /-
 theorem isRotated_iff_mem_map_range : l ~r l' ↔ l' ∈ (List.range (l.length + 1)).map l.rotate :=
@@ -681,6 +690,7 @@ theorem isRotated_iff_mem_map_range : l ~r l' ↔ l' ∈ (List.range (l.length +
 #align list.is_rotated_iff_mem_map_range List.isRotated_iff_mem_map_range
 -/
 
+#print List.IsRotated.map /-
 @[congr]
 theorem IsRotated.map {β : Type _} {l₁ l₂ : List α} (h : l₁ ~r l₂) (f : α → β) :
     map f l₁ ~r map f l₂ := by
@@ -688,6 +698,7 @@ theorem IsRotated.map {β : Type _} {l₁ l₂ : List α} (h : l₁ ~r l₂) (f
   rw [map_rotate]
   use n
 #align list.is_rotated.map List.IsRotated.map
+-/
 
 #print List.cyclicPermutations /-
 /-- List of all cyclic permutations of `l`.

f2f413b9

bump to nightly-2023-06-09-07

mathlib commit https://github.com/leanprover-community/mathlib/commit/7e5137f579de09a059a5ce98f364a04e221aabf0

16afdc39

Diff

@@ -123,7 +123,6 @@ theorem rotate'_length_mul (l : List α) : ∀ n : ℕ, l.rotate' (l.length * n)
           (l.rotate' (l.length * n)).rotate' (l.rotate' (l.length * n)).length :=
         by simp [-rotate'_length, Nat.mul_succ, rotate'_rotate']
       _ = l := by rw [rotate'_length, rotate'_length_mul]
-      
 #align list.rotate'_length_mul List.rotate'_length_mul
 -/
 
@@ -134,7 +133,6 @@ theorem rotate'_mod (l : List α) (n : ℕ) : l.rotate' (n % l.length) = l.rotat
         (l.rotate' (n % l.length)).rotate' ((l.rotate' (n % l.length)).length * (n / l.length)) :=
       by rw [rotate'_length_mul]
     _ = l.rotate' n := by rw [rotate'_rotate', length_rotate', Nat.mod_add_div]
-    
 #align list.rotate'_mod List.rotate'_mod
 -/

f2f413b9

bump to nightly-2023-06-01-16

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

b9c87c70

Diff

@@ -232,7 +232,7 @@ theorem prod_rotate_eq_one_of_prod_eq_one [Group α] :
   | a :: l, hl, n =>
     by
     have : n % List.length (a :: l) ≤ List.length (a :: l) := le_of_lt (Nat.mod_lt _ (by decide))
-    rw [← List.take_append_drop (n % List.length (a :: l)) (a :: l)] at hl <;>
+    rw [← List.take_append_drop (n % List.length (a :: l)) (a :: l)] at hl  <;>
       rw [← rotate_mod, rotate_eq_drop_append_take this, List.prod_append, mul_eq_one_iff_inv_eq, ←
         one_mul (List.prod _)⁻¹, ← hl, List.prod_append, mul_assoc, mul_inv_self, mul_one]
 #align list.prod_rotate_eq_one_of_prod_eq_one List.prod_rotate_eq_one_of_prod_eq_one
@@ -487,7 +487,7 @@ theorem Nodup.rotate_eq_self_iff {l : List α} (hl : l.Nodup) {n : ℕ} :
     cases' l.length.zero_le.eq_or_lt with hl' hl'
     · simp [← length_eq_zero, ← hl']
     left
-    rw [nodup_iff_nth_le_inj] at hl
+    rw [nodup_iff_nth_le_inj] at hl 
     refine' hl _ _ (mod_lt _ hl') hl' _
     rw [← nth_le_rotate' _ n]
     simp_rw [h, tsub_add_cancel_of_le (mod_lt _ hl').le, mod_self]
@@ -750,7 +750,7 @@ theorem nthLe_cyclicPermutations (l : List α) (n : ℕ) (hn : n < length (cycli
   by
   obtain rfl | h := eq_or_ne l []
   · simp
-  · rw [length_cyclic_permutations_of_ne_nil _ h] at hn
+  · rw [length_cyclic_permutations_of_ne_nil _ h] at hn 
     simp [init_eq_take, cyclic_permutations_of_ne_nil _ h, nth_le_take',
       rotate_eq_drop_append_take hn.le]
 #align list.nth_le_cyclic_permutations List.nthLe_cyclicPermutations
@@ -821,7 +821,7 @@ theorem Nodup.cyclicPermutations {l : List α} (hn : Nodup l) : Nodup (cyclicPer
   · simp
   rw [nodup_iff_nth_le_inj]
   intro i j hi hj h
-  simp only [length_cyclic_permutations_cons] at hi hj
+  simp only [length_cyclic_permutations_cons] at hi hj 
   rw [← mod_eq_of_lt hi, ← mod_eq_of_lt hj, ← length_cons x l]
   apply hn.rotate_congr
   · simp

f2f413b9

bump to nightly-2023-05-28-06

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

ba5d8b97

Diff

@@ -226,12 +226,6 @@ theorem rotate_length_mul (l : List α) (n : ℕ) : l.rotate (l.length * n) = l
 #align list.rotate_length_mul List.rotate_length_mul
 -/
 
-/- warning: list.prod_rotate_eq_one_of_prod_eq_one -> List.prod_rotate_eq_one_of_prod_eq_one is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} [_inst_1 : Group.{u1} α] {l : List.{u1} α}, (Eq.{succ u1} α (List.prod.{u1} α (MulOneClass.toHasMul.{u1} α (Monoid.toMulOneClass.{u1} α (DivInvMonoid.toMonoid.{u1} α (Group.toDivInvMonoid.{u1} α _inst_1)))) (MulOneClass.toHasOne.{u1} α (Monoid.toMulOneClass.{u1} α (DivInvMonoid.toMonoid.{u1} α (Group.toDivInvMonoid.{u1} α _inst_1)))) l) (OfNat.ofNat.{u1} α 1 (OfNat.mk.{u1} α 1 (One.one.{u1} α (MulOneClass.toHasOne.{u1} α (Monoid.toMulOneClass.{u1} α (DivInvMonoid.toMonoid.{u1} α (Group.toDivInvMonoid.{u1} α _inst_1)))))))) -> (forall (n : Nat), Eq.{succ u1} α (List.prod.{u1} α (MulOneClass.toHasMul.{u1} α (Monoid.toMulOneClass.{u1} α (DivInvMonoid.toMonoid.{u1} α (Group.toDivInvMonoid.{u1} α _inst_1)))) (MulOneClass.toHasOne.{u1} α (Monoid.toMulOneClass.{u1} α (DivInvMonoid.toMonoid.{u1} α (Group.toDivInvMonoid.{u1} α _inst_1)))) (List.rotate.{u1} α l n)) (OfNat.ofNat.{u1} α 1 (OfNat.mk.{u1} α 1 (One.one.{u1} α (MulOneClass.toHasOne.{u1} α (Monoid.toMulOneClass.{u1} α (DivInvMonoid.toMonoid.{u1} α (Group.toDivInvMonoid.{u1} α _inst_1))))))))
-but is expected to have type
-  forall {α : Type.{u1}} [_inst_1 : Group.{u1} α] {l : List.{u1} α}, (Eq.{succ u1} α (List.prod.{u1} α (MulOneClass.toMul.{u1} α (Monoid.toMulOneClass.{u1} α (DivInvMonoid.toMonoid.{u1} α (Group.toDivInvMonoid.{u1} α _inst_1)))) (InvOneClass.toOne.{u1} α (DivInvOneMonoid.toInvOneClass.{u1} α (DivisionMonoid.toDivInvOneMonoid.{u1} α (Group.toDivisionMonoid.{u1} α _inst_1)))) l) (OfNat.ofNat.{u1} α 1 (One.toOfNat1.{u1} α (InvOneClass.toOne.{u1} α (DivInvOneMonoid.toInvOneClass.{u1} α (DivisionMonoid.toDivInvOneMonoid.{u1} α (Group.toDivisionMonoid.{u1} α _inst_1))))))) -> (forall (n : Nat), Eq.{succ u1} α (List.prod.{u1} α (MulOneClass.toMul.{u1} α (Monoid.toMulOneClass.{u1} α (DivInvMonoid.toMonoid.{u1} α (Group.toDivInvMonoid.{u1} α _inst_1)))) (InvOneClass.toOne.{u1} α (DivInvOneMonoid.toInvOneClass.{u1} α (DivisionMonoid.toDivInvOneMonoid.{u1} α (Group.toDivisionMonoid.{u1} α _inst_1)))) (List.rotate.{u1} α l n)) (OfNat.ofNat.{u1} α 1 (One.toOfNat1.{u1} α (InvOneClass.toOne.{u1} α (DivInvOneMonoid.toInvOneClass.{u1} α (DivisionMonoid.toDivInvOneMonoid.{u1} α (Group.toDivisionMonoid.{u1} α _inst_1)))))))
-Case conversion may be inaccurate. Consider using '#align list.prod_rotate_eq_one_of_prod_eq_one List.prod_rotate_eq_one_of_prod_eq_oneₓ'. -/
 theorem prod_rotate_eq_one_of_prod_eq_one [Group α] :
     ∀ {l : List α} (hl : l.Prod = 1) (n : ℕ), (l.rotate n).Prod = 1
   | [], _, _ => by simp
@@ -289,12 +283,6 @@ theorem rotate_singleton (x : α) (n : ℕ) : [x].rotate n = [x] :=
 #align list.rotate_singleton List.rotate_singleton
 -/
 
-/- warning: list.zip_with_rotate_distrib -> List.zipWith_rotate_distrib is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {β : Type.{u2}} {γ : Type.{u3}} (f : α -> β -> γ) (l : List.{u1} α) (l' : List.{u2} β) (n : Nat), (Eq.{1} Nat (List.length.{u1} α l) (List.length.{u2} β l')) -> (Eq.{succ u3} (List.{u3} γ) (List.rotate.{u3} γ (List.zipWith.{u1, u2, u3} α β γ f l l') n) (List.zipWith.{u1, u2, u3} α β γ f (List.rotate.{u1} α l n) (List.rotate.{u2} β l' n)))
-but is expected to have type
-  forall {α : Type.{u3}} {β : Type.{u2}} {γ : Type.{u1}} (f : α -> β -> γ) (l : List.{u3} α) (l' : List.{u2} β) (n : Nat), (Eq.{1} Nat (List.length.{u3} α l) (List.length.{u2} β l')) -> (Eq.{succ u1} (List.{u1} γ) (List.rotate.{u1} γ (List.zipWith.{u3, u2, u1} α β γ f l l') n) (List.zipWith.{u3, u2, u1} α β γ f (List.rotate.{u3} α l n) (List.rotate.{u2} β l' n)))
-Case conversion may be inaccurate. Consider using '#align list.zip_with_rotate_distrib List.zipWith_rotate_distribₓ'. -/
 theorem zipWith_rotate_distrib {α β γ : Type _} (f : α → β → γ) (l : List α) (l' : List β) (n : ℕ)
     (h : l.length = l'.length) : (zipWith f l l').rotate n = zipWith f (l.rotate n) (l'.rotate n) :=
   by
@@ -306,12 +294,6 @@ theorem zipWith_rotate_distrib {α β γ : Type _} (f : α → β → γ) (l : L
 
 attribute [local simp] rotate_cons_succ
 
-/- warning: list.zip_with_rotate_one -> List.zipWith_rotate_one is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {β : Type.{u2}} (f : α -> α -> β) (x : α) (y : α) (l : List.{u1} α), Eq.{succ u2} (List.{u2} β) (List.zipWith.{u1, u1, u2} α α β f (List.cons.{u1} α x (List.cons.{u1} α y l)) (List.rotate.{u1} α (List.cons.{u1} α x (List.cons.{u1} α y l)) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))))) (List.cons.{u2} β (f x y) (List.zipWith.{u1, u1, u2} α α β f (List.cons.{u1} α y l) (Append.append.{u1} (List.{u1} α) (List.hasAppend.{u1} α) l (List.cons.{u1} α x (List.nil.{u1} α)))))
-but is expected to have type
-  forall {α : Type.{u2}} {β : Type.{u1}} (f : α -> α -> β) (x : α) (y : α) (l : List.{u2} α), Eq.{succ u1} (List.{u1} β) (List.zipWith.{u2, u2, u1} α α β f (List.cons.{u2} α x (List.cons.{u2} α y l)) (List.rotate.{u2} α (List.cons.{u2} α x (List.cons.{u2} α y l)) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)))) (List.cons.{u1} β (f x y) (List.zipWith.{u2, u2, u1} α α β f (List.cons.{u2} α y l) (HAppend.hAppend.{u2, u2, u2} (List.{u2} α) (List.{u2} α) (List.{u2} α) (instHAppend.{u2} (List.{u2} α) (List.instAppendList.{u2} α)) l (List.cons.{u2} α x (List.nil.{u2} α)))))
-Case conversion may be inaccurate. Consider using '#align list.zip_with_rotate_one List.zipWith_rotate_oneₓ'. -/
 @[simp]
 theorem zipWith_rotate_one {β : Type _} (f : α → α → β) (x y : α) (l : List α) :
     zipWith f (x :: y :: l) ((x :: y :: l).rotate 1) = f x y :: zipWith f (y :: l) (l ++ [x]) := by
@@ -486,12 +468,6 @@ theorem rotate_reverse (l : List α) (n : ℕ) :
 #align list.rotate_reverse List.rotate_reverse
 -/
 
-/- warning: list.map_rotate -> List.map_rotate is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {β : Type.{u2}} (f : α -> β) (l : List.{u1} α) (n : Nat), Eq.{succ u2} (List.{u2} β) (List.map.{u1, u2} α β f (List.rotate.{u1} α l n)) (List.rotate.{u2} β (List.map.{u1, u2} α β f l) n)
-but is expected to have type
-  forall {α : Type.{u2}} {β : Type.{u1}} (f : α -> β) (l : List.{u2} α) (n : Nat), Eq.{succ u1} (List.{u1} β) (List.map.{u2, u1} α β f (List.rotate.{u2} α l n)) (List.rotate.{u1} β (List.map.{u2, u1} α β f l) n)
-Case conversion may be inaccurate. Consider using '#align list.map_rotate List.map_rotateₓ'. -/
 theorem map_rotate {β : Type _} (f : α → β) (l : List α) (n : ℕ) :
     map f (l.rotate n) = (map f l).rotate n :=
   by
@@ -687,12 +663,6 @@ theorem isRotated_reverse_iff : l.reverse ~r l'.reverse ↔ l ~r l' := by
 #align list.is_rotated_reverse_iff List.isRotated_reverse_iff
 -/
 
-/- warning: list.is_rotated_iff_mod -> List.isRotated_iff_mod is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {l : List.{u1} α} {l' : List.{u1} α}, Iff (List.IsRotated.{u1} α l l') (Exists.{1} Nat (fun (n : Nat) => Exists.{0} (LE.le.{0} Nat Nat.hasLe n (List.length.{u1} α l)) (fun (H : LE.le.{0} Nat Nat.hasLe n (List.length.{u1} α l)) => Eq.{succ u1} (List.{u1} α) (List.rotate.{u1} α l n) l')))
-but is expected to have type
-  forall {α : Type.{u1}} {l : List.{u1} α} {l' : List.{u1} α}, Iff (List.IsRotated.{u1} α l l') (Exists.{1} Nat (fun (n : Nat) => And (LE.le.{0} Nat instLENat n (List.length.{u1} α l)) (Eq.{succ u1} (List.{u1} α) (List.rotate.{u1} α l n) l')))
-Case conversion may be inaccurate. Consider using '#align list.is_rotated_iff_mod List.isRotated_iff_modₓ'. -/
 theorem isRotated_iff_mod : l ~r l' ↔ ∃ n ≤ l.length, l.rotate n = l' :=
   by
   refine' ⟨fun h => _, fun ⟨n, _, h⟩ => ⟨n, h⟩⟩
@@ -713,12 +683,6 @@ theorem isRotated_iff_mem_map_range : l ~r l' ↔ l' ∈ (List.range (l.length +
 #align list.is_rotated_iff_mem_map_range List.isRotated_iff_mem_map_range
 -/
 
-/- warning: list.is_rotated.map -> List.IsRotated.map is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {β : Type.{u2}} {l₁ : List.{u1} α} {l₂ : List.{u1} α}, (List.IsRotated.{u1} α l₁ l₂) -> (forall (f : α -> β), List.IsRotated.{u2} β (List.map.{u1, u2} α β f l₁) (List.map.{u1, u2} α β f l₂))
-but is expected to have type
-  forall {α : Type.{u2}} {β : Type.{u1}} {l₁ : List.{u2} α} {l₂ : List.{u2} α}, (List.IsRotated.{u2} α l₁ l₂) -> (forall (f : α -> β), List.IsRotated.{u1} β (List.map.{u2, u1} α β f l₁) (List.map.{u2, u1} α β f l₂))
-Case conversion may be inaccurate. Consider using '#align list.is_rotated.map List.IsRotated.mapₓ'. -/
 @[congr]
 theorem IsRotated.map {β : Type _} {l₁ l₂ : List α} (h : l₁ ~r l₂) (f : α → β) :
     map f l₁ ~r map f l₂ := by

f2f413b9

bump to nightly-2023-03-27-02

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

0e4ebd8c

Diff

@@ -171,10 +171,12 @@ theorem length_rotate (l : List α) (n : ℕ) : (l.rotate n).length = l.length :
 #align list.length_rotate List.length_rotate
 -/
 
+#print List.rotate_replicate /-
 theorem rotate_replicate (a : α) (n : ℕ) (k : ℕ) : (replicate n a).rotate k = replicate n a :=
   eq_replicate.2
     ⟨by rw [length_rotate, length_replicate], fun b hb => eq_of_mem_replicate <| mem_rotate.1 hb⟩
 #align list.rotate_replicate List.rotate_replicate
+-/
 
 #print List.rotate_eq_drop_append_take /-
 theorem rotate_eq_drop_append_take {l : List α} {n : ℕ} :
@@ -364,17 +366,22 @@ theorem nthLe_rotate' (l : List α) (n k : ℕ) (hk : k < l.length) :
 #align list.nth_le_rotate' List.nthLe_rotate'
 -/
 
+#print List.get?_rotate /-
 theorem get?_rotate {l : List α} {n m : ℕ} (hml : m < l.length) :
     (l.rotate n).get? m = l.get? ((m + n) % l.length) :=
   by
   rw [nth_le_nth, nth_le_nth (Nat.mod_lt _ _), nth_le_rotate]
   rwa [length_rotate]
 #align list.nth_rotate List.get?_rotate
+-/
 
+#print List.head?_rotate /-
 theorem head?_rotate {l : List α} {n : ℕ} (h : n < l.length) : head? (l.rotate n) = l.get? n := by
   rw [← nth_zero, nth_rotate (n.zero_le.trans_lt h), zero_add, Nat.mod_eq_of_lt h]
 #align list.head'_rotate List.head?_rotate
+-/
 
+#print List.rotate_eq_self_iff_eq_replicate /-
 theorem rotate_eq_self_iff_eq_replicate [hα : Nonempty α] :
     ∀ {l : List α}, (∀ n, l.rotate n = l) ↔ ∃ a, l = replicate l.length a
   | [] => by simp
@@ -387,7 +394,9 @@ theorem rotate_eq_self_iff_eq_replicate [hα : Nonempty α] :
           rw [nth_le_replicate, ← Option.some_inj, ← nth_le_nth, ← head'_rotate h₁, h, head']⟩,
       fun ⟨b, hb⟩ n => by rw [hb, rotate_replicate]⟩
 #align list.rotate_eq_self_iff_eq_replicate List.rotate_eq_self_iff_eq_replicate
+-/
 
+#print List.rotate_one_eq_self_iff_eq_replicate /-
 theorem rotate_one_eq_self_iff_eq_replicate [Nonempty α] {l : List α} :
     l.rotate 1 = l ↔ ∃ a : α, l = List.replicate l.length a :=
   ⟨fun h =>
@@ -395,6 +404,7 @@ theorem rotate_one_eq_self_iff_eq_replicate [Nonempty α] {l : List α} :
       Nat.rec l.rotate_zero (fun n hn => by rwa [Nat.succ_eq_add_one, ← l.rotate_rotate, hn]) n,
     fun h => rotate_eq_self_iff_eq_replicate.mpr h 1⟩
 #align list.rotate_one_eq_self_iff_eq_replicate List.rotate_one_eq_self_iff_eq_replicate
+-/
 
 #print List.rotate_injective /-
 theorem rotate_injective (n : ℕ) : Function.Injective fun l : List α => l.rotate n :=

f2f413b9

bump to nightly-2023-02-21-16

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

1107b979

Changes in mathlib4

mathlib3

mathlib4

f694c7de

feat(List): add lemmas about Sublist (#12326)

Move tail_sublist to Basic
Rename sublist_of_cons_sublist_cons to Sublist.of_cons_cos
Rename cons_sublist_cons_iff to cons_sublist_cons
Add Sublist.tail, drop_sublist_drop_left, Sublist.drop
Protect some lemmas

add5ed22

Diff

@@ -6,6 +6,7 @@ Authors: Chris Hughes, Yakov Pechersky
 import Mathlib.Data.List.Nodup
 import Mathlib.Data.List.Zip
 import Mathlib.Data.Nat.Defs
+import Mathlib.Data.List.Infix
 
 #align_import data.list.rotate from "leanprover-community/mathlib"@"f694c7dead66f5d4c80f446c796a5aad14707f0e"

f694c7de

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

Most of them go back to the port.

9150835a

Diff

@@ -258,7 +258,7 @@ theorem head?_rotate {l : List α} {n : ℕ} (h : n < l.length) : head? (l.rotat
 -- Porting note: moved down from its original location below `get_rotate` so that the
 -- non-deprecated lemma does not use the deprecated version
 set_option linter.deprecated false in
-@[deprecated get_rotate]
+@[deprecated get_rotate] -- 2023-01-13
 theorem nthLe_rotate (l : List α) (n k : ℕ) (hk : k < (l.rotate n).length) :
     (l.rotate n).nthLe k hk =
       l.nthLe ((k + n) % l.length) (mod_lt _ (length_rotate l n ▸ k.zero_le.trans_lt hk)) :=

f694c7de

feat(List/rotate): migrate to get, new lemmas, golf (#12171)

Add List.Nodup.rotate_congr_iff, List.cyclicPermutations_ne_nil, List.head?_cyclicPermutations, List.head_cyclicPermutations, List.cyclicPermutations_injective, List.cyclicPermutations_inj.
Change List.nthLe_cyclicPermutations to List.get_cyclicPermutations. While the old lemma wasn't deprecated during port, the definition List.nthLe was, so I think that we can drop the lemma without a deprecation period.

7aace659

Diff

@@ -381,34 +381,26 @@ theorem map_rotate {β : Type*} (f : α → β) (l : List α) (n : ℕ) :
     · simp [hn]
 #align list.map_rotate List.map_rotate
 
-set_option linter.deprecated false in
-theorem Nodup.rotate_eq_self_iff {l : List α} (hl : l.Nodup) {n : ℕ} :
-    l.rotate n = l ↔ n % l.length = 0 ∨ l = [] := by
-  constructor
-  · intro h
-    rcases l.length.zero_le.eq_or_lt with hl' | hl'
-    · simp [← length_eq_zero, ← hl']
-    left
-    rw [nodup_iff_nthLe_inj] at hl
-    refine' hl _ _ (mod_lt _ hl') hl' _
-    rw [← nthLe_rotate' _ n]
-    simp_rw [h, Nat.sub_add_cancel (mod_lt _ hl').le, mod_self]
-  · rintro (h | h)
-    · rw [← rotate_mod, h]
-      exact rotate_zero l
-    · simp [h]
-#align list.nodup.rotate_eq_self_iff List.Nodup.rotate_eq_self_iff
-
-set_option linter.deprecated false in
 theorem Nodup.rotate_congr {l : List α} (hl : l.Nodup) (hn : l ≠ []) (i j : ℕ)
     (h : l.rotate i = l.rotate j) : i % l.length = j % l.length := by
-  have hi : i % l.length < l.length := mod_lt _ (length_pos_of_ne_nil hn)
-  have hj : j % l.length < l.length := mod_lt _ (length_pos_of_ne_nil hn)
-  refine' (nodup_iff_nthLe_inj.mp hl) _ _ hi hj _
-  rw [← nthLe_rotate' l i, ← nthLe_rotate' l j]
-  simp [Nat.sub_add_cancel, hi.le, hj.le, h]
+  rw [← rotate_mod l i, ← rotate_mod l j] at h
+  simpa only [head?_rotate, mod_lt, length_pos_of_ne_nil hn, get?_eq_get, Option.some_inj,
+    hl.get_inj_iff, Fin.ext_iff] using congr_arg head? h
 #align list.nodup.rotate_congr List.Nodup.rotate_congr
 
+theorem Nodup.rotate_congr_iff {l : List α} (hl : l.Nodup) {i j : ℕ} :
+    l.rotate i = l.rotate j ↔ i % l.length = j % l.length ∨ l = [] := by
+  rcases eq_or_ne l [] with rfl | hn
+  · simp
+  · simp only [hn, or_false]
+    refine ⟨hl.rotate_congr hn _ _, fun h ↦ ?_⟩
+    rw [← rotate_mod, h, rotate_mod]
+
+theorem Nodup.rotate_eq_self_iff {l : List α} (hl : l.Nodup) {n : ℕ} :
+    l.rotate n = l ↔ n % l.length = 0 ∨ l = [] := by
+  rw [← zero_mod, ← hl.rotate_congr_iff, rotate_zero]
+#align list.nodup.rotate_eq_self_iff List.Nodup.rotate_eq_self_iff
+
 section IsRotated
 
 variable (l l' : List α)
@@ -548,7 +540,7 @@ theorem IsRotated.map {β : Type*} {l₁ l₂ : List α} (h : l₁ ~r l₂) (f :
 /-- List of all cyclic permutations of `l`.
 The `cyclicPermutations` of a nonempty list `l` will always contain `List.length l` elements.
 This implies that under certain conditions, there are duplicates in `List.cyclicPermutations l`.
-The `n`th entry is equal to `l.rotate n`, proven in `List.nthLe_cyclicPermutations`.
+The `n`th entry is equal to `l.rotate n`, proven in `List.get_cyclicPermutations`.
 The proof that every cyclic permutant of `l` is in the list is `List.mem_cyclicPermutations_iff`.
 
      cyclicPermutations [1, 2, 3, 2, 4] =
@@ -584,109 +576,103 @@ theorem length_cyclicPermutations_of_ne_nil (l : List α) (h : l ≠ []) :
     length (cyclicPermutations l) = length l := by simp [cyclicPermutations_of_ne_nil _ h]
 #align list.length_cyclic_permutations_of_ne_nil List.length_cyclicPermutations_of_ne_nil
 
-set_option linter.deprecated false in
 @[simp]
-theorem nthLe_cyclicPermutations (l : List α) (n : ℕ) (hn : n < length (cyclicPermutations l)) :
-    nthLe (cyclicPermutations l) n hn = l.rotate n := by
-  obtain rfl | h := eq_or_ne l []
-  · simp
-  · rw [length_cyclicPermutations_of_ne_nil _ h] at hn
-    simp [dropLast_eq_take, cyclicPermutations_of_ne_nil _ h, nthLe_take',
-      rotate_eq_drop_append_take hn.le]
-#align list.nth_le_cyclic_permutations List.nthLe_cyclicPermutations
+theorem cyclicPermutations_ne_nil : ∀ l : List α, cyclicPermutations l ≠ []
+  | a::l, h => by simpa using congr_arg length h
 
-set_option linter.deprecated false in
-theorem mem_cyclicPermutations_self (l : List α) : l ∈ cyclicPermutations l := by
-  cases' l with x l
-  · simp
-  · rw [mem_iff_nthLe]
-    refine' ⟨0, by simp, _⟩
-    simp
-#align list.mem_cyclic_permutations_self List.mem_cyclicPermutations_self
+@[simp]
+theorem get_cyclicPermutations (l : List α) (n : Fin (length (cyclicPermutations l))) :
+    (cyclicPermutations l).get n = l.rotate n := by
+  cases l with
+  | nil => simp
+  | cons a l =>
+    simp only [cyclicPermutations_cons, get_dropLast, get_zipWith, get_tails, get_inits]
+    rw [rotate_eq_drop_append_take (by simpa using n.2.le)]
+#align list.nth_le_cyclic_permutations List.get_cyclicPermutations
+
+@[simp]
+theorem head?_cyclicPermutations (l : List α) : (cyclicPermutations l).head? = l := by
+  have h : 0 < length (cyclicPermutations l) := length_pos_of_ne_nil (cyclicPermutations_ne_nil _)
+  simp_rw [← get_zero h, get_cyclicPermutations, rotate_zero]
+
+@[simp]
+theorem head_cyclicPermutations (l : List α) :
+    (cyclicPermutations l).head (cyclicPermutations_ne_nil l) = l := by
+  rw [← Option.some_inj, ← head?_eq_head, head?_cyclicPermutations]
+
+theorem cyclicPermutations_injective : Function.Injective (@cyclicPermutations α) := fun l l' h ↦ by
+  simpa using congr_arg head? h
+
+@[simp]
+theorem cyclicPermutations_inj {l l' : List α} :
+    cyclicPermutations l = cyclicPermutations l' ↔ l = l' :=
+  cyclicPermutations_injective.eq_iff
 
-set_option linter.deprecated false in
 theorem length_mem_cyclicPermutations (l : List α) (h : l' ∈ cyclicPermutations l) :
     length l' = length l := by
-  obtain ⟨k, hk, rfl⟩ := nthLe_of_mem h
+  obtain ⟨k, hk, rfl⟩ := get_of_mem h
   simp
 #align list.length_mem_cyclic_permutations List.length_mem_cyclicPermutations
 
-set_option linter.deprecated false in
+theorem mem_cyclicPermutations_self (l : List α) : l ∈ cyclicPermutations l := by
+  simpa using head_mem (cyclicPermutations_ne_nil l)
+#align list.mem_cyclic_permutations_self List.mem_cyclicPermutations_self
+
 @[simp]
-theorem mem_cyclicPermutations_iff {l l' : List α} : l ∈ cyclicPermutations l' ↔ l ~r l' := by
-  constructor
-  · intro h
-    obtain ⟨k, hk, rfl⟩ := nthLe_of_mem h
-    simp
-  · intro h
-    obtain ⟨k, rfl⟩ := h.symm
-    rw [mem_iff_nthLe]
-    simp only [exists_prop, nthLe_cyclicPermutations]
-    cases' l' with x l
+theorem cyclicPermutations_rotate (l : List α) (k : ℕ) :
+    (l.rotate k).cyclicPermutations = l.cyclicPermutations.rotate k := by
+  have : (l.rotate k).cyclicPermutations.length = length (l.cyclicPermutations.rotate k) := by
+    cases l
     · simp
-    · refine' ⟨k % length (x :: l), _, rotate_mod _ _⟩
-      simpa using Nat.mod_lt _ (zero_lt_succ _)
+    · rw [length_cyclicPermutations_of_ne_nil] <;> simp
+  refine' ext_get this fun n hn hn' => _
+  rw [get_rotate, get_cyclicPermutations, rotate_rotate, ← rotate_mod, Nat.add_comm]
+  cases l <;> simp
+#align list.cyclic_permutations_rotate List.cyclicPermutations_rotate
+
+@[simp]
+theorem mem_cyclicPermutations_iff : l ∈ cyclicPermutations l' ↔ l ~r l' := by
+  constructor
+  · simp_rw [mem_iff_get, get_cyclicPermutations]
+    rintro ⟨k, rfl⟩
+    exact .forall _ _
+  · rintro ⟨k, rfl⟩
+    rw [cyclicPermutations_rotate, mem_rotate]
+    apply mem_cyclicPermutations_self
 #align list.mem_cyclic_permutations_iff List.mem_cyclicPermutations_iff
 
 @[simp]
-theorem cyclicPermutations_eq_nil_iff {l : List α} : cyclicPermutations l = [[]] ↔ l = [] := by
-  refine' ⟨fun h => _, fun h => by simp [h]⟩
-  rw [eq_comm, ← isRotated_nil_iff', ← mem_cyclicPermutations_iff, h, mem_singleton]
+theorem cyclicPermutations_eq_nil_iff {l : List α} : cyclicPermutations l = [[]] ↔ l = [] :=
+  cyclicPermutations_injective.eq_iff' rfl
 #align list.cyclic_permutations_eq_nil_iff List.cyclicPermutations_eq_nil_iff
 
 @[simp]
 theorem cyclicPermutations_eq_singleton_iff {l : List α} {x : α} :
-    cyclicPermutations l = [[x]] ↔ l = [x] := by
-  refine' ⟨fun h => _, fun h => by simp [cyclicPermutations, h, dropLast_eq_take]⟩
-  rw [eq_comm, ← isRotated_singleton_iff', ← mem_cyclicPermutations_iff, h, mem_singleton]
+    cyclicPermutations l = [[x]] ↔ l = [x] :=
+  cyclicPermutations_injective.eq_iff' rfl
 #align list.cyclic_permutations_eq_singleton_iff List.cyclicPermutations_eq_singleton_iff
 
-set_option linter.deprecated false in
 /-- If a `l : List α` is `Nodup l`, then all of its cyclic permutants are distinct. -/
-theorem Nodup.cyclicPermutations {l : List α} (hn : Nodup l) : Nodup (cyclicPermutations l) := by
-  cases' l with x l
-  · simp
-  rw [nodup_iff_nthLe_inj]
-  intro i j hi hj h
-  simp only [length_cyclicPermutations_cons] at hi hj
-  rw [← mod_eq_of_lt hi, ← mod_eq_of_lt hj]
-  apply hn.rotate_congr
+protected theorem Nodup.cyclicPermutations {l : List α} (hn : Nodup l) :
+    Nodup (cyclicPermutations l) := by
+  rcases eq_or_ne l [] with rfl | hl
   · simp
-  · simpa using h
+  · rw [nodup_iff_injective_get]
+    rintro ⟨i, hi⟩ ⟨j, hj⟩ h
+    simp only [length_cyclicPermutations_of_ne_nil l hl] at hi hj
+    simpa [hn.rotate_congr_iff, mod_eq_of_lt, *] using h
 #align list.nodup.cyclic_permutations List.Nodup.cyclicPermutations
 
-set_option linter.deprecated false in
-@[simp]
-theorem cyclicPermutations_rotate (l : List α) (k : ℕ) :
-    (l.rotate k).cyclicPermutations = l.cyclicPermutations.rotate k := by
-  have : (l.rotate k).cyclicPermutations.length = length (l.cyclicPermutations.rotate k) := by
-    cases l
-    · simp
-    · rw [length_cyclicPermutations_of_ne_nil] <;> simp
-  refine' ext_nthLe this fun n hn hn' => _
-  rw [nthLe_rotate, nthLe_cyclicPermutations, rotate_rotate, ← rotate_mod, Nat.add_comm]
-  cases l <;> simp
-#align list.cyclic_permutations_rotate List.cyclicPermutations_rotate
-
-theorem IsRotated.cyclicPermutations {l l' : List α} (h : l ~r l') :
+protected theorem IsRotated.cyclicPermutations {l l' : List α} (h : l ~r l') :
     l.cyclicPermutations ~r l'.cyclicPermutations := by
   obtain ⟨k, rfl⟩ := h
   exact ⟨k, by simp⟩
 #align list.is_rotated.cyclic_permutations List.IsRotated.cyclicPermutations
 
-set_option linter.deprecated false in
 @[simp]
 theorem isRotated_cyclicPermutations_iff {l l' : List α} :
     l.cyclicPermutations ~r l'.cyclicPermutations ↔ l ~r l' := by
-  by_cases hl : l = []
-  · simp [hl, eq_comm]
-  have hl' : l.cyclicPermutations.length = l.length := length_cyclicPermutations_of_ne_nil _ hl
-  refine' ⟨fun h => _, IsRotated.cyclicPermutations⟩
-  obtain ⟨k, hk⟩ := h
-  refine' ⟨k % l.length, _⟩
-  have hk' : k % l.length < l.length := mod_lt _ (length_pos_of_ne_nil hl)
-  rw [← nthLe_cyclicPermutations _ _ (hk'.trans_le hl'.ge), ← nthLe_rotate' _ k]
-  simp [hk, hl', Nat.sub_add_cancel hk'.le]
+  simp only [IsRotated, ← cyclicPermutations_rotate, cyclicPermutations_inj]
 #align list.is_rotated_cyclic_permutations_iff List.isRotated_cyclicPermutations_iff
 
 section Decidable

f694c7de

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

@@ -5,6 +5,7 @@ Authors: Chris Hughes, Yakov Pechersky
 -/
 import Mathlib.Data.List.Nodup
 import Mathlib.Data.List.Zip
+import Mathlib.Data.Nat.Defs
 
 #align_import data.list.rotate from "leanprover-community/mathlib"@"f694c7dead66f5d4c80f446c796a5aad14707f0e"
 
@@ -78,7 +79,7 @@ theorem rotate'_rotate' : ∀ (l : List α) (n m : ℕ), (l.rotate' n).rotate' m
   | a :: l, 0, m => by simp
   | [], n, m => by simp
   | a :: l, n + 1, m => by
-    rw [rotate'_cons_succ, rotate'_rotate' _ n, add_right_comm, ← rotate'_cons_succ]
+    rw [rotate'_cons_succ, rotate'_rotate' _ n, Nat.add_right_comm, ← rotate'_cons_succ]
 #align list.rotate'_rotate' List.rotate'_rotate'
 
 @[simp]
@@ -170,16 +171,6 @@ theorem rotate_length_mul (l : List α) (n : ℕ) : l.rotate (l.length * n) = l
   rw [rotate_eq_rotate', rotate'_length_mul]
 #align list.rotate_length_mul List.rotate_length_mul
 
-theorem prod_rotate_eq_one_of_prod_eq_one [Group α] :
-    ∀ {l : List α} (_ : l.prod = 1) (n : ℕ), (l.rotate n).prod = 1
-  | [], _, _ => by simp
-  | a :: l, hl, n => by
-    have : n % List.length (a :: l) ≤ List.length (a :: l) := le_of_lt (Nat.mod_lt _ (by simp))
-    rw [← List.take_append_drop (n % List.length (a :: l)) (a :: l)] at hl;
-      rw [← rotate_mod, rotate_eq_drop_append_take this, List.prod_append, mul_eq_one_iff_inv_eq, ←
-        one_mul (List.prod _)⁻¹, ← hl, List.prod_append, mul_assoc, mul_inv_self, mul_one]
-#align list.prod_rotate_eq_one_of_prod_eq_one List.prod_rotate_eq_one_of_prod_eq_one
-
 theorem rotate_perm (l : List α) (n : ℕ) : l.rotate n ~ l := by
   rw [rotate_eq_rotate']
   induction' n with n hn generalizing l
@@ -235,22 +226,22 @@ theorem get?_rotate {l : List α} {n m : ℕ} (hml : m < l.length) :
     (l.rotate n).get? m = l.get? ((m + n) % l.length) := by
   rw [rotate_eq_drop_append_take_mod]
   rcases lt_or_le m (l.drop (n % l.length)).length with hm | hm
-  · rw [get?_append hm, get?_drop, add_comm m, ← mod_add_mod]
-    rw [length_drop, lt_tsub_iff_left] at hm
-    rw [mod_eq_of_lt hm]
+  · rw [get?_append hm, get?_drop, ← add_mod_mod]
+    rw [length_drop, Nat.lt_sub_iff_add_lt] at hm
+    rw [mod_eq_of_lt hm, Nat.add_comm]
   · have hlt : n % length l < length l := mod_lt _ (m.zero_le.trans_lt hml)
     rw [get?_append_right hm, get?_take, length_drop]
     · congr 1
       rw [length_drop] at hm
-      have hm' := tsub_le_iff_left.1 hm
+      have hm' := Nat.sub_le_iff_le_add'.1 hm
       have : n % length l + m - length l < length l := by
-        rw [tsub_lt_iff_left hm']
+        rw [Nat.sub_lt_iff_lt_add' hm']
         exact Nat.add_lt_add hlt hml
-      conv_rhs => rw [add_comm m, ← mod_add_mod, mod_eq_sub_mod hm', mod_eq_of_lt this]
-      rw [← add_right_inj l.length, ← add_tsub_assoc_of_le (α := ℕ), add_tsub_tsub_cancel (α := ℕ),
-        add_tsub_cancel_of_le (α := ℕ), add_comm]
+      conv_rhs => rw [Nat.add_comm m, ← mod_add_mod, mod_eq_sub_mod hm', mod_eq_of_lt this]
+      rw [← Nat.add_right_inj, ← Nat.add_sub_assoc, Nat.add_sub_sub_cancel, Nat.add_sub_cancel',
+        Nat.add_comm]
       exacts [hm', hlt.le, hm]
-    · rwa [tsub_lt_iff_left hm, length_drop, tsub_add_cancel_of_le hlt.le]
+    · rwa [Nat.sub_lt_iff_lt_add hm, length_drop, Nat.sub_add_cancel hlt.le]
 #align list.nth_rotate List.get?_rotate
 
 -- Porting note (#10756): new lemma
@@ -261,7 +252,7 @@ theorem get_rotate (l : List α) (n : ℕ) (k : Fin (l.rotate n).length) :
   exact k.2.trans_eq (length_rotate _ _)
 
 theorem head?_rotate {l : List α} {n : ℕ} (h : n < l.length) : head? (l.rotate n) = l.get? n := by
-  rw [← get?_zero, get?_rotate (n.zero_le.trans_lt h), zero_add, Nat.mod_eq_of_lt h]
+  rw [← get?_zero, get?_rotate (n.zero_le.trans_lt h), Nat.zero_add, Nat.mod_eq_of_lt h]
 #align list.head'_rotate List.head?_rotate
 
 -- Porting note: moved down from its original location below `get_rotate` so that the
@@ -291,7 +282,7 @@ theorem get_eq_get_rotate (l : List α) (n : ℕ) (k : Fin l.length) :
   rw [get_rotate]
   refine congr_arg l.get (Fin.eq_of_val_eq ?_)
   simp only [mod_add_mod]
-  rw [← add_mod_mod, add_right_comm, tsub_add_cancel_of_le (α := ℕ), add_mod_left, mod_eq_of_lt]
+  rw [← add_mod_mod, Nat.add_right_comm, Nat.sub_add_cancel, add_mod_left, mod_eq_of_lt]
   exacts [k.2, (mod_lt _ (k.1.zero_le.trans_lt k.2)).le]
 
 set_option linter.deprecated false in
@@ -340,7 +331,7 @@ theorem rotate_eq_iff {l l' : List α} {n : ℕ} :
   · rw [eq_nil_of_length_eq_zero hl.symm, rotate_nil]
   · rcases (Nat.zero_le (n % l'.length)).eq_or_lt with hn | hn
     · simp [← hn]
-    · rw [mod_eq_of_lt (tsub_lt_self hl hn), tsub_add_cancel_of_le (α := ℕ), mod_self, rotate_zero]
+    · rw [mod_eq_of_lt (Nat.sub_lt hl hn), Nat.sub_add_cancel, mod_self, rotate_zero]
       exact (Nat.mod_lt _ hl).le
 #align list.rotate_eq_iff List.rotate_eq_iff
 
@@ -376,9 +367,9 @@ theorem rotate_reverse (l : List α) (n : ℕ) :
   · simp_all! [k, length_reverse, ← rotate_rotate]
   · cases' l with x l
     · simp
-    · rw [Nat.mod_eq_of_lt, tsub_add_cancel_of_le (α := ℕ), rotate_length]
-      · exact tsub_le_self
-      · exact tsub_lt_self (by simp) (by simp_all! [k])
+    · rw [Nat.mod_eq_of_lt, Nat.sub_add_cancel, rotate_length]
+      · exact Nat.sub_le _ _
+      · exact Nat.sub_lt (by simp) (by simp_all! [k])
 #align list.rotate_reverse List.rotate_reverse
 
 theorem map_rotate {β : Type*} (f : α → β) (l : List α) (n : ℕ) :
@@ -401,7 +392,7 @@ theorem Nodup.rotate_eq_self_iff {l : List α} (hl : l.Nodup) {n : ℕ} :
     rw [nodup_iff_nthLe_inj] at hl
     refine' hl _ _ (mod_lt _ hl') hl' _
     rw [← nthLe_rotate' _ n]
-    simp_rw [h, tsub_add_cancel_of_le (mod_lt _ hl').le, mod_self]
+    simp_rw [h, Nat.sub_add_cancel (mod_lt _ hl').le, mod_self]
   · rintro (h | h)
     · rw [← rotate_mod, h]
       exact rotate_zero l
@@ -415,7 +406,7 @@ theorem Nodup.rotate_congr {l : List α} (hl : l.Nodup) (hn : l ≠ []) (i j : 
   have hj : j % l.length < l.length := mod_lt _ (length_pos_of_ne_nil hn)
   refine' (nodup_iff_nthLe_inj.mp hl) _ _ hi hj _
   rw [← nthLe_rotate' l i, ← nthLe_rotate' l j]
-  simp [tsub_add_cancel_of_le, hi.le, hj.le, h]
+  simp [Nat.sub_add_cancel, hi.le, hj.le, h]
 #align list.nodup.rotate_congr List.Nodup.rotate_congr
 
 section IsRotated
@@ -444,7 +435,7 @@ theorem IsRotated.symm (h : l ~r l') : l' ~r l := by
   cases' l with hd tl
   · exists 0
   · use (hd :: tl).length * n - n
-    rw [rotate_rotate, add_tsub_cancel_of_le (α := ℕ), rotate_length_mul]
+    rw [rotate_rotate, Nat.add_sub_cancel', rotate_length_mul]
     exact Nat.le_mul_of_pos_left _ (by simp)
 #align list.is_rotated.symm List.IsRotated.symm
 
@@ -673,7 +664,7 @@ theorem cyclicPermutations_rotate (l : List α) (k : ℕ) :
     · simp
     · rw [length_cyclicPermutations_of_ne_nil] <;> simp
   refine' ext_nthLe this fun n hn hn' => _
-  rw [nthLe_rotate, nthLe_cyclicPermutations, rotate_rotate, ← rotate_mod, add_comm]
+  rw [nthLe_rotate, nthLe_cyclicPermutations, rotate_rotate, ← rotate_mod, Nat.add_comm]
   cases l <;> simp
 #align list.cyclic_permutations_rotate List.cyclicPermutations_rotate
 
@@ -695,7 +686,7 @@ theorem isRotated_cyclicPermutations_iff {l l' : List α} :
   refine' ⟨k % l.length, _⟩
   have hk' : k % l.length < l.length := mod_lt _ (length_pos_of_ne_nil hl)
   rw [← nthLe_cyclicPermutations _ _ (hk'.trans_le hl'.ge), ← nthLe_rotate' _ k]
-  simp [hk, hl', tsub_add_cancel_of_le hk'.le]
+  simp [hk, hl', Nat.sub_add_cancel hk'.le]
 #align list.is_rotated_cyclic_permutations_iff List.isRotated_cyclicPermutations_iff
 
 section Decidable

f694c7de

chore: classify new lemma porting notes (#11217)

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

"new lemma"
"added lemma"

68df7d0d

Diff

@@ -253,7 +253,7 @@ theorem get?_rotate {l : List α} {n m : ℕ} (hml : m < l.length) :
     · rwa [tsub_lt_iff_left hm, length_drop, tsub_add_cancel_of_le hlt.le]
 #align list.nth_rotate List.get?_rotate
 
--- Porting note: new lemma
+-- Porting note (#10756): new lemma
 theorem get_rotate (l : List α) (n : ℕ) (k : Fin (l.rotate n).length) :
     (l.rotate n).get k =
       l.get ⟨(k + n) % l.length, mod_lt _ (length_rotate l n ▸ k.1.zero_le.trans_lt k.2)⟩ := by
@@ -281,7 +281,7 @@ theorem nthLe_rotate_one (l : List α) (k : ℕ) (hk : k < (l.rotate 1).length)
   nthLe_rotate l 1 k hk
 #align list.nth_le_rotate_one List.nthLe_rotate_one
 
--- Porting note: new lemma
+-- Porting note (#10756): new lemma
 /-- A version of `List.get_rotate` that represents `List.get l` in terms of
 `List.get (List.rotate l n)`, not vice versa. Can be used instead of rewriting `List.get_rotate`
 from right to left. -/

f694c7de

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

@@ -43,7 +43,7 @@ theorem rotate_nil (n : ℕ) : ([] : List α).rotate n = [] := by simp [rotate]
 theorem rotate_zero (l : List α) : l.rotate 0 = l := by simp [rotate]
 #align list.rotate_zero List.rotate_zero
 
---Porting note: removing simp, simp can prove it
+-- Porting note: removing simp, simp can prove it
 theorem rotate'_nil (n : ℕ) : ([] : List α).rotate' n = [] := by cases n <;> rfl
 #align list.rotate'_nil List.rotate'_nil
 
@@ -225,7 +225,7 @@ theorem zipWith_rotate_distrib {α β γ : Type*} (f : α → β → γ) (l : Li
 
 attribute [local simp] rotate_cons_succ
 
---Porting note: removing @[simp], simp can prove it
+-- Porting note: removing @[simp], simp can prove it
 theorem zipWith_rotate_one {β : Type*} (f : α → α → β) (x y : α) (l : List α) :
     zipWith f (x :: y :: l) ((x :: y :: l).rotate 1) = f x y :: zipWith f (y :: l) (l ++ [x]) := by
   simp
@@ -253,7 +253,7 @@ theorem get?_rotate {l : List α} {n m : ℕ} (hml : m < l.length) :
     · rwa [tsub_lt_iff_left hm, length_drop, tsub_add_cancel_of_le hlt.le]
 #align list.nth_rotate List.get?_rotate
 
--- porting note: new lemma
+-- Porting note: new lemma
 theorem get_rotate (l : List α) (n : ℕ) (k : Fin (l.rotate n).length) :
     (l.rotate n).get k =
       l.get ⟨(k + n) % l.length, mod_lt _ (length_rotate l n ▸ k.1.zero_le.trans_lt k.2)⟩ := by
@@ -264,7 +264,7 @@ theorem head?_rotate {l : List α} {n : ℕ} (h : n < l.length) : head? (l.rotat
   rw [← get?_zero, get?_rotate (n.zero_le.trans_lt h), zero_add, Nat.mod_eq_of_lt h]
 #align list.head'_rotate List.head?_rotate
 
--- porting note: moved down from its original location below `get_rotate` so that the
+-- Porting note: moved down from its original location below `get_rotate` so that the
 -- non-deprecated lemma does not use the deprecated version
 set_option linter.deprecated false in
 @[deprecated get_rotate]
@@ -281,7 +281,7 @@ theorem nthLe_rotate_one (l : List α) (k : ℕ) (hk : k < (l.rotate 1).length)
   nthLe_rotate l 1 k hk
 #align list.nth_le_rotate_one List.nthLe_rotate_one
 
--- porting note: new lemma
+-- Porting note: new lemma
 /-- A version of `List.get_rotate` that represents `List.get l` in terms of
 `List.get (List.rotate l n)`, not vice versa. Can be used instead of rewriting `List.get_rotate`
 from right to left. -/

f694c7de

chore: prepare Lean version bump with explicit simp (#10999)

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

38bce757

Diff

@@ -373,12 +373,12 @@ theorem rotate_reverse (l : List α) (n : ℕ) :
   rw [← length_reverse l]
   let k := n % l.reverse.length
   cases' hk' : k with k'
-  · simp_all! [length_reverse, ← rotate_rotate]
+  · simp_all! [k, length_reverse, ← rotate_rotate]
   · cases' l with x l
     · simp
     · rw [Nat.mod_eq_of_lt, tsub_add_cancel_of_le (α := ℕ), rotate_length]
       · exact tsub_le_self
-      · exact tsub_lt_self (by simp) (by simp_all!)
+      · exact tsub_lt_self (by simp) (by simp_all! [k])
 #align list.rotate_reverse List.rotate_reverse
 
 theorem map_rotate {β : Type*} (f : α → β) (l : List α) (n : ℕ) :

f694c7de

chore: Remove unnecessary "rw"s (#10704)

Remove unnecessary "rw"s.

db5a9376

Diff

@@ -337,7 +337,7 @@ theorem rotate_eq_iff {l l' : List α} {n : ℕ} :
     l.rotate n = l' ↔ l = l'.rotate (l'.length - n % l'.length) := by
   rw [← @rotate_eq_rotate _ l _ n, rotate_rotate, ← rotate_mod l', add_mod]
   rcases l'.length.zero_le.eq_or_lt with hl | hl
-  · rw [eq_nil_of_length_eq_zero hl.symm, rotate_nil, rotate_eq_nil_iff]
+  · rw [eq_nil_of_length_eq_zero hl.symm, rotate_nil]
   · rcases (Nat.zero_le (n % l'.length)).eq_or_lt with hn | hn
     · simp [← hn]
     · rw [mod_eq_of_lt (tsub_lt_self hl hn), tsub_add_cancel_of_le (α := ℕ), mod_self, rotate_zero]

f694c7de

chore(Data/List/Rotate): add @[simp] to rotate_replicate (#10106)

d883f187

Diff

@@ -130,7 +130,7 @@ theorem length_rotate (l : List α) (n : ℕ) : (l.rotate n).length = l.length :
   rw [rotate_eq_rotate', length_rotate']
 #align list.length_rotate List.length_rotate
 
--- porting note: todo: add `@[simp]`
+@[simp]
 theorem rotate_replicate (a : α) (n : ℕ) (k : ℕ) : (replicate n a).rotate k = replicate n a :=
   eq_replicate.2 ⟨by rw [length_rotate, length_replicate], fun b hb =>
     eq_of_mem_replicate <| mem_rotate.1 hb⟩

f694c7de

chore: reduce imports (#9830)

This uses the improved shake script from #9772 to reduce imports across mathlib. The corresponding noshake.json file has been added to #9772.

Co-authored-by: Mario Carneiro <di.gama@gmail.com>

f4c4ca61

Diff

@@ -3,8 +3,8 @@ Copyright (c) 2019 Chris Hughes. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Chris Hughes, Yakov Pechersky
 -/
-import Mathlib.Data.List.Perm
-import Mathlib.Data.List.Range
+import Mathlib.Data.List.Nodup
+import Mathlib.Data.List.Zip
 
 #align_import data.list.rotate from "leanprover-community/mathlib"@"f694c7dead66f5d4c80f446c796a5aad14707f0e"
 
@@ -247,8 +247,8 @@ theorem get?_rotate {l : List α} {n m : ℕ} (hml : m < l.length) :
         rw [tsub_lt_iff_left hm']
         exact Nat.add_lt_add hlt hml
       conv_rhs => rw [add_comm m, ← mod_add_mod, mod_eq_sub_mod hm', mod_eq_of_lt this]
-      rw [← add_right_inj l.length, ← add_tsub_assoc_of_le, add_tsub_tsub_cancel,
-        add_tsub_cancel_of_le, add_comm]
+      rw [← add_right_inj l.length, ← add_tsub_assoc_of_le (α := ℕ), add_tsub_tsub_cancel (α := ℕ),
+        add_tsub_cancel_of_le (α := ℕ), add_comm]
       exacts [hm', hlt.le, hm]
     · rwa [tsub_lt_iff_left hm, length_drop, tsub_add_cancel_of_le hlt.le]
 #align list.nth_rotate List.get?_rotate
@@ -291,7 +291,7 @@ theorem get_eq_get_rotate (l : List α) (n : ℕ) (k : Fin l.length) :
   rw [get_rotate]
   refine congr_arg l.get (Fin.eq_of_val_eq ?_)
   simp only [mod_add_mod]
-  rw [← add_mod_mod, add_right_comm, tsub_add_cancel_of_le, add_mod_left, mod_eq_of_lt]
+  rw [← add_mod_mod, add_right_comm, tsub_add_cancel_of_le (α := ℕ), add_mod_left, mod_eq_of_lt]
   exacts [k.2, (mod_lt _ (k.1.zero_le.trans_lt k.2)).le]
 
 set_option linter.deprecated false in
@@ -340,7 +340,7 @@ theorem rotate_eq_iff {l l' : List α} {n : ℕ} :
   · rw [eq_nil_of_length_eq_zero hl.symm, rotate_nil, rotate_eq_nil_iff]
   · rcases (Nat.zero_le (n % l'.length)).eq_or_lt with hn | hn
     · simp [← hn]
-    · rw [mod_eq_of_lt (tsub_lt_self hl hn), tsub_add_cancel_of_le, mod_self, rotate_zero]
+    · rw [mod_eq_of_lt (tsub_lt_self hl hn), tsub_add_cancel_of_le (α := ℕ), mod_self, rotate_zero]
       exact (Nat.mod_lt _ hl).le
 #align list.rotate_eq_iff List.rotate_eq_iff
 
@@ -376,7 +376,7 @@ theorem rotate_reverse (l : List α) (n : ℕ) :
   · simp_all! [length_reverse, ← rotate_rotate]
   · cases' l with x l
     · simp
-    · rw [Nat.mod_eq_of_lt, tsub_add_cancel_of_le, rotate_length]
+    · rw [Nat.mod_eq_of_lt, tsub_add_cancel_of_le (α := ℕ), rotate_length]
       · exact tsub_le_self
       · exact tsub_lt_self (by simp) (by simp_all!)
 #align list.rotate_reverse List.rotate_reverse
@@ -444,7 +444,7 @@ theorem IsRotated.symm (h : l ~r l') : l' ~r l := by
   cases' l with hd tl
   · exists 0
   · use (hd :: tl).length * n - n
-    rw [rotate_rotate, add_tsub_cancel_of_le, rotate_length_mul]
+    rw [rotate_rotate, add_tsub_cancel_of_le (α := ℕ), rotate_length_mul]
     exact Nat.le_mul_of_pos_left _ (by simp)
 #align list.is_rotated.symm List.IsRotated.symm

f694c7de

fix: patch for std4#198 (more mul lemmas for Nat) (#6204)

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

2f63d25e

Diff

@@ -445,7 +445,7 @@ theorem IsRotated.symm (h : l ~r l') : l' ~r l := by
   · exists 0
   · use (hd :: tl).length * n - n
     rw [rotate_rotate, add_tsub_cancel_of_le, rotate_length_mul]
-    exact Nat.le_mul_of_pos_left (by simp)
+    exact Nat.le_mul_of_pos_left _ (by simp)
 #align list.is_rotated.symm List.IsRotated.symm
 
 theorem isRotated_comm : l ~r l' ↔ l' ~r l :=

f694c7de

chore: remove uses of cases' (#9171)

I literally went through and regex'd some uses of cases', replacing them with rcases; this is meant to be a low effort PR as I hope that tools can do this in the future.

rcases is an easier replacement than cases, though with better tools we could in future do a second pass converting simple rcases added here (and existing ones) to cases.

3fca282c

Diff

@@ -143,7 +143,7 @@ theorem rotate_eq_drop_append_take {l : List α} {n : ℕ} :
 
 theorem rotate_eq_drop_append_take_mod {l : List α} {n : ℕ} :
     l.rotate n = l.drop (n % l.length) ++ l.take (n % l.length) := by
-  cases' l.length.zero_le.eq_or_lt with hl hl
+  rcases l.length.zero_le.eq_or_lt with hl | hl
   · simp [eq_nil_of_length_eq_zero hl.symm]
   rw [← rotate_eq_drop_append_take (n.mod_lt hl).le, rotate_mod]
 #align list.rotate_eq_drop_append_take_mod List.rotate_eq_drop_append_take_mod
@@ -336,9 +336,9 @@ theorem rotate_eq_rotate {l l' : List α} {n : ℕ} : l.rotate n = l'.rotate n 
 theorem rotate_eq_iff {l l' : List α} {n : ℕ} :
     l.rotate n = l' ↔ l = l'.rotate (l'.length - n % l'.length) := by
   rw [← @rotate_eq_rotate _ l _ n, rotate_rotate, ← rotate_mod l', add_mod]
-  cases' l'.length.zero_le.eq_or_lt with hl hl
+  rcases l'.length.zero_le.eq_or_lt with hl | hl
   · rw [eq_nil_of_length_eq_zero hl.symm, rotate_nil, rotate_eq_nil_iff]
-  · cases' (Nat.zero_le (n % l'.length)).eq_or_lt with hn hn
+  · rcases (Nat.zero_le (n % l'.length)).eq_or_lt with hn | hn
     · simp [← hn]
     · rw [mod_eq_of_lt (tsub_lt_self hl hn), tsub_add_cancel_of_le, mod_self, rotate_zero]
       exact (Nat.mod_lt _ hl).le
@@ -395,7 +395,7 @@ theorem Nodup.rotate_eq_self_iff {l : List α} (hl : l.Nodup) {n : ℕ} :
     l.rotate n = l ↔ n % l.length = 0 ∨ l = [] := by
   constructor
   · intro h
-    cases' l.length.zero_le.eq_or_lt with hl' hl'
+    rcases l.length.zero_le.eq_or_lt with hl' | hl'
     · simp [← length_eq_zero, ← hl']
     left
     rw [nodup_iff_nthLe_inj] at hl

f694c7de

chore: avoid lean3 style have/suffices (#6964)

Many proofs use the "stream of consciousness" style from Lean 3, rather than have ... := or suffices ... from/by.

This PR updates a fraction of these to the preferred Lean 4 style.

I think a good goal would be to delete the "deferred" versions of have, suffices, and let at the bottom of Mathlib.Tactic.Have

(Anyone who would like to contribute more cleanup is welcome to push directly to this branch.)

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

bdc47f68

Diff

@@ -243,8 +243,8 @@ theorem get?_rotate {l : List α} {n m : ℕ} (hml : m < l.length) :
     · congr 1
       rw [length_drop] at hm
       have hm' := tsub_le_iff_left.1 hm
-      have : n % length l + m - length l < length l
-      · rw [tsub_lt_iff_left hm']
+      have : n % length l + m - length l < length l := by
+        rw [tsub_lt_iff_left hm']
         exact Nat.add_lt_add hlt hml
       conv_rhs => rw [add_comm m, ← mod_add_mod, mod_eq_sub_mod hm', mod_eq_of_lt this]
       rw [← add_right_inj l.length, ← add_tsub_assoc_of_le, add_tsub_tsub_cancel,

f694c7de

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

@@ -214,7 +214,7 @@ theorem rotate_singleton (x : α) (n : ℕ) : [x].rotate n = [x] :=
   rotate_replicate x 1 n
 #align list.rotate_singleton List.rotate_singleton
 
-theorem zipWith_rotate_distrib {α β γ : Type _} (f : α → β → γ) (l : List α) (l' : List β) (n : ℕ)
+theorem zipWith_rotate_distrib {α β γ : Type*} (f : α → β → γ) (l : List α) (l' : List β) (n : ℕ)
     (h : l.length = l'.length) :
     (zipWith f l l').rotate n = zipWith f (l.rotate n) (l'.rotate n) := by
   rw [rotate_eq_drop_append_take_mod, rotate_eq_drop_append_take_mod,
@@ -226,7 +226,7 @@ theorem zipWith_rotate_distrib {α β γ : Type _} (f : α → β → γ) (l : L
 attribute [local simp] rotate_cons_succ
 
 --Porting note: removing @[simp], simp can prove it
-theorem zipWith_rotate_one {β : Type _} (f : α → α → β) (x y : α) (l : List α) :
+theorem zipWith_rotate_one {β : Type*} (f : α → α → β) (x y : α) (l : List α) :
     zipWith f (x :: y :: l) ((x :: y :: l).rotate 1) = f x y :: zipWith f (y :: l) (l ++ [x]) := by
   simp
 #align list.zip_with_rotate_one List.zipWith_rotate_one
@@ -381,7 +381,7 @@ theorem rotate_reverse (l : List α) (n : ℕ) :
       · exact tsub_lt_self (by simp) (by simp_all!)
 #align list.rotate_reverse List.rotate_reverse
 
-theorem map_rotate {β : Type _} (f : α → β) (l : List α) (n : ℕ) :
+theorem map_rotate {β : Type*} (f : α → β) (l : List α) (n : ℕ) :
     map f (l.rotate n) = (map f l).rotate n := by
   induction' n with n hn IH generalizing l
   · simp
@@ -467,7 +467,7 @@ theorem IsRotated.eqv : Equivalence (@IsRotated α) :=
 #align list.is_rotated.eqv List.IsRotated.eqv
 
 /-- The relation `List.IsRotated l l'` forms a `Setoid` of cycles. -/
-def IsRotated.setoid (α : Type _) : Setoid (List α) where
+def IsRotated.setoid (α : Type*) : Setoid (List α) where
   r := IsRotated
   iseqv := IsRotated.eqv
 #align list.is_rotated.setoid List.IsRotated.setoid
@@ -547,7 +547,7 @@ theorem isRotated_iff_mem_map_range : l ~r l' ↔ l' ∈ (List.range (l.length +
 
 -- Porting note: @[congr] only works for equality.
 -- @[congr]
-theorem IsRotated.map {β : Type _} {l₁ l₂ : List α} (h : l₁ ~r l₂) (f : α → β) :
+theorem IsRotated.map {β : Type*} {l₁ l₂ : List α} (h : l₁ ~r l₂) (f : α → β) :
     map f l₁ ~r map f l₂ := by
   obtain ⟨n, rfl⟩ := h
   rw [map_rotate]

f694c7de

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,15 +2,12 @@
 Copyright (c) 2019 Chris Hughes. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Chris Hughes, Yakov Pechersky
-
-! This file was ported from Lean 3 source module data.list.rotate
-! leanprover-community/mathlib commit f694c7dead66f5d4c80f446c796a5aad14707f0e
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Data.List.Perm
 import Mathlib.Data.List.Range
 
+#align_import data.list.rotate from "leanprover-community/mathlib"@"f694c7dead66f5d4c80f446c796a5aad14707f0e"
+
 /-!
 # List rotation

f694c7de

chore: reenable eta, bump to nightly 2023-05-16 (#3414)

Now that leanprover/lean4#2210 has been merged, this PR:

removes all the set_option synthInstance.etaExperiment true commands (and some etaExperiment% term elaborators)
removes many but not quite all set_option maxHeartbeats commands
makes various other changes required to cope with leanprover/lean4#2210.

Co-authored-by: Scott Morrison <scott.morrison@anu.edu.au> Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Matthew Ballard <matt@mrb.email>

a6e1045f

Diff

@@ -77,14 +77,11 @@ theorem rotate'_eq_drop_append_take :
         drop_append_of_le_length hnl, take_append_of_le_length hnl]; simp
 #align list.rotate'_eq_drop_append_take List.rotate'_eq_drop_append_take
 
--- Porting note: Added termination_by and decreasing_by as recursion fails
 theorem rotate'_rotate' : ∀ (l : List α) (n m : ℕ), (l.rotate' n).rotate' m = l.rotate' (n + m)
   | a :: l, 0, m => by simp
   | [], n, m => by simp
   | a :: l, n + 1, m => by
     rw [rotate'_cons_succ, rotate'_rotate' _ n, add_right_comm, ← rotate'_cons_succ]
-    simp
-  termination_by rotate'_rotate' l n _ => (l.length, n)
 #align list.rotate'_rotate' List.rotate'_rotate'
 
 @[simp]
@@ -92,7 +89,6 @@ theorem rotate'_length (l : List α) : rotate' l l.length = l := by
   rw [rotate'_eq_drop_append_take le_rfl]; simp
 #align list.rotate'_length List.rotate'_length
 
--- Porting note: Added termination_by and decreasing_by as recursion fails
 @[simp]
 theorem rotate'_length_mul (l : List α) : ∀ n : ℕ, l.rotate' (l.length * n) = l
   | 0 => by simp

f694c7de

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

@@ -180,8 +180,7 @@ theorem rotate_length_mul (l : List α) (n : ℕ) : l.rotate (l.length * n) = l
 theorem prod_rotate_eq_one_of_prod_eq_one [Group α] :
     ∀ {l : List α} (_ : l.prod = 1) (n : ℕ), (l.rotate n).prod = 1
   | [], _, _ => by simp
-  | a :: l, hl, n =>
-    by
+  | a :: l, hl, n => by
     have : n % List.length (a :: l) ≤ List.length (a :: l) := le_of_lt (Nat.mod_lt _ (by simp))
     rw [← List.take_append_drop (n % List.length (a :: l)) (a :: l)] at hl;
       rw [← rotate_mod, rotate_eq_drop_append_take this, List.prod_append, mul_eq_one_iff_inv_eq, ←
@@ -223,8 +222,8 @@ theorem rotate_singleton (x : α) (n : ℕ) : [x].rotate n = [x] :=
 #align list.rotate_singleton List.rotate_singleton
 
 theorem zipWith_rotate_distrib {α β γ : Type _} (f : α → β → γ) (l : List α) (l' : List β) (n : ℕ)
-    (h : l.length = l'.length) : (zipWith f l l').rotate n = zipWith f (l.rotate n) (l'.rotate n) :=
-  by
+    (h : l.length = l'.length) :
+    (zipWith f l l').rotate n = zipWith f (l.rotate n) (l'.rotate n) := by
   rw [rotate_eq_drop_append_take_mod, rotate_eq_drop_append_take_mod,
     rotate_eq_drop_append_take_mod, h, zipWith_append, ← zipWith_distrib_drop, ←
     zipWith_distrib_take, List.length_zipWith, h, min_self]

f694c7de

chore: fix #align lines (#3640)

This PR fixes two things:

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

2b42dc7c

Diff

@@ -110,7 +110,6 @@ theorem rotate'_mod (l : List α) (n : ℕ) : l.rotate' (n % l.length) = l.rotat
         (l.rotate' (n % l.length)).rotate' ((l.rotate' (n % l.length)).length * (n / l.length)) :=
       by rw [rotate'_length_mul]
     _ = l.rotate' n := by rw [rotate'_rotate', length_rotate', Nat.mod_add_div]
-
 #align list.rotate'_mod List.rotate'_mod
 
 theorem rotate_eq_rotate' (l : List α) (n : ℕ) : l.rotate n = l.rotate' n :=

f694c7de

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

@@ -550,8 +550,8 @@ theorem isRotated_iff_mod : l ~r l' ↔ ∃ n ≤ l.length, l.rotate n = l' := b
 theorem isRotated_iff_mem_map_range : l ~r l' ↔ l' ∈ (List.range (l.length + 1)).map l.rotate := by
   simp_rw [mem_map, mem_range, isRotated_iff_mod]
   exact
-    ⟨fun ⟨n, hn, h⟩ => ⟨n, Nat.lt_succ_of_le hn, h.symm⟩,
-      fun ⟨n, hn, h⟩ => ⟨n, Nat.le_of_lt_succ hn, h.symm⟩⟩
+    ⟨fun ⟨n, hn, h⟩ => ⟨n, Nat.lt_succ_of_le hn, h⟩,
+      fun ⟨n, hn, h⟩ => ⟨n, Nat.le_of_lt_succ hn, h⟩⟩
 #align list.is_rotated_iff_mem_map_range List.isRotated_iff_mem_map_range
 
 -- Porting note: @[congr] only works for equality.

f694c7de

chore: sync Data.List.Rotate (#3040)

data.list.rotate@ccad6d5093bd2f5c6ca621fc74674cce51355af6..f694c7dead66f5d4c80f446c796a5aad14707f0e

Also add non-deprecated versions of some lemmas (use List.get instead of List.nthLe).

Co-authored-by: Jeremy Tan Jie Rui <reddeloostw@gmail.com>

c001e380

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Chris Hughes, Yakov Pechersky
 
 ! This file was ported from Lean 3 source module data.list.rotate
-! leanprover-community/mathlib commit ccad6d5093bd2f5c6ca621fc74674cce51355af6
+! leanprover-community/mathlib commit f694c7dead66f5d4c80f446c796a5aad14707f0e
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -18,8 +18,8 @@ This file proves basic results about `List.rotate`, the list rotation.
 
 ## Main declarations
 
-* `IsRotated l₁ l₂`: States that `l₁` is a rotated version of `l₂`.
-* `cyclicPermutations l`: The list of all cyclic permutants of `l`, up to the length of `l`.
+* `List.IsRotated l₁ l₂`: States that `l₁` is a rotated version of `l₂`.
+* `List.cyclicPermutations l`: The list of all cyclic permutants of `l`, up to the length of `l`.
 
 ## Tags
 
@@ -31,7 +31,7 @@ universe u
 
 variable {α : Type u}
 
-open Nat
+open Nat Function
 
 namespace List
 
@@ -138,6 +138,12 @@ theorem length_rotate (l : List α) (n : ℕ) : (l.rotate n).length = l.length :
   rw [rotate_eq_rotate', length_rotate']
 #align list.length_rotate List.length_rotate
 
+-- porting note: todo: add `@[simp]`
+theorem rotate_replicate (a : α) (n : ℕ) (k : ℕ) : (replicate n a).rotate k = replicate n a :=
+  eq_replicate.2 ⟨by rw [length_rotate, length_replicate], fun b hb =>
+    eq_of_mem_replicate <| mem_rotate.1 hb⟩
+#align list.rotate_replicate List.rotate_replicate
+
 theorem rotate_eq_drop_append_take {l : List α} {n : ℕ} :
     n ≤ l.length → l.rotate n = l.drop n ++ l.take n := by
   rw [rotate_eq_rotate']; exact rotate'_eq_drop_append_take
@@ -213,26 +219,10 @@ theorem nil_eq_rotate_iff {l : List α} {n : ℕ} : [] = l.rotate n ↔ [] = l :
 #align list.nil_eq_rotate_iff List.nil_eq_rotate_iff
 
 @[simp]
-theorem rotate_singleton (x : α) (n : ℕ) : [x].rotate n = [x] := by
-  induction' n with n hn
-  · simp
-  · rwa [rotate_cons_succ]
+theorem rotate_singleton (x : α) (n : ℕ) : [x].rotate n = [x] :=
+  rotate_replicate x 1 n
 #align list.rotate_singleton List.rotate_singleton
 
-@[simp]
-theorem rotate_eq_singleton_iff {l : List α} {n : ℕ} {x : α} : l.rotate n = [x] ↔ l = [x] := by
-  induction' n with n hn generalizing l
-  · simp
-  · cases' l with hd tl
-    · simp only [rotate_nil]
-    · simp [rotate_cons_succ, hn, append_eq_cons_iff, and_comm]
-#align list.rotate_eq_singleton_iff List.rotate_eq_singleton_iff
-
-@[simp]
-theorem singleton_eq_rotate_iff {l : List α} {n : ℕ} {x : α} : [x] = l.rotate n ↔ [x] = l := by
-  rw [eq_comm, rotate_eq_singleton_iff, eq_comm]
-#align list.singleton_eq_rotate_iff List.singleton_eq_rotate_iff
-
 theorem zipWith_rotate_distrib {α β γ : Type _} (f : α → β → γ) (l : List α) (l' : List β) (n : ℕ)
     (h : l.length = l'.length) : (zipWith f l l').rotate n = zipWith f (l.rotate n) (l'.rotate n) :=
   by
@@ -250,46 +240,95 @@ theorem zipWith_rotate_one {β : Type _} (f : α → α → β) (x y : α) (l :
   simp
 #align list.zip_with_rotate_one List.zipWith_rotate_one
 
+theorem get?_rotate {l : List α} {n m : ℕ} (hml : m < l.length) :
+    (l.rotate n).get? m = l.get? ((m + n) % l.length) := by
+  rw [rotate_eq_drop_append_take_mod]
+  rcases lt_or_le m (l.drop (n % l.length)).length with hm | hm
+  · rw [get?_append hm, get?_drop, add_comm m, ← mod_add_mod]
+    rw [length_drop, lt_tsub_iff_left] at hm
+    rw [mod_eq_of_lt hm]
+  · have hlt : n % length l < length l := mod_lt _ (m.zero_le.trans_lt hml)
+    rw [get?_append_right hm, get?_take, length_drop]
+    · congr 1
+      rw [length_drop] at hm
+      have hm' := tsub_le_iff_left.1 hm
+      have : n % length l + m - length l < length l
+      · rw [tsub_lt_iff_left hm']
+        exact Nat.add_lt_add hlt hml
+      conv_rhs => rw [add_comm m, ← mod_add_mod, mod_eq_sub_mod hm', mod_eq_of_lt this]
+      rw [← add_right_inj l.length, ← add_tsub_assoc_of_le, add_tsub_tsub_cancel,
+        add_tsub_cancel_of_le, add_comm]
+      exacts [hm', hlt.le, hm]
+    · rwa [tsub_lt_iff_left hm, length_drop, tsub_add_cancel_of_le hlt.le]
+#align list.nth_rotate List.get?_rotate
+
+-- porting note: new lemma
+theorem get_rotate (l : List α) (n : ℕ) (k : Fin (l.rotate n).length) :
+    (l.rotate n).get k =
+      l.get ⟨(k + n) % l.length, mod_lt _ (length_rotate l n ▸ k.1.zero_le.trans_lt k.2)⟩ := by
+  rw [← Option.some_inj, ← get?_eq_get, ← get?_eq_get, get?_rotate]
+  exact k.2.trans_eq (length_rotate _ _)
+
+theorem head?_rotate {l : List α} {n : ℕ} (h : n < l.length) : head? (l.rotate n) = l.get? n := by
+  rw [← get?_zero, get?_rotate (n.zero_le.trans_lt h), zero_add, Nat.mod_eq_of_lt h]
+#align list.head'_rotate List.head?_rotate
+
+-- porting note: moved down from its original location below `get_rotate` so that the
+-- non-deprecated lemma does not use the deprecated version
+set_option linter.deprecated false in
+@[deprecated get_rotate]
+theorem nthLe_rotate (l : List α) (n k : ℕ) (hk : k < (l.rotate n).length) :
+    (l.rotate n).nthLe k hk =
+      l.nthLe ((k + n) % l.length) (mod_lt _ (length_rotate l n ▸ k.zero_le.trans_lt hk)) :=
+  get_rotate l n ⟨k, hk⟩
+#align list.nth_le_rotate List.nthLe_rotate
+
 set_option linter.deprecated false in
 theorem nthLe_rotate_one (l : List α) (k : ℕ) (hk : k < (l.rotate 1).length) :
     (l.rotate 1).nthLe k hk =
-      l.nthLe ((k + 1) % l.length) (mod_lt _ (length_rotate l 1 ▸ k.zero_le.trans_lt hk)) := by
-  cases' l with hd tl
-  · contradiction
-  · have : k ≤ tl.length := by
-      refine' Nat.le_of_lt_succ _
-      simpa using hk
-    rcases this.eq_or_lt with (rfl | hk')
-    · simp [nthLe_append_right le_rfl, nthLe_cons]
-    · simp [nthLe_append _ hk', length_cons, Nat.mod_eq_of_lt (Nat.succ_lt_succ hk'), nthLe_cons]
+      l.nthLe ((k + 1) % l.length) (mod_lt _ (length_rotate l 1 ▸ k.zero_le.trans_lt hk)) :=
+  nthLe_rotate l 1 k hk
 #align list.nth_le_rotate_one List.nthLe_rotate_one
 
-theorem nthLe_rotate (l : List α) (n k : ℕ) (hk : k < (l.rotate n).length) :
-    (l.rotate n).nthLe k hk =
-      l.nthLe ((k + n) % l.length) (mod_lt _ (length_rotate l n ▸ k.zero_le.trans_lt hk)) := by
-  induction' n with n hn generalizing l k
-  · have hk' : k < l.length := by simpa using hk
-    simp [Nat.mod_eq_of_lt hk']
-  · simp [Nat.succ_eq_add_one, ← rotate_rotate, nthLe_rotate_one, hn l, add_comm, add_left_comm]
-#align list.nth_le_rotate List.nthLe_rotate
+-- porting note: new lemma
+/-- A version of `List.get_rotate` that represents `List.get l` in terms of
+`List.get (List.rotate l n)`, not vice versa. Can be used instead of rewriting `List.get_rotate`
+from right to left. -/
+theorem get_eq_get_rotate (l : List α) (n : ℕ) (k : Fin l.length) :
+    l.get k = (l.rotate n).get ⟨(l.length - n % l.length + k) % l.length,
+      (Nat.mod_lt _ (k.1.zero_le.trans_lt k.2)).trans_eq (length_rotate _ _).symm⟩ := by
+  rw [get_rotate]
+  refine congr_arg l.get (Fin.eq_of_val_eq ?_)
+  simp only [mod_add_mod]
+  rw [← add_mod_mod, add_right_comm, tsub_add_cancel_of_le, add_mod_left, mod_eq_of_lt]
+  exacts [k.2, (mod_lt _ (k.1.zero_le.trans_lt k.2)).le]
 
-/-- A variant of `nthLe_rotate` useful for rewrites. -/
+set_option linter.deprecated false in
+/-- A variant of `List.nthLe_rotate` useful for rewrites from right to left. -/
+@[deprecated get_eq_get_rotate]
 theorem nthLe_rotate' (l : List α) (n k : ℕ) (hk : k < l.length) :
     (l.rotate n).nthLe ((l.length - n % l.length + k) % l.length)
         ((Nat.mod_lt _ (k.zero_le.trans_lt hk)).trans_le (length_rotate _ _).ge) =
-      l.nthLe k hk := by
-  rw [nthLe_rotate]
-  congr
-  let m := l.length
-  rw [mod_add_mod, add_assoc, add_left_comm, add_comm, add_mod, add_mod _ n]
-  cases' (n % m).zero_le.eq_or_lt with hn hn
-  · simpa [← hn] using Nat.mod_eq_of_lt hk
-  · have mpos : 0 < m := k.zero_le.trans_lt hk
-    have hm : m - n % m < m := tsub_lt_self mpos hn
-    have hn' : n % m < m := Nat.mod_lt _ mpos
-    simpa [mod_eq_of_lt hm, tsub_add_cancel_of_le hn'.le] using Nat.mod_eq_of_lt hk
+      l.nthLe k hk :=
+  (get_eq_get_rotate l n ⟨k, hk⟩).symm
 #align list.nth_le_rotate' List.nthLe_rotate'
 
+theorem rotate_eq_self_iff_eq_replicate [hα : Nonempty α] :
+    ∀ {l : List α}, (∀ n, l.rotate n = l) ↔ ∃ a, l = replicate l.length a
+  | [] => by simp
+  | a :: l => ⟨fun h => ⟨a, ext_get (length_replicate _ _).symm fun n h₁ h₂ => by
+      rw [get_replicate, ← Option.some_inj, ← get?_eq_get, ← head?_rotate h₁, h, head?_cons]⟩,
+    fun ⟨b, hb⟩ n => by rw [hb, rotate_replicate]⟩
+#align list.rotate_eq_self_iff_eq_replicate List.rotate_eq_self_iff_eq_replicate
+
+theorem rotate_one_eq_self_iff_eq_replicate [Nonempty α] {l : List α} :
+    l.rotate 1 = l ↔ ∃ a : α, l = List.replicate l.length a :=
+  ⟨fun h =>
+    rotate_eq_self_iff_eq_replicate.mp fun n =>
+      Nat.rec l.rotate_zero (fun n hn => by rwa [Nat.succ_eq_add_one, ← l.rotate_rotate, hn]) n,
+    fun h => rotate_eq_self_iff_eq_replicate.mpr h 1⟩
+#align list.rotate_one_eq_self_iff_eq_replicate List.rotate_one_eq_self_iff_eq_replicate
+
 theorem rotate_injective (n : ℕ) : Function.Injective fun l : List α => l.rotate n := by
   rintro l l' (h : l.rotate n = l'.rotate n)
   have hle : l.length = l'.length := (l.length_rotate n).symm.trans (h.symm ▸ l'.length_rotate n)
@@ -298,7 +337,7 @@ theorem rotate_injective (n : ℕ) : Function.Injective fun l : List α => l.rot
   rw [← take_append_drop _ l, ht, hd, take_append_drop]
 #align list.rotate_injective List.rotate_injective
 
--- possibly easier to find in doc-gen, otherwise not that useful.
+@[simp]
 theorem rotate_eq_rotate {l l' : List α} {n : ℕ} : l.rotate n = l'.rotate n ↔ l = l' :=
   (rotate_injective n).eq_iff
 #align list.rotate_eq_rotate List.rotate_eq_rotate
@@ -314,6 +353,16 @@ theorem rotate_eq_iff {l l' : List α} {n : ℕ} :
       exact (Nat.mod_lt _ hl).le
 #align list.rotate_eq_iff List.rotate_eq_iff
 
+@[simp]
+theorem rotate_eq_singleton_iff {l : List α} {n : ℕ} {x : α} : l.rotate n = [x] ↔ l = [x] := by
+  rw [rotate_eq_iff, rotate_singleton]
+#align list.rotate_eq_singleton_iff List.rotate_eq_singleton_iff
+
+@[simp]
+theorem singleton_eq_rotate_iff {l : List α} {n : ℕ} {x : α} : [x] = l.rotate n ↔ [x] = l := by
+  rw [eq_comm, rotate_eq_singleton_iff, eq_comm]
+#align list.singleton_eq_rotate_iff List.singleton_eq_rotate_iff
+
 theorem reverse_rotate (l : List α) (n : ℕ) :
     (l.rotate n).reverse = l.reverse.rotate (l.length - n % l.length) := by
   rw [← length_reverse l, ← rotate_eq_iff]
@@ -545,7 +594,7 @@ theorem cyclicPermutations_of_ne_nil (l : List α) (h : l ≠ []) :
 #align list.cyclic_permutations_of_ne_nil List.cyclicPermutations_of_ne_nil
 
 theorem length_cyclicPermutations_cons (x : α) (l : List α) :
-    length (cyclicPermutations (x :: l)) = length l + 1 := by simp [cyclicPermutations_of_ne_nil]
+    length (cyclicPermutations (x :: l)) = length l + 1 := by simp [cyclicPermutations_cons]
 #align list.length_cyclic_permutations_cons List.length_cyclicPermutations_cons
 
 @[simp]
@@ -643,6 +692,7 @@ theorem IsRotated.cyclicPermutations {l l' : List α} (h : l ~r l') :
   exact ⟨k, by simp⟩
 #align list.is_rotated.cyclic_permutations List.IsRotated.cyclicPermutations
 
+set_option linter.deprecated false in
 @[simp]
 theorem isRotated_cyclicPermutations_iff {l l' : List α} :
     l.cyclicPermutations ~r l'.cyclicPermutations ↔ l ~r l' := by

ccad6d50

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

526ab32a

Diff

@@ -426,7 +426,7 @@ theorem IsRotated.eqv : Equivalence (@IsRotated α) :=
   Equivalence.mk IsRotated.refl IsRotated.symm IsRotated.trans
 #align list.is_rotated.eqv List.IsRotated.eqv
 
-/-- The relation `List.IsRotated l l'` forms a `setoid` of cycles. -/
+/-- The relation `List.IsRotated l l'` forms a `Setoid` of cycles. -/
 def IsRotated.setoid (α : Type _) : Setoid (List α) where
   r := IsRotated
   iseqv := IsRotated.eqv

ccad6d50

feat: port Data.List.Rotate (#1490)

Co-authored-by: ChrisHughes24 <chrishughes24@gmail.com> Co-authored-by: qawbecrdtey <qawbecrdtey@naver.com> Co-authored-by: qawbecrdtey <40463813+qawbecrdtey@users.noreply.github.com>

e78a2694

`data.list.rotate` ⟷ `Mathlib.Data.List.Rotate`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 2 + 139

data.list.rotate ⟷ Mathlib.Data.List.Rotate

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 2 + 139

`data.list.rotate` ⟷ `Mathlib.Data.List.Rotate`