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

@@ -67,8 +67,8 @@ begin
     have : ∀ (x : α) (h : x ∈ u₂), x = a := λ x m,
       antisymm ((pairwise_append.1 s₂).2.2 _ m a (mem_cons_self _ _))
         (h₁ _ (by simp [m])),
-    rw [(@eq_repeat _ a (length u₂ + 1) (a::u₂)).2,
-        (@eq_repeat _ a (length u₂ + 1) (u₂++[a])).2];
+    rw [(@eq_replicate _ a (length u₂ + 1) (a::u₂)).2,
+        (@eq_replicate _ a (length u₂ + 1) (u₂++[a])).2];
     split; simp [iff_true_intro this, or_comm] }
 end

9003f287

(first ported)

Changes in mathlib3port

mathlib3

mathlib3port

327c3c0d

bump to nightly-2024-04-25-08

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

ad7a2212

Diff

@@ -104,7 +104,7 @@ theorem eq_of_perm_of_sorted [IsAntisymm α r] {l₁ l₂ : List α} (p : l₁ ~
     rw [(@eq_replicate _ a (length u₂ + 1) (a :: u₂)).2,
           (@eq_replicate _ a (length u₂ + 1) (u₂ ++ [a])).2] <;>
         constructor <;>
-      simp [iff_true_intro this, or_comm']
+      simp [iff_true_intro this, or_comm]
 #align list.eq_of_perm_of_sorted List.eq_of_perm_of_sorted
 -/

327c3c0d

bump to nightly-2024-03-17-08

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

22f01ce4

Diff

@@ -148,7 +148,7 @@ theorem Sorted.rel_of_mem_take_of_mem_drop {l : List α} (h : List.Sorted r l) {
   obtain ⟨iy, hiy, rfl⟩ := nth_le_of_mem hy
   obtain ⟨ix, hix, rfl⟩ := nth_le_of_mem hx
   rw [nth_le_take', nth_le_drop']
-  rw [length_take] at hix 
+  rw [length_take] at hix
   exact h.rel_nth_le_of_lt _ _ (ix.lt_add_right _ _ (lt_min_iff.mp hix).left)
 #align list.sorted.rel_of_mem_take_of_mem_drop List.Sorted.rel_of_mem_take_of_mem_drop
 -/

327c3c0d

bump to nightly-2024-02-05-08

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

516c6ec2

Diff

@@ -390,7 +390,7 @@ def merge : List α → List α → List α
 #align list.merge List.merge
 -/
 
-/- ./././Mathport/Syntax/Translate/Command.lean:298:8: warning: using_well_founded used, estimated equivalent -/
+/- ./././Mathport/Syntax/Translate/Command.lean:299:8: warning: using_well_founded used, estimated equivalent -/
 #print List.mergeSort /-
 /-- Implementation of a merge sort algorithm to sort a list. -/
 def mergeSort : List α → List α
@@ -400,8 +400,7 @@ def mergeSort : List α → List α
     cases' e : split (a :: b :: l) with l₁ l₂
     cases' length_split_lt e with h₁ h₂
     exact merge r (merge_sort l₁) (merge_sort l₂)
-termination_by
-  _ x => WellFounded.wrap (InvImage.wf length Nat.lt_wfRel) x
+termination_by x => WellFounded.wrap (InvImage.wf length Nat.lt_wfRel) x
 #align list.merge_sort List.mergeSort
 -/
 
@@ -434,7 +433,7 @@ theorem perm_merge : ∀ l l' : List α, merge r l l' ~ l ++ l'
 #align list.perm_merge List.perm_merge
 -/
 
-/- ./././Mathport/Syntax/Translate/Command.lean:298:8: warning: using_well_founded used, estimated equivalent -/
+/- ./././Mathport/Syntax/Translate/Command.lean:299:8: warning: using_well_founded used, estimated equivalent -/
 #print List.perm_mergeSort /-
 theorem perm_mergeSort : ∀ l : List α, mergeSort r l ~ l
   | [] => by simp [merge_sort]
@@ -445,8 +444,7 @@ theorem perm_mergeSort : ∀ l : List α, mergeSort r l ~ l
     rw [merge_sort_cons_cons r e]
     apply (perm_merge r _ _).trans
     exact ((perm_merge_sort l₁).append (perm_merge_sort l₂)).trans (perm_split e).symm
-termination_by
-  _ x => WellFounded.wrap (InvImage.wf length Nat.lt_wfRel) x
+termination_by x => WellFounded.wrap (InvImage.wf length Nat.lt_wfRel) x
 #align list.perm_merge_sort List.perm_mergeSort
 -/
 
@@ -491,7 +489,7 @@ theorem Sorted.merge : ∀ {l l' : List α}, Sorted r l → Sorted r l' → Sort
 
 variable (r)
 
-/- ./././Mathport/Syntax/Translate/Command.lean:298:8: warning: using_well_founded used, estimated equivalent -/
+/- ./././Mathport/Syntax/Translate/Command.lean:299:8: warning: using_well_founded used, estimated equivalent -/
 #print List.sorted_mergeSort /-
 theorem sorted_mergeSort : ∀ l : List α, Sorted r (mergeSort r l)
   | [] => by simp [merge_sort]
@@ -501,8 +499,7 @@ theorem sorted_mergeSort : ∀ l : List α, Sorted r (mergeSort r l)
     cases' length_split_lt e with h₁ h₂
     rw [merge_sort_cons_cons r e]
     exact (sorted_merge_sort l₁).merge (sorted_merge_sort l₂)
-termination_by
-  _ x => WellFounded.wrap (InvImage.wf length Nat.lt_wfRel) x
+termination_by x => WellFounded.wrap (InvImage.wf length Nat.lt_wfRel) x
 #align list.sorted_merge_sort List.sorted_mergeSort
 -/

327c3c0d

bump to nightly-2023-12-23-06

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

b8c74971

Diff

@@ -390,6 +390,7 @@ def merge : List α → List α → List α
 #align list.merge List.merge
 -/
 
+/- ./././Mathport/Syntax/Translate/Command.lean:298:8: warning: using_well_founded used, estimated equivalent -/
 #print List.mergeSort /-
 /-- Implementation of a merge sort algorithm to sort a list. -/
 def mergeSort : List α → List α
@@ -399,7 +400,8 @@ def mergeSort : List α → List α
     cases' e : split (a :: b :: l) with l₁ l₂
     cases' length_split_lt e with h₁ h₂
     exact merge r (merge_sort l₁) (merge_sort l₂)
-termination_by' ⟨_, InvImage.wf length Nat.lt_wfRel⟩
+termination_by
+  _ x => WellFounded.wrap (InvImage.wf length Nat.lt_wfRel) x
 #align list.merge_sort List.mergeSort
 -/
 
@@ -432,6 +434,7 @@ theorem perm_merge : ∀ l l' : List α, merge r l l' ~ l ++ l'
 #align list.perm_merge List.perm_merge
 -/
 
+/- ./././Mathport/Syntax/Translate/Command.lean:298:8: warning: using_well_founded used, estimated equivalent -/
 #print List.perm_mergeSort /-
 theorem perm_mergeSort : ∀ l : List α, mergeSort r l ~ l
   | [] => by simp [merge_sort]
@@ -442,7 +445,8 @@ theorem perm_mergeSort : ∀ l : List α, mergeSort r l ~ l
     rw [merge_sort_cons_cons r e]
     apply (perm_merge r _ _).trans
     exact ((perm_merge_sort l₁).append (perm_merge_sort l₂)).trans (perm_split e).symm
-termination_by' ⟨_, InvImage.wf length Nat.lt_wfRel⟩
+termination_by
+  _ x => WellFounded.wrap (InvImage.wf length Nat.lt_wfRel) x
 #align list.perm_merge_sort List.perm_mergeSort
 -/
 
@@ -487,6 +491,7 @@ theorem Sorted.merge : ∀ {l l' : List α}, Sorted r l → Sorted r l' → Sort
 
 variable (r)
 
+/- ./././Mathport/Syntax/Translate/Command.lean:298:8: warning: using_well_founded used, estimated equivalent -/
 #print List.sorted_mergeSort /-
 theorem sorted_mergeSort : ∀ l : List α, Sorted r (mergeSort r l)
   | [] => by simp [merge_sort]
@@ -496,7 +501,8 @@ theorem sorted_mergeSort : ∀ l : List α, Sorted r (mergeSort r l)
     cases' length_split_lt e with h₁ h₂
     rw [merge_sort_cons_cons r e]
     exact (sorted_merge_sort l₁).merge (sorted_merge_sort l₂)
-termination_by' ⟨_, InvImage.wf length Nat.lt_wfRel⟩
+termination_by
+  _ x => WellFounded.wrap (InvImage.wf length Nat.lt_wfRel) x
 #align list.sorted_merge_sort List.sorted_mergeSort
 -/

327c3c0d

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) 2016 Jeremy Avigad. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Jeremy Avigad
 -/
-import Mathbin.Data.List.OfFn
-import Mathbin.Data.List.Perm
+import Data.List.OfFn
+import Data.List.Perm
 
 #align_import data.list.sort from "leanprover-community/mathlib"@"327c3c0d9232d80e250dc8f65e7835b82b266ea5"

327c3c0d

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) 2016 Jeremy Avigad. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Jeremy Avigad
-
-! This file was ported from Lean 3 source module data.list.sort
-! leanprover-community/mathlib commit 327c3c0d9232d80e250dc8f65e7835b82b266ea5
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Data.List.OfFn
 import Mathbin.Data.List.Perm
 
+#align_import data.list.sort from "leanprover-community/mathlib"@"327c3c0d9232d80e250dc8f65e7835b82b266ea5"
+
 /-!
 # Sorting algorithms on lists

327c3c0d

bump to nightly-2023-06-13-21

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

829520ac

Diff

@@ -162,17 +162,21 @@ section Monotone
 
 variable {n : ℕ} {α : Type uu} [Preorder α] {f : Fin n → α}
 
+#print List.monotone_iff_ofFn_sorted /-
 /-- A tuple is monotone if and only if the list obtained from it is sorted. -/
 theorem monotone_iff_ofFn_sorted : Monotone f ↔ (ofFn f).Sorted (· ≤ ·) :=
   by
   simp_rw [sorted, pairwise_iff_nth_le, length_of_fn, nth_le_of_fn', monotone_iff_forall_lt]
   exact ⟨fun h i j hj hij => h <| fin.mk_lt_mk.mpr hij, fun h ⟨i, _⟩ ⟨j, hj⟩ hij => h i j hj hij⟩
 #align list.monotone_iff_of_fn_sorted List.monotone_iff_ofFn_sorted
+-/
 
+#print Monotone.ofFn_sorted /-
 /-- The list obtained from a monotone tuple is sorted. -/
 theorem Monotone.ofFn_sorted (h : Monotone f) : (ofFn f).Sorted (· ≤ ·) :=
   monotone_iff_ofFn_sorted.1 h
 #align list.monotone.of_fn_sorted Monotone.ofFn_sorted
+-/
 
 end Monotone
 
@@ -180,7 +184,6 @@ section Sort
 
 variable {α : Type uu} (r : α → α → Prop) [DecidableRel r]
 
--- mathport name: «expr ≼ »
 local infixl:50 " ≼ " => r
 
 /-! ### Insertion sort -/
@@ -390,8 +393,6 @@ def merge : List α → List α → List α
 #align list.merge List.merge
 -/
 
-include r
-
 #print List.mergeSort /-
 /-- Implementation of a merge sort algorithm to sort a list. -/
 def mergeSort : List α → List α

327c3c0d

bump to nightly-2023-06-01-16

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

b9c87c70

Diff

@@ -151,7 +151,7 @@ theorem Sorted.rel_of_mem_take_of_mem_drop {l : List α} (h : List.Sorted r l) {
   obtain ⟨iy, hiy, rfl⟩ := nth_le_of_mem hy
   obtain ⟨ix, hix, rfl⟩ := nth_le_of_mem hx
   rw [nth_le_take', nth_le_drop']
-  rw [length_take] at hix
+  rw [length_take] at hix 
   exact h.rel_nth_le_of_lt _ _ (ix.lt_add_right _ _ (lt_min_iff.mp hix).left)
 #align list.sorted.rel_of_mem_take_of_mem_drop List.Sorted.rel_of_mem_take_of_mem_drop
 -/
@@ -248,9 +248,8 @@ open Perm
 theorem perm_orderedInsert (a) : ∀ l : List α, orderedInsert r a l ~ a :: l
   | [] => Perm.refl _
   | b :: l => by
-    by_cases a ≼ b <;>
-      [simp [ordered_insert,
-        h];simpa [ordered_insert, h] using ((perm_ordered_insert l).cons _).trans (perm.swap _ _ _)]
+    by_cases a ≼ b <;> [simp [ordered_insert, h];
+      simpa [ordered_insert, h] using ((perm_ordered_insert l).cons _).trans (perm.swap _ _ _)]
 #align list.perm_ordered_insert List.perm_orderedInsert
 -/
 
@@ -282,7 +281,7 @@ theorem Sorted.insertionSort_eq : ∀ {l : List α} (h : Sorted r l), insertionS
   | a :: b :: l, h =>
     by
     rw [insertion_sort, sorted.insertion_sort_eq, ordered_insert, if_pos]
-    exacts[rel_of_sorted_cons h _ (Or.inl rfl), h.tail]
+    exacts [rel_of_sorted_cons h _ (Or.inl rfl), h.tail]
 #align list.sorted.insertion_sort_eq List.Sorted.insertionSort_eq
 -/
 
@@ -401,8 +400,8 @@ def mergeSort : List α → List α
   | a :: b :: l => by
     cases' e : split (a :: b :: l) with l₁ l₂
     cases' length_split_lt e with h₁ h₂
-    exact merge r (merge_sort l₁) (merge_sort l₂)termination_by'
-  ⟨_, InvImage.wf length Nat.lt_wfRel⟩
+    exact merge r (merge_sort l₁) (merge_sort l₂)
+termination_by' ⟨_, InvImage.wf length Nat.lt_wfRel⟩
 #align list.merge_sort List.mergeSort
 -/
 
@@ -416,7 +415,7 @@ theorem mergeSort_cons_cons {a b} {l l₁ l₂ : List α} (h : split (a :: b ::
           h1 =
         L
     by simp [merge_sort, h]; apply this
-  intros ; cases h1; rfl
+  intros; cases h1; rfl
 #align list.merge_sort_cons_cons List.mergeSort_cons_cons
 -/
 
@@ -444,9 +443,8 @@ theorem perm_mergeSort : ∀ l : List α, mergeSort r l ~ l
     cases' length_split_lt e with h₁ h₂
     rw [merge_sort_cons_cons r e]
     apply (perm_merge r _ _).trans
-    exact
-      ((perm_merge_sort l₁).append (perm_merge_sort l₂)).trans (perm_split e).symm termination_by'
-  ⟨_, InvImage.wf length Nat.lt_wfRel⟩
+    exact ((perm_merge_sort l₁).append (perm_merge_sort l₂)).trans (perm_split e).symm
+termination_by' ⟨_, InvImage.wf length Nat.lt_wfRel⟩
 #align list.perm_merge_sort List.perm_mergeSort
 -/
 
@@ -499,8 +497,8 @@ theorem sorted_mergeSort : ∀ l : List α, Sorted r (mergeSort r l)
     cases' e : split (a :: b :: l) with l₁ l₂
     cases' length_split_lt e with h₁ h₂
     rw [merge_sort_cons_cons r e]
-    exact (sorted_merge_sort l₁).merge (sorted_merge_sort l₂)termination_by'
-  ⟨_, InvImage.wf length Nat.lt_wfRel⟩
+    exact (sorted_merge_sort l₁).merge (sorted_merge_sort l₂)
+termination_by' ⟨_, InvImage.wf length Nat.lt_wfRel⟩
 #align list.sorted_merge_sort List.sorted_mergeSort
 -/

327c3c0d

bump to nightly-2023-05-28-06

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

ba5d8b97

Diff

@@ -162,12 +162,6 @@ section Monotone
 
 variable {n : ℕ} {α : Type uu} [Preorder α] {f : Fin n → α}
 
-/- warning: list.monotone_iff_of_fn_sorted -> List.monotone_iff_ofFn_sorted is a dubious translation:
-lean 3 declaration is
-  forall {n : Nat} {α : Type.{u1}} [_inst_1 : Preorder.{u1} α] {f : (Fin n) -> α}, Iff (Monotone.{0, u1} (Fin n) α (PartialOrder.toPreorder.{0} (Fin n) (Fin.partialOrder n)) _inst_1 f) (List.Sorted.{u1} α (LE.le.{u1} α (Preorder.toHasLe.{u1} α _inst_1)) (List.ofFn.{u1} α n f))
-but is expected to have type
-  forall {n : Nat} {α : Type.{u1}} [_inst_1 : Preorder.{u1} α] {f : (Fin n) -> α}, Iff (Monotone.{0, u1} (Fin n) α (PartialOrder.toPreorder.{0} (Fin n) (Fin.instPartialOrderFin n)) _inst_1 f) (List.Sorted.{u1} α (fun (x._@.Mathlib.Data.List.Sort._hyg.1419 : α) (x._@.Mathlib.Data.List.Sort._hyg.1421 : α) => LE.le.{u1} α (Preorder.toLE.{u1} α _inst_1) x._@.Mathlib.Data.List.Sort._hyg.1419 x._@.Mathlib.Data.List.Sort._hyg.1421) (List.ofFn.{u1} α n f))
-Case conversion may be inaccurate. Consider using '#align list.monotone_iff_of_fn_sorted List.monotone_iff_ofFn_sortedₓ'. -/
 /-- A tuple is monotone if and only if the list obtained from it is sorted. -/
 theorem monotone_iff_ofFn_sorted : Monotone f ↔ (ofFn f).Sorted (· ≤ ·) :=
   by
@@ -175,12 +169,6 @@ theorem monotone_iff_ofFn_sorted : Monotone f ↔ (ofFn f).Sorted (· ≤ ·) :=
   exact ⟨fun h i j hj hij => h <| fin.mk_lt_mk.mpr hij, fun h ⟨i, _⟩ ⟨j, hj⟩ hij => h i j hj hij⟩
 #align list.monotone_iff_of_fn_sorted List.monotone_iff_ofFn_sorted
 
-/- warning: list.monotone.of_fn_sorted -> Monotone.ofFn_sorted is a dubious translation:
-lean 3 declaration is
-  forall {n : Nat} {α : Type.{u1}} [_inst_1 : Preorder.{u1} α] {f : (Fin n) -> α}, (Monotone.{0, u1} (Fin n) α (PartialOrder.toPreorder.{0} (Fin n) (Fin.partialOrder n)) _inst_1 f) -> (List.Sorted.{u1} α (LE.le.{u1} α (Preorder.toHasLe.{u1} α _inst_1)) (List.ofFn.{u1} α n f))
-but is expected to have type
-  forall {n : Nat} {α : Type.{u1}} [_inst_1 : Preorder.{u1} α] {f : (Fin n) -> α}, (Monotone.{0, u1} (Fin n) α (PartialOrder.toPreorder.{0} (Fin n) (Fin.instPartialOrderFin n)) _inst_1 f) -> (List.Sorted.{u1} α (fun (x._@.Mathlib.Data.List.Sort._hyg.1378 : α) (x._@.Mathlib.Data.List.Sort._hyg.1380 : α) => LE.le.{u1} α (Preorder.toLE.{u1} α _inst_1) x._@.Mathlib.Data.List.Sort._hyg.1378 x._@.Mathlib.Data.List.Sort._hyg.1380) (List.ofFn.{u1} α n f))
-Case conversion may be inaccurate. Consider using '#align list.monotone.of_fn_sorted Monotone.ofFn_sortedₓ'. -/
 /-- The list obtained from a monotone tuple is sorted. -/
 theorem Monotone.ofFn_sorted (h : Monotone f) : (ofFn f).Sorted (· ≤ ·) :=
   monotone_iff_ofFn_sorted.1 h

327c3c0d

bump to nightly-2023-05-28-04

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

6797a637

Diff

@@ -101,9 +101,7 @@ theorem eq_of_perm_of_sorted [IsAntisymm α r] {l₁ l₂ : List α} (p : l₁ ~
     rcases mem_split this with ⟨u₂, v₂, rfl⟩
     have p' := (perm_cons a).1 (p.trans perm_middle)
     obtain rfl := IH p' (s₂.sublist <| by simp)
-    change a :: u₂ ++ v₂ = u₂ ++ ([a] ++ v₂)
-    rw [← append_assoc]
-    congr
+    change a :: u₂ ++ v₂ = u₂ ++ ([a] ++ v₂); rw [← append_assoc]; congr
     have : ∀ (x : α) (h : x ∈ u₂), x = a := fun x m =>
       antisymm ((pairwise_append.1 s₂).2.2 _ m a (mem_cons_self _ _)) (h₁ _ (by simp [m]))
     rw [(@eq_replicate _ a (length u₂ + 1) (a :: u₂)).2,
@@ -141,8 +139,7 @@ theorem Sorted.rel_nthLe_of_le [IsRefl α r] {l : List α} (h : l.Sorted r) {a b
     (ha : a < l.length) (hb : b < l.length) (hab : a ≤ b) : r (l.nthLe a ha) (l.nthLe b hb) :=
   by
   cases' eq_or_lt_of_le hab with H H
-  · subst H
-    exact refl _
+  · subst H; exact refl _
   · exact h.rel_nth_le_of_lt _ _ H
 #align list.sorted.rel_nth_le_of_le List.Sorted.rel_nthLe_of_le
 -/
@@ -232,9 +229,7 @@ theorem orderedInsert_nil (a : α) : [].orderedInsert r a = [a] :=
 #print List.orderedInsert_length /-
 theorem orderedInsert_length : ∀ (L : List α) (a : α), (L.orderedInsert r a).length = L.length + 1
   | [], a => rfl
-  | hd :: tl, a => by
-    dsimp [ordered_insert]
-    split_ifs <;> simp [ordered_insert_length]
+  | hd :: tl, a => by dsimp [ordered_insert]; split_ifs <;> simp [ordered_insert_length]
 #align list.ordered_insert_length List.orderedInsert_length
 -/
 
@@ -244,9 +239,7 @@ theorem orderedInsert_eq_take_drop (a : α) :
     ∀ l : List α,
       l.orderedInsert r a = (l.takeWhile fun b => ¬a ≼ b) ++ a :: l.dropWhileₓ fun b => ¬a ≼ b
   | [] => rfl
-  | b :: l => by
-    dsimp only [ordered_insert]
-    split_ifs <;> simp [take_while, drop_while, *]
+  | b :: l => by dsimp only [ordered_insert]; split_ifs <;> simp [take_while, drop_while, *]
 #align list.ordered_insert_eq_take_drop List.orderedInsert_eq_take_drop
 -/
 
@@ -319,8 +312,7 @@ theorem Sorted.orderedInsert (a : α) : ∀ l, Sorted r l → Sorted r (orderedI
         simpa [ordered_insert, h', h.of_cons.ordered_insert l]
       intro b' bm
       cases' show b' = a ∨ b' ∈ l by simpa using (perm_ordered_insert _ _ _).Subset bm with be bm
-      · subst b'
-        exact (total_of r _ _).resolve_left h'
+      · subst b'; exact (total_of r _ _).resolve_left h'
       · exact rel_of_sorted_cons h _ bm
 #align list.sorted.ordered_insert List.Sorted.orderedInsert
 -/
@@ -435,12 +427,8 @@ theorem mergeSort_cons_cons {a b} {l l₁ l₂ : List α} (h : split (a :: b ::
       @And.ndrec (fun a a (_ : length l₁ < length l + 1 + 1 ∧ length l₂ < length l + 1 + 1) => L) h1
           h1 =
         L
-    by
-    simp [merge_sort, h]
-    apply this
-  intros
-  cases h1
-  rfl
+    by simp [merge_sort, h]; apply this
+  intros ; cases h1; rfl
 #align list.merge_sort_cons_cons List.mergeSort_cons_cons
 -/
 
@@ -498,8 +486,7 @@ theorem Sorted.merge : ∀ {l l' : List α}, Sorted r l → Sorted r l' → Sort
       rcases show b' = b ∨ b' ∈ l ∨ b' ∈ l' by
           simpa [or_left_comm] using (perm_merge _ _ _).Subset bm with
         (be | bl | bl')
-      · subst b'
-        assumption
+      · subst b'; assumption
       · exact rel_of_sorted_cons h₁ _ bl
       · exact trans h (rel_of_sorted_cons h₂ _ bl')
     · suffices ∀ (b' : α) (_ : b' ∈ merge r (a :: l) l'), r b b' by
@@ -508,8 +495,7 @@ theorem Sorted.merge : ∀ {l l' : List α}, Sorted r l → Sorted r l' → Sort
       have ba : b ≼ a := (total_of r _ _).resolve_left h
       rcases show b' = a ∨ b' ∈ l ∨ b' ∈ l' by simpa using (perm_merge _ _ _).Subset bm with
         (be | bl | bl')
-      · subst b'
-        assumption
+      · subst b'; assumption
       · exact trans ba (rel_of_sorted_cons h₁ _ bl)
       · exact rel_of_sorted_cons h₂ _ bl'
 #align list.sorted.merge List.Sorted.merge

327c3c0d

bump to nightly-2023-05-24-06

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

fbc7b476

Diff

@@ -267,8 +267,9 @@ open Perm
 theorem perm_orderedInsert (a) : ∀ l : List α, orderedInsert r a l ~ a :: l
   | [] => Perm.refl _
   | b :: l => by
-    by_cases a ≼ b <;> [simp [ordered_insert, h],
-      simpa [ordered_insert, h] using ((perm_ordered_insert l).cons _).trans (perm.swap _ _ _)]
+    by_cases a ≼ b <;>
+      [simp [ordered_insert,
+        h];simpa [ordered_insert, h] using ((perm_ordered_insert l).cons _).trans (perm.swap _ _ _)]
 #align list.perm_ordered_insert List.perm_orderedInsert
 -/

327c3c0d

bump to nightly-2023-05-16-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/0b9eaaa7686280fad8cce467f5c3c57ee6ce77f8

9cb92e8c

Diff

@@ -167,7 +167,7 @@ variable {n : ℕ} {α : Type uu} [Preorder α] {f : Fin n → α}
 
 /- warning: list.monotone_iff_of_fn_sorted -> List.monotone_iff_ofFn_sorted is a dubious translation:
 lean 3 declaration is
-  forall {n : Nat} {α : Type.{u1}} [_inst_1 : Preorder.{u1} α] {f : (Fin n) -> α}, Iff (Monotone.{0, u1} (Fin n) α (PartialOrder.toPreorder.{0} (Fin n) (Fin.partialOrder n)) _inst_1 f) (List.Sorted.{u1} α (LE.le.{u1} α (Preorder.toLE.{u1} α _inst_1)) (List.ofFn.{u1} α n f))
+  forall {n : Nat} {α : Type.{u1}} [_inst_1 : Preorder.{u1} α] {f : (Fin n) -> α}, Iff (Monotone.{0, u1} (Fin n) α (PartialOrder.toPreorder.{0} (Fin n) (Fin.partialOrder n)) _inst_1 f) (List.Sorted.{u1} α (LE.le.{u1} α (Preorder.toHasLe.{u1} α _inst_1)) (List.ofFn.{u1} α n f))
 but is expected to have type
   forall {n : Nat} {α : Type.{u1}} [_inst_1 : Preorder.{u1} α] {f : (Fin n) -> α}, Iff (Monotone.{0, u1} (Fin n) α (PartialOrder.toPreorder.{0} (Fin n) (Fin.instPartialOrderFin n)) _inst_1 f) (List.Sorted.{u1} α (fun (x._@.Mathlib.Data.List.Sort._hyg.1419 : α) (x._@.Mathlib.Data.List.Sort._hyg.1421 : α) => LE.le.{u1} α (Preorder.toLE.{u1} α _inst_1) x._@.Mathlib.Data.List.Sort._hyg.1419 x._@.Mathlib.Data.List.Sort._hyg.1421) (List.ofFn.{u1} α n f))
 Case conversion may be inaccurate. Consider using '#align list.monotone_iff_of_fn_sorted List.monotone_iff_ofFn_sortedₓ'. -/
@@ -180,7 +180,7 @@ theorem monotone_iff_ofFn_sorted : Monotone f ↔ (ofFn f).Sorted (· ≤ ·) :=
 
 /- warning: list.monotone.of_fn_sorted -> Monotone.ofFn_sorted is a dubious translation:
 lean 3 declaration is
-  forall {n : Nat} {α : Type.{u1}} [_inst_1 : Preorder.{u1} α] {f : (Fin n) -> α}, (Monotone.{0, u1} (Fin n) α (PartialOrder.toPreorder.{0} (Fin n) (Fin.partialOrder n)) _inst_1 f) -> (List.Sorted.{u1} α (LE.le.{u1} α (Preorder.toLE.{u1} α _inst_1)) (List.ofFn.{u1} α n f))
+  forall {n : Nat} {α : Type.{u1}} [_inst_1 : Preorder.{u1} α] {f : (Fin n) -> α}, (Monotone.{0, u1} (Fin n) α (PartialOrder.toPreorder.{0} (Fin n) (Fin.partialOrder n)) _inst_1 f) -> (List.Sorted.{u1} α (LE.le.{u1} α (Preorder.toHasLe.{u1} α _inst_1)) (List.ofFn.{u1} α n f))
 but is expected to have type
   forall {n : Nat} {α : Type.{u1}} [_inst_1 : Preorder.{u1} α] {f : (Fin n) -> α}, (Monotone.{0, u1} (Fin n) α (PartialOrder.toPreorder.{0} (Fin n) (Fin.instPartialOrderFin n)) _inst_1 f) -> (List.Sorted.{u1} α (fun (x._@.Mathlib.Data.List.Sort._hyg.1378 : α) (x._@.Mathlib.Data.List.Sort._hyg.1380 : α) => LE.le.{u1} α (Preorder.toLE.{u1} α _inst_1) x._@.Mathlib.Data.List.Sort._hyg.1378 x._@.Mathlib.Data.List.Sort._hyg.1380) (List.ofFn.{u1} α n f))
 Case conversion may be inaccurate. Consider using '#align list.monotone.of_fn_sorted Monotone.ofFn_sortedₓ'. -/

327c3c0d

bump to nightly-2023-05-03-22

mathlib commit https://github.com/leanprover-community/mathlib/commit/36b8aa61ea7c05727161f96a0532897bd72aedab

aa7b8e08

Diff

@@ -169,7 +169,7 @@ variable {n : ℕ} {α : Type uu} [Preorder α] {f : Fin n → α}
 lean 3 declaration is
   forall {n : Nat} {α : Type.{u1}} [_inst_1 : Preorder.{u1} α] {f : (Fin n) -> α}, Iff (Monotone.{0, u1} (Fin n) α (PartialOrder.toPreorder.{0} (Fin n) (Fin.partialOrder n)) _inst_1 f) (List.Sorted.{u1} α (LE.le.{u1} α (Preorder.toLE.{u1} α _inst_1)) (List.ofFn.{u1} α n f))
 but is expected to have type
-  forall {n : Nat} {α : Type.{u1}} [_inst_1 : Preorder.{u1} α] {f : (Fin n) -> α}, Iff (Monotone.{0, u1} (Fin n) α (PartialOrder.toPreorder.{0} (Fin n) (Fin.instPartialOrderFin n)) _inst_1 f) (List.Sorted.{u1} α (fun (x._@.Mathlib.Data.List.Sort._hyg.1422 : α) (x._@.Mathlib.Data.List.Sort._hyg.1424 : α) => LE.le.{u1} α (Preorder.toLE.{u1} α _inst_1) x._@.Mathlib.Data.List.Sort._hyg.1422 x._@.Mathlib.Data.List.Sort._hyg.1424) (List.ofFn.{u1} α n f))
+  forall {n : Nat} {α : Type.{u1}} [_inst_1 : Preorder.{u1} α] {f : (Fin n) -> α}, Iff (Monotone.{0, u1} (Fin n) α (PartialOrder.toPreorder.{0} (Fin n) (Fin.instPartialOrderFin n)) _inst_1 f) (List.Sorted.{u1} α (fun (x._@.Mathlib.Data.List.Sort._hyg.1419 : α) (x._@.Mathlib.Data.List.Sort._hyg.1421 : α) => LE.le.{u1} α (Preorder.toLE.{u1} α _inst_1) x._@.Mathlib.Data.List.Sort._hyg.1419 x._@.Mathlib.Data.List.Sort._hyg.1421) (List.ofFn.{u1} α n f))
 Case conversion may be inaccurate. Consider using '#align list.monotone_iff_of_fn_sorted List.monotone_iff_ofFn_sortedₓ'. -/
 /-- A tuple is monotone if and only if the list obtained from it is sorted. -/
 theorem monotone_iff_ofFn_sorted : Monotone f ↔ (ofFn f).Sorted (· ≤ ·) :=
@@ -182,7 +182,7 @@ theorem monotone_iff_ofFn_sorted : Monotone f ↔ (ofFn f).Sorted (· ≤ ·) :=
 lean 3 declaration is
   forall {n : Nat} {α : Type.{u1}} [_inst_1 : Preorder.{u1} α] {f : (Fin n) -> α}, (Monotone.{0, u1} (Fin n) α (PartialOrder.toPreorder.{0} (Fin n) (Fin.partialOrder n)) _inst_1 f) -> (List.Sorted.{u1} α (LE.le.{u1} α (Preorder.toLE.{u1} α _inst_1)) (List.ofFn.{u1} α n f))
 but is expected to have type
-  forall {n : Nat} {α : Type.{u1}} [_inst_1 : Preorder.{u1} α] {f : (Fin n) -> α}, (Monotone.{0, u1} (Fin n) α (PartialOrder.toPreorder.{0} (Fin n) (Fin.instPartialOrderFin n)) _inst_1 f) -> (List.Sorted.{u1} α (fun (x._@.Mathlib.Data.List.Sort._hyg.1381 : α) (x._@.Mathlib.Data.List.Sort._hyg.1383 : α) => LE.le.{u1} α (Preorder.toLE.{u1} α _inst_1) x._@.Mathlib.Data.List.Sort._hyg.1381 x._@.Mathlib.Data.List.Sort._hyg.1383) (List.ofFn.{u1} α n f))
+  forall {n : Nat} {α : Type.{u1}} [_inst_1 : Preorder.{u1} α] {f : (Fin n) -> α}, (Monotone.{0, u1} (Fin n) α (PartialOrder.toPreorder.{0} (Fin n) (Fin.instPartialOrderFin n)) _inst_1 f) -> (List.Sorted.{u1} α (fun (x._@.Mathlib.Data.List.Sort._hyg.1378 : α) (x._@.Mathlib.Data.List.Sort._hyg.1380 : α) => LE.le.{u1} α (Preorder.toLE.{u1} α _inst_1) x._@.Mathlib.Data.List.Sort._hyg.1378 x._@.Mathlib.Data.List.Sort._hyg.1380) (List.ofFn.{u1} α n f))
 Case conversion may be inaccurate. Consider using '#align list.monotone.of_fn_sorted Monotone.ofFn_sortedₓ'. -/
 /-- The list obtained from a monotone tuple is sorted. -/
 theorem Monotone.ofFn_sorted (h : Monotone f) : (ofFn f).Sorted (· ≤ ·) :=

327c3c0d

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

@@ -5,6 +5,7 @@ Authors: Jeremy Avigad
 -/
 import Mathlib.Data.List.OfFn
 import Mathlib.Data.List.Nodup
+import Mathlib.Data.List.Infix
 
 #align_import data.list.sort 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

@@ -177,7 +177,7 @@ strictly monotone. -/
   sorted_ofFn_iff.trans monotone_iff_forall_lt.symm
 
 /-- A tuple is monotone if and only if the list obtained from it is sorted. -/
-@[deprecated sorted_le_ofFn_iff]
+@[deprecated sorted_le_ofFn_iff] -- 2023-01-10
 theorem monotone_iff_ofFn_sorted : Monotone f ↔ (ofFn f).Sorted (· ≤ ·) := sorted_le_ofFn_iff.symm
 #align list.monotone_iff_of_fn_sorted List.monotone_iff_ofFn_sorted

f694c7de

doc: fix references to List.Pairwise in List.Sorted docs (#12123)

9e99a83e

Diff

@@ -11,8 +11,9 @@ import Mathlib.Data.List.Nodup
 /-!
 # Sorting algorithms on lists
 
-In this file we define `List.Sorted r l` to be an alias for `Pairwise r l`. This alias is preferred
-in the case that `r` is a `<` or `≤`-like relation. Then we define two sorting algorithms:
+In this file we define `List.Sorted r l` to be an alias for `List.Pairwise r l`.
+This alias is preferred in the case that `r` is a `<` or `≤`-like relation.
+Then we define two sorting algorithms:
 `List.insertionSort` and `List.mergeSort`, and prove their correctness.
 -/
 
@@ -32,7 +33,7 @@ section Sorted
 
 variable {α : Type uu} {r : α → α → Prop} {a : α} {l : List α}
 
-/-- `Sorted r l` is the same as `Pairwise r l`, preferred in the case that `r`
+/-- `Sorted r l` is the same as `List.Pairwise r l`, preferred in the case that `r`
   is a `<` or `≤`-like relation (transitive and antisymmetric or asymmetric) -/
 def Sorted :=
   @Pairwise

f694c7de

chore: make List.mem_split an alias of List.append_of_mem (#11060)

List.mem_split duplicates List.append_of_mem from Std: https://github.com/leanprover/std4/blob/a756b7d643ae5dcd7bf314e99f8e493e5d81b9ed/Std/Data/List/Lemmas.lean#L94-L96

This PR makes it an alias.

Co-authored-by: Yaël Dillies <yael.dillies@gmail.com>

9682f6b2

Diff

@@ -104,7 +104,7 @@ theorem eq_of_perm_of_sorted [IsAntisymm α r] {l₁ l₂ : List α} (hp : l₁
   induction' hs₁ with a l₁ h₁ hs₁ IH generalizing l₂
   · exact hp.nil_eq
   · have : a ∈ l₂ := hp.subset (mem_cons_self _ _)
-    rcases mem_split this with ⟨u₂, v₂, rfl⟩
+    rcases append_of_mem this with ⟨u₂, v₂, rfl⟩
     have hp' := (perm_cons a).1 (hp.trans perm_middle)
     obtain rfl := IH hp' (hs₂.sublist <| by simp)
     change a :: u₂ ++ v₂ = u₂ ++ ([a] ++ v₂)

f694c7de

chore: remove unneeded decreasing_by and termination_by (#11386)

The termination checker has been getting more capable, and many of the termination_by or decreasing_by clauses in Mathlib are no longer needed.

(Note that termination_by? will show the automatically derived termination expression, so no information is being lost by removing these.)

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

c7950e4e

Diff

@@ -487,7 +487,6 @@ theorem Sorted.merge : ∀ {l l' : List α}, Sorted r l → Sorted r l' → Sort
         assumption
       · exact _root_.trans ba (rel_of_sorted_cons h₁ _ bl)
       · exact rel_of_sorted_cons h₂ _ bl'
-  termination_by l₁ l₂ => length l₁ + length l₂
 #align list.sorted.merge List.Sorted.merge
 
 variable (r)

f694c7de

fix: patch for std4#579 (#11347)

This if @fgdorais's patch for https://github.com/leanprover/std4/pull/579.

Co-authored-by: F. G. Dorais <fgdorais@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

526c94c0

Diff

@@ -412,14 +412,6 @@ theorem perm_split : ∀ {l l₁ l₂ : List α}, split l = (l₁, l₂) → l ~
     exact ((perm_split e).trans perm_append_comm).cons a
 #align list.perm_split List.perm_split
 
-/-- Merge two sorted lists into one in linear time.
-
-     merge [1, 2, 4, 5] [0, 1, 3, 4] = [0, 1, 1, 2, 3, 4, 4, 5] -/
-def merge : List α → List α → List α
-  | [], l' => l'
-  | l, [] => l
-  | a :: l, b :: l' => if a ≼ b then a :: merge l (b :: l') else b :: merge (a :: l) l'
-  termination_by l₁ l₂ => length l₁ + length l₂
 #align list.merge List.merge
 
 /-- Implementation of a merge sort algorithm to sort a list. -/
@@ -433,28 +425,18 @@ def mergeSort : List α → List α
     have h := length_split_lt e
     have := h.1
     have := h.2
-    exact merge r (mergeSort ls.1) (mergeSort ls.2)
+    exact merge (r · ·) (mergeSort ls.1) (mergeSort ls.2)
   termination_by l => length l
 #align list.merge_sort List.mergeSort
 
 @[nolint unusedHavesSuffices] -- Porting note: false positive
 theorem mergeSort_cons_cons {a b} {l l₁ l₂ : List α} (h : split (a :: b :: l) = (l₁, l₂)) :
-    mergeSort r (a :: b :: l) = merge r (mergeSort r l₁) (mergeSort r l₂) := by
+    mergeSort r (a :: b :: l) = merge (r · ·) (mergeSort r l₁) (mergeSort r l₂) := by
   simp only [mergeSort, h]
 #align list.merge_sort_cons_cons List.mergeSort_cons_cons
 
 section Correctness
 
-theorem perm_merge : ∀ l l' : List α, merge r l l' ~ l ++ l'
-  | [], [] => by simp [merge]
-  | [], b :: l' => by simp [merge]
-  | a :: l, [] => by simp [merge]
-  | a :: l, b :: l' => by
-    by_cases h : a ≼ b
-    · simpa [merge, h] using perm_merge _ _
-    · suffices b :: merge r (a :: l) l' ~ a :: (l ++ b :: l') by simpa [merge, h]
-      exact ((perm_merge _ _).cons _).trans ((swap _ _ _).trans (perm_middle.symm.cons _))
-  termination_by l₁ l₂ => length l₁ + length l₂
 #align list.perm_merge List.perm_merge
 
 theorem perm_mergeSort : ∀ l : List α, mergeSort r l ~ l
@@ -464,7 +446,7 @@ theorem perm_mergeSort : ∀ l : List α, mergeSort r l ~ l
     cases' e : split (a :: b :: l) with l₁ l₂
     cases' length_split_lt e with h₁ h₂
     rw [mergeSort_cons_cons r e]
-    apply (perm_merge r _ _).trans
+    apply (perm_merge (r · ·) _ _).trans
     exact
       ((perm_mergeSort l₁).append (perm_mergeSort l₂)).trans (perm_split e).symm
   termination_by l => length l
@@ -479,14 +461,14 @@ section TotalAndTransitive
 
 variable {r} [IsTotal α r] [IsTrans α r]
 
-theorem Sorted.merge : ∀ {l l' : List α}, Sorted r l → Sorted r l' → Sorted r (merge r l l')
-  | [], [], _, _ => by simp [List.merge]
-  | [], b :: l', _, h₂ => by simpa [List.merge] using h₂
-  | a :: l, [], h₁, _ => by simpa [List.merge] using h₁
+theorem Sorted.merge : ∀ {l l' : List α}, Sorted r l → Sorted r l' → Sorted r (merge (r · ·) l l')
+  | [], [], _, _ => by simp
+  | [], b :: l', _, h₂ => by simpa using h₂
+  | a :: l, [], h₁, _ => by simpa using h₁
   | a :: l, b :: l', h₁, h₂ => by
     by_cases h : a ≼ b
-    · suffices ∀ b' ∈ List.merge r l (b :: l'), r a b' by
-        simpa [List.merge, h, h₁.of_cons.merge h₂]
+    · suffices ∀ b' ∈ List.merge (r · ·) l (b :: l'), r a b' by
+        simpa [h, h₁.of_cons.merge h₂]
       intro b' bm
       rcases show b' = b ∨ b' ∈ l ∨ b' ∈ l' by
           simpa [or_left_comm] using (perm_merge _ _ _).subset bm with
@@ -495,8 +477,8 @@ theorem Sorted.merge : ∀ {l l' : List α}, Sorted r l → Sorted r l' → Sort
         assumption
       · exact rel_of_sorted_cons h₁ _ bl
       · exact _root_.trans h (rel_of_sorted_cons h₂ _ bl')
-    · suffices ∀ b' ∈ List.merge r (a :: l) l', r b b' by
-        simpa [List.merge, h, h₁.merge h₂.of_cons]
+    · suffices ∀ b' ∈ List.merge (r · ·) (a :: l) l', r b b' by
+        simpa [h, h₁.merge h₂.of_cons]
       intro b' bm
       have ba : b ≼ a := (total_of r _ _).resolve_left h
       have : b' = a ∨ b' ∈ l ∨ b' ∈ l' := by simpa using (perm_merge _ _ _).subset bm

f694c7de

feat: results about List.orderedInsert (#11191)

I suspect I will need some of these for #10660

0c4cb825

Diff

@@ -241,6 +241,17 @@ theorem insertionSort_cons_eq_take_drop (a : α) (l : List α) :
   orderedInsert_eq_take_drop r a _
 #align list.insertion_sort_cons_eq_take_drop List.insertionSort_cons_eq_take_drop
 
+@[simp]
+theorem mem_orderedInsert {a b : α} {l : List α} :
+    a ∈ orderedInsert r b l ↔ a = b ∨ a ∈ l :=
+  match l with
+  | [] => by simp [orderedInsert]
+  | x :: xs => by
+    rw [orderedInsert]
+    split_ifs
+    · simp [orderedInsert]
+    · rw [mem_cons, mem_cons, mem_orderedInsert, or_left_comm]
+
 section Correctness
 
 open Perm
@@ -276,6 +287,48 @@ theorem Sorted.insertionSort_eq : ∀ {l : List α}, Sorted r l → insertionSor
     exacts [rel_of_sorted_cons h _ (mem_cons_self _ _), h.tail]
 #align list.sorted.insertion_sort_eq List.Sorted.insertionSort_eq
 
+/-- For a reflexive relation, insert then erasing is the identity. -/
+theorem erase_orderedInsert [DecidableEq α] [IsRefl α r] (x : α) (xs : List α) :
+    (xs.orderedInsert r x).erase x = xs := by
+  rw [orderedInsert_eq_take_drop, erase_append_right, List.erase_cons_head,
+    takeWhile_append_dropWhile]
+  intro h
+  replace h := mem_takeWhile_imp h
+  simp [refl x] at h
+
+/-- Inserting then erasing an element that is absent is the identity. -/
+theorem erase_orderedInsert_of_not_mem [DecidableEq α]
+    {x : α} {xs : List α} (hx : x ∉ xs) :
+    (xs.orderedInsert r x).erase x = xs := by
+  rw [orderedInsert_eq_take_drop, erase_append_right, List.erase_cons_head,
+    takeWhile_append_dropWhile]
+  exact mt ((takeWhile_prefix _).sublist.subset ·) hx
+
+/-- For an antisymmetric relation, erasing then inserting is the identity. -/
+theorem orderedInsert_erase [DecidableEq α] [IsAntisymm α r] (x : α) (xs : List α) (hx : x ∈ xs)
+    (hxs : Sorted r xs) :
+    (xs.erase x).orderedInsert r x = xs := by
+  induction xs generalizing x with
+  | nil => cases hx
+  | cons y ys ih =>
+    rw [sorted_cons] at hxs
+    obtain rfl | hxy := Decidable.eq_or_ne x y
+    · rw [erase_cons_head]
+      cases ys with
+      | nil => rfl
+      | cons z zs =>
+        rw [orderedInsert, if_pos (hxs.1 _ (.head zs))]
+    · rw [mem_cons] at hx
+      replace hx := hx.resolve_left hxy
+      rw [erase_cons_tail _ (not_beq_of_ne hxy.symm), orderedInsert, ih _ hx hxs.2, if_neg]
+      refine mt (fun hrxy => ?_) hxy
+      exact antisymm hrxy (hxs.1 _ hx)
+
+theorem sublist_orderedInsert (x : α) (xs : List α) : xs <+ xs.orderedInsert r x := by
+  rw [orderedInsert_eq_take_drop]
+  refine Sublist.trans ?_ (.append_left (.cons _ (.refl _)) _)
+  rw [takeWhile_append_dropWhile]
+
 section TotalAndTransitive
 
 variable [IsTotal α r] [IsTrans α r]
@@ -291,7 +344,7 @@ theorem Sorted.orderedInsert (a : α) : ∀ l, Sorted r l → Sorted r (orderedI
     · suffices ∀ b' : α, b' ∈ List.orderedInsert r a l → r b b' by
         simpa [orderedInsert, h', h.of_cons.orderedInsert a l]
       intro b' bm
-      cases' show b' = a ∨ b' ∈ l by simpa using (perm_orderedInsert _ _ _).subset bm with be bm
+      cases' (mem_orderedInsert r).mp bm with be bm
       · subst b'
         exact (total_of r _ _).resolve_left h'
       · exact rel_of_sorted_cons h _ bm

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

@@ -124,7 +124,7 @@ theorem sublist_of_subperm_of_sorted [IsAntisymm α r] {l₁ l₂ : List α} (hp
   rwa [← eq_of_perm_of_sorted h (hs₂.sublist h') hs₁]
 #align list.sublist_of_subperm_of_sorted List.sublist_of_subperm_of_sorted
 
-@[simp 1100] --Porting note: higher priority for linter
+@[simp 1100] -- Porting note: higher priority for linter
 theorem sorted_singleton (a : α) : Sorted r [a] :=
   pairwise_singleton _ _
 #align list.sorted_singleton List.sorted_singleton
@@ -384,7 +384,7 @@ def mergeSort : List α → List α
   termination_by l => length l
 #align list.merge_sort List.mergeSort
 
-@[nolint unusedHavesSuffices] --Porting note: false positive
+@[nolint unusedHavesSuffices] -- Porting note: false positive
 theorem mergeSort_cons_cons {a b} {l l₁ l₂ : List α} (h : split (a :: b :: l) = (l₁, l₂)) :
     mergeSort r (a :: b :: l) = merge r (mergeSort r l₁) (mergeSort r l₂) := by
   simp only [mergeSort, h]

f694c7de

chore: move to v4.6.0-rc1, merging adaptations from bump/v4.6.0 (#10176)

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Joachim Breitner <mail@joachim-breitner.de>

490d2d48

Diff

@@ -366,7 +366,7 @@ def merge : List α → List α → List α
   | [], l' => l'
   | l, [] => l
   | a :: l, b :: l' => if a ≼ b then a :: merge l (b :: l') else b :: merge (a :: l) l'
-  termination_by merge l₁ l₂ => length l₁ + length l₂
+  termination_by l₁ l₂ => length l₁ + length l₂
 #align list.merge List.merge
 
 /-- Implementation of a merge sort algorithm to sort a list. -/
@@ -381,7 +381,7 @@ def mergeSort : List α → List α
     have := h.1
     have := h.2
     exact merge r (mergeSort ls.1) (mergeSort ls.2)
-  termination_by mergeSort l => length l
+  termination_by l => length l
 #align list.merge_sort List.mergeSort
 
 @[nolint unusedHavesSuffices] --Porting note: false positive
@@ -401,7 +401,7 @@ theorem perm_merge : ∀ l l' : List α, merge r l l' ~ l ++ l'
     · simpa [merge, h] using perm_merge _ _
     · suffices b :: merge r (a :: l) l' ~ a :: (l ++ b :: l') by simpa [merge, h]
       exact ((perm_merge _ _).cons _).trans ((swap _ _ _).trans (perm_middle.symm.cons _))
-  termination_by perm_merge l₁ l₂ => length l₁ + length l₂
+  termination_by l₁ l₂ => length l₁ + length l₂
 #align list.perm_merge List.perm_merge
 
 theorem perm_mergeSort : ∀ l : List α, mergeSort r l ~ l
@@ -414,7 +414,7 @@ theorem perm_mergeSort : ∀ l : List α, mergeSort r l ~ l
     apply (perm_merge r _ _).trans
     exact
       ((perm_mergeSort l₁).append (perm_mergeSort l₂)).trans (perm_split e).symm
-  termination_by perm_mergeSort l => length l
+  termination_by l => length l
 #align list.perm_merge_sort List.perm_mergeSort
 
 @[simp]
@@ -452,7 +452,7 @@ theorem Sorted.merge : ∀ {l l' : List α}, Sorted r l → Sorted r l' → Sort
         assumption
       · exact _root_.trans ba (rel_of_sorted_cons h₁ _ bl)
       · exact rel_of_sorted_cons h₂ _ bl'
-  termination_by Sorted.merge l₁ l₂ _ _ => length l₁ + length l₂
+  termination_by l₁ l₂ => length l₁ + length l₂
 #align list.sorted.merge List.Sorted.merge
 
 variable (r)
@@ -465,7 +465,7 @@ theorem sorted_mergeSort : ∀ l : List α, Sorted r (mergeSort r l)
     cases' length_split_lt e with h₁ h₂
     rw [mergeSort_cons_cons r e]
     exact (sorted_mergeSort l₁).merge (sorted_mergeSort l₂)
-  termination_by sorted_mergeSort l => length l
+  termination_by l => length l
 #align list.sorted_merge_sort List.sorted_mergeSort
 
 theorem mergeSort_eq_self [IsAntisymm α r] {l : List α} : Sorted r l → mergeSort r l = l :=

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

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Jeremy Avigad
 -/
 import Mathlib.Data.List.OfFn
-import Mathlib.Data.List.Perm
+import Mathlib.Data.List.Nodup
 
 #align_import data.list.sort from "leanprover-community/mathlib"@"f694c7dead66f5d4c80f446c796a5aad14707f0e"

f694c7de

chore(Data/List/Sort): names of assumptions not like names of data (#9324)

Co-authored-by: madvorak <dvorakmartinbridge@seznam.cz>

30667e28

Diff

@@ -99,29 +99,29 @@ protected theorem Sorted.nodup {r : α → α → Prop} [IsIrrefl α r] {l : Lis
   Pairwise.nodup h
 #align list.sorted.nodup List.Sorted.nodup
 
-theorem eq_of_perm_of_sorted [IsAntisymm α r] {l₁ l₂ : List α} (p : l₁ ~ l₂) (s₁ : Sorted r l₁)
-    (s₂ : Sorted r l₂) : l₁ = l₂ := by
-  induction' s₁ with a l₁ h₁ s₁ IH generalizing l₂
-  · exact p.nil_eq
-  · have : a ∈ l₂ := p.subset (mem_cons_self _ _)
+theorem eq_of_perm_of_sorted [IsAntisymm α r] {l₁ l₂ : List α} (hp : l₁ ~ l₂) (hs₁ : Sorted r l₁)
+    (hs₂ : Sorted r l₂) : l₁ = l₂ := by
+  induction' hs₁ with a l₁ h₁ hs₁ IH generalizing l₂
+  · exact hp.nil_eq
+  · have : a ∈ l₂ := hp.subset (mem_cons_self _ _)
     rcases mem_split this with ⟨u₂, v₂, rfl⟩
-    have p' := (perm_cons a).1 (p.trans perm_middle)
-    obtain rfl := IH p' (s₂.sublist <| by simp)
+    have hp' := (perm_cons a).1 (hp.trans perm_middle)
+    obtain rfl := IH hp' (hs₂.sublist <| by simp)
     change a :: u₂ ++ v₂ = u₂ ++ ([a] ++ v₂)
     rw [← append_assoc]
     congr
     have : ∀ x ∈ u₂, x = a := fun x m =>
-      antisymm ((pairwise_append.1 s₂).2.2 _ m a (mem_cons_self _ _)) (h₁ _ (by simp [m]))
+      antisymm ((pairwise_append.1 hs₂).2.2 _ m a (mem_cons_self _ _)) (h₁ _ (by simp [m]))
     rw [(@eq_replicate _ a (length u₂ + 1) (a :: u₂)).2,
-          (@eq_replicate _ a (length u₂ + 1) (u₂ ++ [a])).2] <;>
+        (@eq_replicate _ a (length u₂ + 1) (u₂ ++ [a])).2] <;>
         constructor <;>
       simp [iff_true_intro this, or_comm]
 #align list.eq_of_perm_of_sorted List.eq_of_perm_of_sorted
 
-theorem sublist_of_subperm_of_sorted [IsAntisymm α r] {l₁ l₂ : List α} (p : l₁ <+~ l₂)
-    (s₁ : l₁.Sorted r) (s₂ : l₂.Sorted r) : l₁ <+ l₂ := by
-  let ⟨_, h, h'⟩ := p
-  rwa [← eq_of_perm_of_sorted h (s₂.sublist h') s₁]
+theorem sublist_of_subperm_of_sorted [IsAntisymm α r] {l₁ l₂ : List α} (hp : l₁ <+~ l₂)
+    (hs₁ : l₁.Sorted r) (hs₂ : l₂.Sorted r) : l₁ <+ l₂ := by
+  let ⟨_, h, h'⟩ := hp
+  rwa [← eq_of_perm_of_sorted h (hs₂.sublist h') hs₁]
 #align list.sublist_of_subperm_of_sorted List.sublist_of_subperm_of_sorted
 
 @[simp 1100] --Porting note: higher priority for linter

f694c7de

chore(*): use ∃ x ∈ s, _ instead of ∃ (x) (_ : x ∈ s), _ (#9184)

Search for [∀∃].*(_ and manually replace some occurrences with more readable versions. In case of ∀, the new expressions are defeq to the old ones. In case of ∃, they differ by exists_prop.

In some rare cases, golf proofs that needed fixing.

14c72960

Diff

@@ -110,7 +110,7 @@ theorem eq_of_perm_of_sorted [IsAntisymm α r] {l₁ l₂ : List α} (p : l₁ ~
     change a :: u₂ ++ v₂ = u₂ ++ ([a] ++ v₂)
     rw [← append_assoc]
     congr
-    have : ∀ (x : α) (_ : x ∈ u₂), x = a := fun x m =>
+    have : ∀ x ∈ u₂, x = a := fun x m =>
       antisymm ((pairwise_append.1 s₂).2.2 _ m a (mem_cons_self _ _)) (h₁ _ (by simp [m]))
     rw [(@eq_replicate _ a (length u₂ + 1) (a :: u₂)).2,
           (@eq_replicate _ a (length u₂ + 1) (u₂ ++ [a])).2] <;>
@@ -268,7 +268,7 @@ variable {r}
 
 /-- If `l` is already `List.Sorted` with respect to `r`, then `insertionSort` does not change
 it. -/
-theorem Sorted.insertionSort_eq : ∀ {l : List α} (_ : Sorted r l), insertionSort r l = l
+theorem Sorted.insertionSort_eq : ∀ {l : List α}, Sorted r l → insertionSort r l = l
   | [], _ => rfl
   | [a], _ => rfl
   | a :: b :: l, h => by
@@ -432,7 +432,7 @@ theorem Sorted.merge : ∀ {l l' : List α}, Sorted r l → Sorted r l' → Sort
   | a :: l, [], h₁, _ => by simpa [List.merge] using h₁
   | a :: l, b :: l', h₁, h₂ => by
     by_cases h : a ≼ b
-    · suffices ∀ (b' : α) (_ : b' ∈ List.merge r l (b :: l')), r a b' by
+    · suffices ∀ b' ∈ List.merge r l (b :: l'), r a b' by
         simpa [List.merge, h, h₁.of_cons.merge h₂]
       intro b' bm
       rcases show b' = b ∨ b' ∈ l ∨ b' ∈ l' by
@@ -442,7 +442,7 @@ theorem Sorted.merge : ∀ {l l' : List α}, Sorted r l → Sorted r l' → Sort
         assumption
       · exact rel_of_sorted_cons h₁ _ bl
       · exact _root_.trans h (rel_of_sorted_cons h₂ _ bl')
-    · suffices ∀ (b' : α) (_ : b' ∈ List.merge r (a :: l) l'), r b b' by
+    · suffices ∀ b' ∈ List.merge r (a :: l) l', r b b' by
         simpa [List.merge, h, h₁.merge h₂.of_cons]
       intro b' bm
       have ba : b ≼ a := (total_of r _ _).resolve_left h

f694c7de

fix: patch for std4#197 (More add lemmas for Nat) (#6202)

d76f1524

Diff

@@ -154,7 +154,7 @@ theorem Sorted.rel_of_mem_take_of_mem_drop {l : List α} (h : List.Sorted r l) {
   obtain ⟨⟨ix, hix⟩, rfl⟩ := get_of_mem hx
   rw [get_take', get_drop']
   rw [length_take] at hix
-  exact h.rel_nthLe_of_lt _ _ (ix.lt_add_right _ _ (lt_min_iff.mp hix).left)
+  exact h.rel_nthLe_of_lt _ _ (Nat.lt_add_right _ (lt_min_iff.mp hix).left)
 #align list.sorted.rel_of_mem_take_of_mem_drop List.Sorted.rel_of_mem_take_of_mem_drop
 
 end Sorted

f694c7de

feat: gt versions of some lemmas about sorted lists and finsets (#7895)

1a79f4b2

Diff

@@ -50,6 +50,14 @@ protected theorem Sorted.lt_of_le [PartialOrder α] {l : List α} (h₁ : l.Sort
     (h₂ : l.Nodup) : l.Sorted (· < ·) :=
   h₁.imp₂ (fun _ _ => lt_of_le_of_ne) h₂
 
+protected theorem Sorted.ge_of_gt [Preorder α] {l : List α} (h : l.Sorted (· > ·)) :
+    l.Sorted (· ≥ ·) :=
+  h.imp le_of_lt
+
+protected theorem Sorted.gt_of_ge [PartialOrder α] {l : List α} (h₁ : l.Sorted (· ≥ ·))
+    (h₂ : l.Nodup) : l.Sorted (· > ·) :=
+  h₁.imp₂ (fun _ _ => lt_of_le_of_ne) <| by simp_rw [ne_comm]; exact h₂
+
 @[simp]
 theorem sorted_nil : Sorted r [] :=
   Pairwise.nil

f694c7de

feat: two small lemmas about ordered lists (#7829)

We prove that in a sorted list, the head! is the smallest element, and that if a list is lexicographically smaller than another list, then its head! is smaller than or equal to that of the other.

7db2b0a8

Diff

@@ -67,6 +67,20 @@ theorem rel_of_sorted_cons {a : α} {l : List α} : Sorted r (a :: l) → ∀ b
   rel_of_pairwise_cons
 #align list.rel_of_sorted_cons List.rel_of_sorted_cons
 
+theorem Sorted.head!_le [Inhabited α] [Preorder α] {a : α} {l : List α} (h : Sorted (· < ·) l)
+    (ha : a ∈ l) : l.head! ≤ a := by
+  rw [← List.cons_head!_tail (List.ne_nil_of_mem ha)] at h ha
+  cases ha
+  · exact le_rfl
+  · exact le_of_lt (rel_of_sorted_cons h a (by assumption))
+
+theorem Sorted.le_head! [Inhabited α] [Preorder α] {a : α} {l : List α} (h : Sorted (· > ·) l)
+    (ha : a ∈ l) : a ≤ l.head! := by
+  rw [← List.cons_head!_tail (List.ne_nil_of_mem ha)] at h ha
+  cases ha
+  · exact le_rfl
+  · exact le_of_lt (rel_of_sorted_cons h a (by assumption))
+
 @[simp]
 theorem sorted_cons {a : α} {l : List α} : Sorted r (a :: l) ↔ (∀ b ∈ l, r a b) ∧ Sorted r l :=
   pairwise_cons

f694c7de

chore: replace Fin.castIso and Fin.revPerm with Fin.cast and Fin.rev for the bump of Std (#5847)

Some theorems in Data.Fin.Basic are copied to Std at the recent commit in Std. These are written using Fin.cast and Fin.rev, so declarations using Fin.castIso and Fin.revPerm in Mathlib should be rewritten.

Co-authored-by: Pol'tta / Miyahara Kō <52843868+Komyyy@users.noreply.github.com> Co-authored-by: Johan Commelin <johan@commelin.net>

45b31dda

Diff

@@ -143,7 +143,7 @@ variable {n : ℕ} {α : Type uu} [Preorder α] {f : Fin n → α}
 
 theorem sorted_ofFn_iff {r : α → α → Prop} : (ofFn f).Sorted r ↔ ((· < ·) ⇒ r) f f := by
   simp_rw [Sorted, pairwise_iff_get, get_ofFn, Relator.LiftFun]
-  exact Iff.symm (Fin.castIso _).surjective.forall₂
+  exact Iff.symm (Fin.rightInverse_cast _).surjective.forall₂
 
 /-- The list `List.ofFn f` is strictly sorted with respect to `(· ≤ ·)` if and only if `f` is
 strictly monotone. -/

f694c7de

feat: patch for new alias command (#6172)

19e0ba92

Diff

@@ -159,7 +159,7 @@ theorem monotone_iff_ofFn_sorted : Monotone f ↔ (ofFn f).Sorted (· ≤ ·) :=
 #align list.monotone_iff_of_fn_sorted List.monotone_iff_ofFn_sorted
 
 /-- The list obtained from a monotone tuple is sorted. -/
-alias sorted_le_ofFn_iff ↔ _ _root_.Monotone.ofFn_sorted
+alias ⟨_, _root_.Monotone.ofFn_sorted⟩ := sorted_le_ofFn_iff
 #align list.monotone.of_fn_sorted Monotone.ofFn_sorted
 
 end Monotone

f694c7de

chore: bump Std (#6721)

This incorporates changes from https://github.com/leanprover-community/mathlib4/pull/6575

I have also renamed Multiset.countp to Multiset.countP for consistency.

Co-authored-by: James Gallichio <jamesgallicchio@gmail.com>

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

f59eee0e

Diff

@@ -234,7 +234,6 @@ theorem perm_orderedInsert (a) : ∀ l : List α, orderedInsert r a l ~ a :: l
 theorem orderedInsert_count [DecidableEq α] (L : List α) (a b : α) :
     count a (L.orderedInsert r b) = count a L + if a = b then 1 else 0 := by
   rw [(L.perm_orderedInsert r b).count_eq, count_cons]
-  split_ifs <;> simp only [Nat.succ_eq_add_one, add_zero]
 #align list.ordered_insert_count List.orderedInsert_count
 
 theorem perm_insertionSort : ∀ l : List α, insertionSort r l ~ l

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) 2016 Jeremy Avigad. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Jeremy Avigad
-
-! This file was ported from Lean 3 source module data.list.sort
-! 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.OfFn
 import Mathlib.Data.List.Perm
 
+#align_import data.list.sort from "leanprover-community/mathlib"@"f694c7dead66f5d4c80f446c796a5aad14707f0e"
+
 /-!
 # Sorting algorithms on lists

f694c7de

chore: cleanup whitespace (#5988)

Grepping for [^ .:{-] [^ :] and reviewing the results. Once I started I couldn't stop. :-)

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

12343aa5

Diff

@@ -51,7 +51,7 @@ protected theorem Sorted.le_of_lt [Preorder α] {l : List α} (h : l.Sorted (·
 
 protected theorem Sorted.lt_of_le [PartialOrder α] {l : List α} (h₁ : l.Sorted (· ≤ ·))
     (h₂ : l.Nodup) : l.Sorted (· < ·) :=
-  h₁.imp₂ (fun _ _ => lt_of_le_of_ne)  h₂
+  h₁.imp₂ (fun _ _ => lt_of_le_of_ne) h₂
 
 @[simp]
 theorem sorted_nil : Sorted r [] :=

f694c7de

chore: rename Fin.cast to Fin.castIso (#5584)

Co-authored-by: Parcly Taxel <reddeloostw@gmail.com>

b0bb2972

Diff

@@ -146,7 +146,7 @@ variable {n : ℕ} {α : Type uu} [Preorder α] {f : Fin n → α}
 
 theorem sorted_ofFn_iff {r : α → α → Prop} : (ofFn f).Sorted r ↔ ((· < ·) ⇒ r) f f := by
   simp_rw [Sorted, pairwise_iff_get, get_ofFn, Relator.LiftFun]
-  exact Iff.symm (Fin.cast _).surjective.forall₂
+  exact Iff.symm (Fin.castIso _).surjective.forall₂
 
 /-- The list `List.ofFn f` is strictly sorted with respect to `(· ≤ ·)` if and only if `f` is
 strictly monotone. -/

f694c7de

chore: add space after exacts (#4945)

Too often tempted to change these during other PRs, so doing a mass edit here.

Co-authored-by: Scott Morrison <scott.morrison@anu.edu.au>

bf799bb9

Diff

@@ -255,7 +255,7 @@ theorem Sorted.insertionSort_eq : ∀ {l : List α} (_ : Sorted r l), insertionS
   | [a], _ => rfl
   | a :: b :: l, h => by
     rw [insertionSort, Sorted.insertionSort_eq, orderedInsert, if_pos]
-    exacts[rel_of_sorted_cons h _ (mem_cons_self _ _), h.tail]
+    exacts [rel_of_sorted_cons h _ (mem_cons_self _ _), h.tail]
 #align list.sorted.insertion_sort_eq List.Sorted.insertionSort_eq
 
 section TotalAndTransitive

f694c7de

feat: implement intermediate state for simp_rw (#3738)

closes #3680, see https://leanprover.zulipchat.com/#narrow/stream/287929-mathlib4/topic/Stepping.20through.20simp_rw/near/326712986

ff334843

Diff

@@ -145,7 +145,7 @@ section Monotone
 variable {n : ℕ} {α : Type uu} [Preorder α] {f : Fin n → α}
 
 theorem sorted_ofFn_iff {r : α → α → Prop} : (ofFn f).Sorted r ↔ ((· < ·) ⇒ r) f f := by
-  simp_rw [Sorted, pairwise_iff_get, length_ofFn, get_ofFn, Relator.LiftFun]
+  simp_rw [Sorted, pairwise_iff_get, get_ofFn, Relator.LiftFun]
   exact Iff.symm (Fin.cast _).surjective.forall₂
 
 /-- The list `List.ofFn f` is strictly sorted with respect to `(· ≤ ·)` if and only if `f` is

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

@@ -435,7 +435,6 @@ theorem Sorted.merge : ∀ {l l' : List α}, Sorted r l → Sorted r l' → Sort
       · exact _root_.trans ba (rel_of_sorted_cons h₁ _ bl)
       · exact rel_of_sorted_cons h₂ _ bl'
   termination_by Sorted.merge l₁ l₂ _ _ => length l₁ + length l₂
-
 #align list.sorted.merge List.Sorted.merge
 
 variable (r)

f694c7de

chore: add missing hypothesis names to by_cases (#2679)

5d07683a

Diff

@@ -379,7 +379,7 @@ theorem perm_merge : ∀ l l' : List α, merge r l l' ~ l ++ l'
   | [], b :: l' => by simp [merge]
   | a :: l, [] => by simp [merge]
   | a :: l, b :: l' => by
-    by_cases a ≼ b
+    by_cases h : a ≼ b
     · simpa [merge, h] using perm_merge _ _
     · suffices b :: merge r (a :: l) l' ~ a :: (l ++ b :: l') by simpa [merge, h]
       exact ((perm_merge _ _).cons _).trans ((swap _ _ _).trans (perm_middle.symm.cons _))

f694c7de

feat: add lemmas about List.Sorted (#2311)

Add List.Sorted.le_of_lt and List.Sorted.lt_of_le (new).
Add List.Sorted.rel_get_of_lt and List.Sorted.rel_get_of_le (get versions of nthLe lemmas).
Add List.sorted_ofFn_iff, List.sorted_lt_ofFn_iff, and List.sorted_le_ofFn_iff (new).
Deprecate List.monotone_iff_ofFn_sorted in favor of List.sorted_le_ofFn_iff.
Rename List.Monotone.ofFn_sorted to Monotone.ofFn_sorted. In Lean 3, dot notation hf.of_fn_sorted used lift.monotone.of_fn_sorted if the list namespace is open. This is no longer the case in Lean 4.

4557f2c4

Diff

@@ -45,6 +45,14 @@ instance decidableSorted [DecidableRel r] (l : List α) : Decidable (Sorted r l)
   List.instDecidablePairwise _
 #align list.decidable_sorted List.decidableSorted
 
+protected theorem Sorted.le_of_lt [Preorder α] {l : List α} (h : l.Sorted (· < ·)) :
+    l.Sorted (· ≤ ·) :=
+  h.imp le_of_lt
+
+protected theorem Sorted.lt_of_le [PartialOrder α] {l : List α} (h₁ : l.Sorted (· ≤ ·))
+    (h₂ : l.Nodup) : l.Sorted (· < ·) :=
+  h₁.imp₂ (fun _ _ => lt_of_le_of_ne)  h₂
+
 @[simp]
 theorem sorted_nil : Sorted r [] :=
   Pairwise.nil
@@ -102,17 +110,23 @@ theorem sorted_singleton (a : α) : Sorted r [a] :=
   pairwise_singleton _ _
 #align list.sorted_singleton List.sorted_singleton
 
+theorem Sorted.rel_get_of_lt {l : List α} (h : l.Sorted r) {a b : Fin l.length} (hab : a < b) :
+    r (l.get a) (l.get b) :=
+  List.pairwise_iff_get.1 h _ _ hab
+
 theorem Sorted.rel_nthLe_of_lt {l : List α} (h : l.Sorted r) {a b : ℕ} (ha : a < l.length)
     (hb : b < l.length) (hab : a < b) : r (l.nthLe a ha) (l.nthLe b hb) :=
   List.pairwise_iff_get.1 h ⟨a, ha⟩ ⟨b, hb⟩ hab
 #align list.sorted.rel_nth_le_of_lt List.Sorted.rel_nthLe_of_lt
 
+theorem Sorted.rel_get_of_le [IsRefl α r] {l : List α} (h : l.Sorted r) {a b : Fin l.length}
+    (hab : a ≤ b) : r (l.get a) (l.get b) := by
+  rcases hab.eq_or_lt with (rfl | hlt)
+  exacts [refl _, h.rel_get_of_lt hlt]
+
 theorem Sorted.rel_nthLe_of_le [IsRefl α r] {l : List α} (h : l.Sorted r) {a b : ℕ}
-    (ha : a < l.length) (hb : b < l.length) (hab : a ≤ b) : r (l.nthLe a ha) (l.nthLe b hb) := by
-  cases' eq_or_lt_of_le hab with H H
-  · subst H
-    exact refl _
-  · exact h.rel_nthLe_of_lt _ _ H
+    (ha : a < l.length) (hb : b < l.length) (hab : a ≤ b) : r (l.nthLe a ha) (l.nthLe b hb) :=
+  h.rel_get_of_le hab
 #align list.sorted.rel_nth_le_of_le List.Sorted.rel_nthLe_of_le
 
 theorem Sorted.rel_of_mem_take_of_mem_drop {l : List α} (h : List.Sorted r l) {k : ℕ} {x y : α}
@@ -130,17 +144,26 @@ section Monotone
 
 variable {n : ℕ} {α : Type uu} [Preorder α] {f : Fin n → α}
 
+theorem sorted_ofFn_iff {r : α → α → Prop} : (ofFn f).Sorted r ↔ ((· < ·) ⇒ r) f f := by
+  simp_rw [Sorted, pairwise_iff_get, length_ofFn, get_ofFn, Relator.LiftFun]
+  exact Iff.symm (Fin.cast _).surjective.forall₂
+
+/-- The list `List.ofFn f` is strictly sorted with respect to `(· ≤ ·)` if and only if `f` is
+strictly monotone. -/
+@[simp] theorem sorted_lt_ofFn_iff : (ofFn f).Sorted (· < ·) ↔ StrictMono f := sorted_ofFn_iff
+
+/-- The list `List.ofFn f` is sorted with respect to `(· ≤ ·)` if and only if `f` is monotone. -/
+@[simp] theorem sorted_le_ofFn_iff : (ofFn f).Sorted (· ≤ ·) ↔ Monotone f :=
+  sorted_ofFn_iff.trans monotone_iff_forall_lt.symm
+
 /-- A tuple is monotone if and only if the list obtained from it is sorted. -/
-theorem monotone_iff_ofFn_sorted : Monotone f ↔ (ofFn f).Sorted (· ≤ ·) := by
-  simp_rw [Sorted, pairwise_iff_get, length_ofFn, get_ofFn, monotone_iff_forall_lt]
-  refine ⟨fun h i j hij => h <| Fin.mk_lt_mk.mpr hij, fun h ⟨i, hi⟩ ⟨j, hj⟩ hij => ?_⟩
-  exact h ⟨i, (length_ofFn f).symm ▸ hi⟩ ⟨j, (length_ofFn f).symm ▸ hj⟩ hij
+@[deprecated sorted_le_ofFn_iff]
+theorem monotone_iff_ofFn_sorted : Monotone f ↔ (ofFn f).Sorted (· ≤ ·) := sorted_le_ofFn_iff.symm
 #align list.monotone_iff_of_fn_sorted List.monotone_iff_ofFn_sorted
 
 /-- The list obtained from a monotone tuple is sorted. -/
-theorem Monotone.ofFn_sorted (h : Monotone f) : (ofFn f).Sorted (· ≤ ·) :=
-  monotone_iff_ofFn_sorted.1 h
-#align list.monotone.of_fn_sorted List.Monotone.ofFn_sorted
+alias sorted_le_ofFn_iff ↔ _ _root_.Monotone.ofFn_sorted
+#align list.monotone.of_fn_sorted Monotone.ofFn_sorted
 
 end Monotone

f694c7de

chore: update SHA sums (#2133)

Part of the List.repeat -> List.replicate refactor. On Mathlib 4 side, I removed mentions of List.repeat in #1475 and #1579

060d1a48

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Jeremy Avigad
 
 ! This file was ported from Lean 3 source module data.list.sort
-! leanprover-community/mathlib commit 9003f28797c0664a49e4179487267c494477d853
+! leanprover-community/mathlib commit f694c7dead66f5d4c80f446c796a5aad14707f0e
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/

9003f287

Feat: prove IsTrans α r → Trans r r r and Trans r r r → IsTrans α r (#1522)

Now Trans.trans conflicts with _root_.trans.

090fcabe

Diff

@@ -246,9 +246,7 @@ theorem Sorted.orderedInsert (a : α) : ∀ l, Sorted r l → Sorted r (orderedI
     · -- Porting note: was
       -- `simpa [orderedInsert, h', h] using fun b' bm => trans h' (rel_of_sorted_cons h _ bm)`
       rw [List.orderedInsert, if_pos h', sorted_cons]
-      refine ⟨fun c hc => ?_, h⟩
-      exact (mem_cons.mp hc).casesOn
-        (fun hc => hc ▸ h') (fun hc => trans h' (rel_of_sorted_cons h c hc))
+      exact ⟨forall_mem_cons.2 ⟨h', fun c hc => _root_.trans h' (rel_of_sorted_cons h _ hc)⟩, h⟩
     · suffices ∀ b' : α, b' ∈ List.orderedInsert r a l → r b b' by
         simpa [orderedInsert, h', h.of_cons.orderedInsert a l]
       intro b' bm
@@ -402,7 +400,7 @@ theorem Sorted.merge : ∀ {l l' : List α}, Sorted r l → Sorted r l' → Sort
       · subst b'
         assumption
       · exact rel_of_sorted_cons h₁ _ bl
-      · exact trans h (rel_of_sorted_cons h₂ _ bl')
+      · exact _root_.trans h (rel_of_sorted_cons h₂ _ bl')
     · suffices ∀ (b' : α) (_ : b' ∈ List.merge r (a :: l) l'), r b b' by
         simpa [List.merge, h, h₁.merge h₂.of_cons]
       intro b' bm
@@ -411,7 +409,7 @@ theorem Sorted.merge : ∀ {l l' : List α}, Sorted r l → Sorted r l' → Sort
       rcases this with (be | bl | bl')
       · subst b'
         assumption
-      · exact trans ba (rel_of_sorted_cons h₁ _ bl)
+      · exact _root_.trans ba (rel_of_sorted_cons h₁ _ bl)
       · exact rel_of_sorted_cons h₂ _ bl'
   termination_by Sorted.merge l₁ l₂ _ _ => length l₁ + length l₂

9003f287

feat: port Data.List.Sort (#1632)

Co-authored-by: ChrisHughes24 <chrishughes24@gmail.com>

9bff38a4

`data.list.sort` ⟷ `Mathlib.Data.List.Sort`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 2 + 148

data.list.sort ⟷ Mathlib.Data.List.Sort

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 2 + 148

`data.list.sort` ⟷ `Mathlib.Data.List.Sort`