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

d2d8742b

(last sync)

chore(logic/equiv/basic): Generalize Type to Sort (#18543)

This backports a change that was already made in mathlib4.

Indeed, mathport complains that the change was made, see the comments in https://github.com/leanprover-community/mathlib3port/blob/e3a205b1f51e409563e9e4294f41dd4df61f578a/Mathbin/Logic/Equiv/Basic.lean#L1729-L1735

By backporting this, we can deal with the fallout up-front rather than during porting.

Diff

@@ -246,23 +246,23 @@ mall id
 end
 
 /-- Auxiliary definition for `foldl_with_index`. -/
-def foldl_with_index_aux (f : ℕ → α → β → α) : ℕ → α → list β → α
+def foldl_with_index_aux {α : Sort*} {β : Type*} (f : ℕ → α → β → α) : ℕ → α → list β → α
 | _ a [] := a
 | i a (b :: l) := foldl_with_index_aux (i + 1) (f i a b) l
 
 /-- Fold a list from left to right as with `foldl`, but the combining function
 also receives each element's index. -/
-def foldl_with_index (f : ℕ → α → β → α) (a : α) (l : list β) : α :=
+def foldl_with_index {α : Sort*} {β : Type*} (f : ℕ → α → β → α) (a : α) (l : list β) : α :=
 foldl_with_index_aux f 0 a l
 
 /-- Auxiliary definition for `foldr_with_index`. -/
-def foldr_with_index_aux (f : ℕ → α → β → β) : ℕ → β → list α → β
+def foldr_with_index_aux {α : Type*} {β : Sort*} (f : ℕ → α → β → β) : ℕ → β → list α → β
 | _ b [] := b
 | i b (a :: l) := f i a (foldr_with_index_aux (i + 1) b l)
 
 /-- Fold a list from right to left as with `foldr`, but the combining function
 also receives each element's index. -/
-def foldr_with_index (f : ℕ → α → β → β) (b : β) (l : list α) : β :=
+def foldr_with_index {α : Type*} {β : Sort*} (f : ℕ → α → β → β) (b : β) (l : list α) : β :=
 foldr_with_index_aux f 0 b l
 
 /-- `find_indexes p l` is the list of indexes of elements of `l` that satisfy `p`. -/

1447cae8

chore(data/list): reorder arguments of list.nthd (#18182)

Sync it with List.getD in Mathlib 4.

Diff

@@ -76,14 +76,14 @@ def to_array (l : list α) : array l.length α :=
 
 /-- "default" `nth` function: returns `d` instead of `none` in the case
   that the index is out of bounds. -/
-def nthd (d : α) : Π (l : list α) (n : ℕ), α
-| []      _       := d
-| (x::xs) 0       := x
-| (x::xs) (n + 1) := nthd xs n
+def nthd : Π (l : list α) (n : ℕ) (d : α), α
+| []      _       d := d
+| (x::xs) 0       d := x
+| (x::xs) (n + 1) d := nthd xs n d
 
 /-- "inhabited" `nth` function: returns `default` instead of `none` in the case
   that the index is out of bounds. -/
-def inth [h : inhabited α] (l : list α) (n : nat) : α := nthd default l n
+def inth [h : inhabited α] (l : list α) (n : nat) : α := nthd l n default
 
 /-- Apply a function to the nth tail of `l`. Returns the input without
   using `f` if the index is larger than the length of the list.

f694c7de

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

@@ -25,6 +25,11 @@ variables {α β γ δ ε ζ : Type*}
 instance [decidable_eq α] : has_sdiff (list α) :=
 ⟨ list.diff ⟩
 
+/-- Create a list of `n` copies of `a`. Same as `function.swap list.repeat`. -/
+@[simp] def replicate : ℕ → α → list α
+| 0 _ := []
+| (succ n) a := a :: replicate n a
+
 /-- Split a list at an index.
 
      split_at 2 [a, b, c] = ([a, b], [c]) -/

1fc36cc9

(first ported)

Changes in mathlib3port

mathlib3

mathlib3port

d2d8742b

bump to nightly-2024-02-05-08

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

516c6ec2

Diff

@@ -683,7 +683,7 @@ private def meas : (Σ' _ : List α, List α) → ℕ × ℕ
 
 local infixl:50 " ≺ " => InvImage (Prod.Lex (· < ·) (· < ·)) meas
 
-/- ./././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.permutationsAux.rec /-
 /-- A recursor for pairs of lists. To have `C l₁ l₂` for all `l₁`, `l₂`, it suffices to have it for
 `l₂ = []` and to be able to pour the elements of `l₁` into `l₂`. -/
@@ -699,8 +699,7 @@ def permutationsAux.rec {C : List α → List α → Sort v} (H0 : ∀ is, C []
         by rw [Nat.succ_add] <;> exact Prod.Lex.right _ (lt_succ_self _)
     have h2 : ⟨is, []⟩ ≺ ⟨t :: ts, is⟩ := Prod.Lex.left _ _ (Nat.lt_add_of_pos_left (succ_pos _))
     H1 t ts is (permutations_aux.rec ts (t :: is)) (permutations_aux.rec is [])
-termination_by
-  _ x =>
+termination_by x =>
   WellFounded.wrap (r := (· ≺ ·)) (@InvImage.wf _ _ _ meas (WellFounded.prod_lex lt_wf lt_wf)) x
 #align list.permutations_aux.rec List.permutationsAux.rec
 -/

d2d8742b

bump to nightly-2023-12-23-06

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

b8c74971

Diff

@@ -683,6 +683,7 @@ private def meas : (Σ' _ : List α, List α) → ℕ × ℕ
 
 local infixl:50 " ≺ " => InvImage (Prod.Lex (· < ·) (· < ·)) meas
 
+/- ./././Mathport/Syntax/Translate/Command.lean:298:8: warning: using_well_founded used, estimated equivalent -/
 #print List.permutationsAux.rec /-
 /-- A recursor for pairs of lists. To have `C l₁ l₂` for all `l₁`, `l₂`, it suffices to have it for
 `l₂ = []` and to be able to pour the elements of `l₁` into `l₂`. -/
@@ -698,7 +699,9 @@ def permutationsAux.rec {C : List α → List α → Sort v} (H0 : ∀ is, C []
         by rw [Nat.succ_add] <;> exact Prod.Lex.right _ (lt_succ_self _)
     have h2 : ⟨is, []⟩ ≺ ⟨t :: ts, is⟩ := Prod.Lex.left _ _ (Nat.lt_add_of_pos_left (succ_pos _))
     H1 t ts is (permutations_aux.rec ts (t :: is)) (permutations_aux.rec is [])
-termination_by' ⟨(· ≺ ·), @InvImage.wf _ _ _ meas (WellFounded.prod_lex lt_wf lt_wf)⟩
+termination_by
+  _ x =>
+  WellFounded.wrap (r := (· ≺ ·)) (@InvImage.wf _ _ _ meas (WellFounded.prod_lex lt_wf lt_wf)) x
 #align list.permutations_aux.rec List.permutationsAux.rec
 -/

d2d8742b

bump to nightly-2023-10-24-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/3365b20c2ffa7c35e47e5209b89ba9abdddf3ffe

5b21425a

Diff

@@ -616,15 +616,15 @@ attribute [simp] forall₂.nil
 
 end Forall₂
 
-#print List.All₂ /-
+#print List.Forall /-
 /-- `l.all₂ p` is equivalent to `∀ a ∈ l, p a`, but unfolds directly to a conjunction, i.e.
 `list.all₂ p [0, 1, 2] = p 0 ∧ p 1 ∧ p 2`. -/
 @[simp]
-def All₂ (p : α → Prop) : List α → Prop
+def Forall (p : α → Prop) : List α → Prop
   | [] => True
   | x :: [] => p x
   | x :: l => p x ∧ all₂ l
-#align list.all₂ List.All₂
+#align list.all₂ List.Forall
 -/
 
 /-- Auxiliary definition used to define `transpose`.

d2d8742b

bump to nightly-2023-10-13-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/19c869efa56bbb8b500f2724c0b77261edbfa28c

a17c86c6

Diff

@@ -505,35 +505,35 @@ def count [DecidableEq α] (a : α) : List α → Nat :=
 #align list.count List.count
 -/
 
-#print List.isPrefix /-
+#print List.IsPrefix /-
 /-- `is_prefix l₁ l₂`, or `l₁ <+: l₂`, means that `l₁` is a prefix of `l₂`,
   that is, `l₂` has the form `l₁ ++ t` for some `t`. -/
-def isPrefix (l₁ : List α) (l₂ : List α) : Prop :=
+def IsPrefix (l₁ : List α) (l₂ : List α) : Prop :=
   ∃ t, l₁ ++ t = l₂
-#align list.is_prefix List.isPrefix
+#align list.is_prefix List.IsPrefix
 -/
 
-#print List.isSuffix /-
+#print List.IsSuffix /-
 /-- `is_suffix l₁ l₂`, or `l₁ <:+ l₂`, means that `l₁` is a suffix of `l₂`,
   that is, `l₂` has the form `t ++ l₁` for some `t`. -/
-def isSuffix (l₁ : List α) (l₂ : List α) : Prop :=
+def IsSuffix (l₁ : List α) (l₂ : List α) : Prop :=
   ∃ t, t ++ l₁ = l₂
-#align list.is_suffix List.isSuffix
+#align list.is_suffix List.IsSuffix
 -/
 
-#print List.isInfix /-
+#print List.IsInfix /-
 /-- `is_infix l₁ l₂`, or `l₁ <:+: l₂`, means that `l₁` is a contiguous
   substring of `l₂`, that is, `l₂` has the form `s ++ l₁ ++ t` for some `s, t`. -/
-def isInfix (l₁ : List α) (l₂ : List α) : Prop :=
+def IsInfix (l₁ : List α) (l₂ : List α) : Prop :=
   ∃ s t, s ++ l₁ ++ t = l₂
-#align list.is_infix List.isInfix
+#align list.is_infix List.IsInfix
 -/
 
-infixl:50 " <+: " => isPrefix
+infixl:50 " <+: " => IsPrefix
 
-infixl:50 " <:+ " => isSuffix
+infixl:50 " <:+ " => IsSuffix
 
-infixl:50 " <:+: " => isInfix
+infixl:50 " <:+: " => IsInfix
 
 #print List.inits /-
 /-- `inits l` is the list of initial segments of `l`.

d2d8742b

bump to nightly-2023-09-24-06

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

5655435f

Diff

@@ -3,10 +3,10 @@ Copyright (c) 2014 Parikshit Khanna. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Parikshit Khanna, Jeremy Avigad, Leonardo de Moura, Floris van Doorn, Mario Carneiro
 -/
-import Mathbin.Logic.Basic
-import Mathbin.Tactic.Cache
-import Mathbin.Data.Rbmap.Basic
-import Mathbin.Data.Rbtree.DefaultLt
+import Logic.Basic
+import Tactic.Cache
+import Data.Rbmap.Basic
+import Data.Rbtree.DefaultLt
 
 #align_import data.list.defs from "leanprover-community/mathlib"@"d2d8742b0c21426362a9dacebc6005db895ca963"

d2d8742b

bump to nightly-2023-08-23-23

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

f612b9e0

Diff

@@ -490,18 +490,18 @@ def lookmap (f : α → Option α) : List α → List α
 #align list.lookmap List.lookmap
 -/
 
-#print List.countp /-
+#print List.countP /-
 /-- `countp p l` is the number of elements of `l` that satisfy `p`. -/
-def countp (p : α → Prop) [DecidablePred p] : List α → Nat
+def countP (p : α → Prop) [DecidablePred p] : List α → Nat
   | [] => 0
   | x :: xs => if p x then succ (countp xs) else countp xs
-#align list.countp List.countp
+#align list.countp List.countP
 -/
 
 #print List.count /-
 /-- `count a l` is the number of occurrences of `a` in `l`. -/
 def count [DecidableEq α] (a : α) : List α → Nat :=
-  countp (Eq a)
+  countP (Eq a)
 #align list.count List.count
 -/

d2d8742b

bump to nightly-2023-07-20-09

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

9c56d0dd

Diff

@@ -2,17 +2,14 @@
 Copyright (c) 2014 Parikshit Khanna. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Parikshit Khanna, Jeremy Avigad, Leonardo de Moura, Floris van Doorn, Mario Carneiro
-
-! This file was ported from Lean 3 source module data.list.defs
-! leanprover-community/mathlib commit d2d8742b0c21426362a9dacebc6005db895ca963
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Logic.Basic
 import Mathbin.Tactic.Cache
 import Mathbin.Data.Rbmap.Basic
 import Mathbin.Data.Rbtree.DefaultLt
 
+#align_import data.list.defs from "leanprover-community/mathlib"@"d2d8742b0c21426362a9dacebc6005db895ca963"
+
 /-!
 ## Definitions on lists

d2d8742b

bump to nightly-2023-06-13-21

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

829520ac

Diff

@@ -64,17 +64,21 @@ def splitOnPAux {α : Type u} (P : α → Prop) [DecidablePred P] :
   | h :: t, f => if P h then f [] :: split_on_p_aux t id else split_on_p_aux t fun l => f (h :: l)
 #align list.split_on_p_aux List.splitOnPAux
 
+#print List.splitOnP /-
 /-- Split a list at every element satisfying a predicate. -/
 def splitOnP {α : Type u} (P : α → Prop) [DecidablePred P] (l : List α) : List (List α) :=
   splitOnPAux P l id
 #align list.split_on_p List.splitOnP
+-/
 
+#print List.splitOn /-
 /-- Split a list at every occurrence of an element.
 
     [1,1,2,3,2,4,4].split_on 2 = [[1,1],[3],[4,4]] -/
 def splitOn {α : Type u} [DecidableEq α] (a : α) (as : List α) : List (List α) :=
   as.splitOnP (· = a)
 #align list.split_on List.splitOn
+-/
 
 #print List.concat /-
 /-- Concatenate an element at the end of a list.
@@ -97,9 +101,11 @@ def head? : List α → Option α
 #align list.head' List.head?
 -/
 
+#print List.toArray /-
 /-- Convert a list into an array (whose length is the length of `l`). -/
 def toArray (l : List α) : Array' l.length α where data v := l.nthLe v.1 v.2
 #align list.to_array List.toArray
+-/
 
 #print List.getD /-
 /-- "default" `nth` function: returns `d` instead of `none` in the case
@@ -181,6 +187,7 @@ def takeI : ∀ n, List α → List α
 
 end Take'
 
+#print List.takeWhile /-
 /-- Get the longest initial segment of the list whose members all satisfy `p`.
 
      take_while (λ x, x < 3) [0, 2, 5, 1] = [0, 2] -/
@@ -188,6 +195,7 @@ def takeWhile (p : α → Prop) [DecidablePred p] : List α → List α
   | [] => []
   | a :: l => if p a then a :: take_while l else []
 #align list.take_while List.takeWhile
+-/
 
 #print List.scanl /-
 /-- Fold a function `f` over the list from the left, returning the list
@@ -272,18 +280,22 @@ def partitionMap (f : α → Sum β γ) : List α → List β × List γ
 #align list.partition_map List.partitionMap
 -/
 
+#print List.find? /-
 /-- `find p l` is the first element of `l` satisfying `p`, or `none` if no such
   element exists. -/
 def find? (p : α → Prop) [DecidablePred p] : List α → Option α
   | [] => none
   | a :: l => if p a then some a else find l
 #align list.find List.find?
+-/
 
+#print List.findM /-
 /-- `mfind tac l` returns the first element of `l` on which `tac` succeeds, and
 fails otherwise. -/
 def findM {α} {m : Type u → Type v} [Monad m] [Alternative m] (tac : α → m PUnit) : List α → m α :=
   List.firstM fun a => tac a $> a
 #align list.mfind List.findM
+-/
 
 #print List.findM?' /-
 /-- `mbfind' p l` returns the first element `a` of `l` for which `p a` returns
@@ -309,6 +321,7 @@ def findM? {α} (p : α → m Bool) (xs : List α) : m (Option α) :=
 #align list.mbfind List.findM?
 -/
 
+#print List.anyM /-
 -- Implementing this via `mbfind` would give us less universe polymorphism.
 /-- `many p as` returns true iff `p` returns true for any element of `l`.
 `many` short-circuits, so if `p` returns true for any element of `l`, later
@@ -319,13 +332,16 @@ def anyM {α : Type u} (p : α → m Bool) : List α → m Bool
     let px ← p x
     if px then pure tt else many xs
 #align list.many List.anyM
+-/
 
+#print List.allM /-
 /-- `mall p as` returns true iff `p` returns true for all elements of `l`.
 `mall` short-circuits, so if `p` returns false for any element of `l`, later
 elements are not checked. This is a monadic version of `list.all`. -/
 def allM {α : Type u} (p : α → m Bool) (as : List α) : m Bool :=
   not <$> anyM (fun a => not <$> p a) as
 #align list.mall List.allM
+-/
 
 #print List.orM /-
 /-- `mbor xs` runs the actions in `xs`, returning true if any of them returns
@@ -353,11 +369,13 @@ def foldlWithIndexAux {α : Sort _} {β : Type _} (f : ℕ → α → β → α)
   | i, a, b :: l => foldl_with_index_aux (i + 1) (f i a b) l
 #align list.foldl_with_index_aux List.foldlWithIndexAux
 
+#print List.foldlIdx /-
 /-- Fold a list from left to right as with `foldl`, but the combining function
 also receives each element's index. -/
 def foldlIdx {α : Sort _} {β : Type _} (f : ℕ → α → β → α) (a : α) (l : List β) : α :=
   foldlWithIndexAux f 0 a l
 #align list.foldl_with_index List.foldlIdx
+-/
 
 /-- Auxiliary definition for `foldr_with_index`. -/
 def foldrWithIndexAux {α : Type _} {β : Sort _} (f : ℕ → α → β → β) : ℕ → β → List α → β
@@ -365,23 +383,30 @@ def foldrWithIndexAux {α : Type _} {β : Sort _} (f : ℕ → α → β → β)
   | i, b, a :: l => f i a (foldr_with_index_aux (i + 1) b l)
 #align list.foldr_with_index_aux List.foldrWithIndexAux
 
+#print List.foldrIdx /-
 /-- Fold a list from right to left as with `foldr`, but the combining function
 also receives each element's index. -/
 def foldrIdx {α : Type _} {β : Sort _} (f : ℕ → α → β → β) (b : β) (l : List α) : β :=
   foldrWithIndexAux f 0 b l
 #align list.foldr_with_index List.foldrIdx
+-/
 
+#print List.findIdxs /-
 /-- `find_indexes p l` is the list of indexes of elements of `l` that satisfy `p`. -/
 def findIdxs (p : α → Prop) [DecidablePred p] (l : List α) : List Nat :=
   foldrIdx (fun i a is => if p a then i :: is else is) [] l
 #align list.find_indexes List.findIdxs
+-/
 
+#print List.indexesValues /-
 /-- Returns the elements of `l` that satisfy `p` together with their indexes in
 `l`. The returned list is ordered by index. -/
 def indexesValues (p : α → Prop) [DecidablePred p] (l : List α) : List (ℕ × α) :=
   foldrIdx (fun i a l => if p a then (i, a) :: l else l) [] l
 #align list.indexes_values List.indexesValues
+-/
 
+#print List.indexesOf /-
 /-- `indexes_of a l` is the list of all indexes of `a` in `l`. For example:
 ```
 indexes_of a [a, b, a, a] = [0, 2, 3]
@@ -390,6 +415,7 @@ indexes_of a [a, b, a, a] = [0, 2, 3]
 def indexesOf [DecidableEq α] (a : α) : List α → List Nat :=
   findIdxs (Eq a)
 #align list.indexes_of List.indexesOf
+-/
 
 section MfoldWithIndex
 
@@ -429,22 +455,28 @@ def mmapWithIndexAux {α β} (f : ℕ → α → m β) : ℕ → List α → m (
   | i, a :: as => List.cons <$> f i a <*> mmap_with_index_aux (i + 1) as
 #align list.mmap_with_index_aux List.mmapWithIndexAux
 
+#print List.mapIdxM /-
 /-- Applicative variant of `map_with_index`. -/
 def mapIdxM {α β} (f : ℕ → α → m β) (as : List α) : m (List β) :=
   mmapWithIndexAux f 0 as
 #align list.mmap_with_index List.mapIdxM
+-/
 
+#print List.mapIdxMAux' /-
 /-- Auxiliary definition for `mmap_with_index'`. -/
 def mapIdxMAux' {α} (f : ℕ → α → m PUnit) : ℕ → List α → m PUnit
   | _, [] => pure ⟨⟩
   | i, a :: as => f i a *> mmap_with_index'_aux (i + 1) as
 #align list.mmap_with_index'_aux List.mapIdxMAux'
+-/
 
+#print List.mapIdxM' /-
 /-- A variant of `mmap_with_index` specialised to applicative actions which
 return `unit`. -/
 def mapIdxM' {α} (f : ℕ → α → m PUnit) (as : List α) : m PUnit :=
   mapIdxMAux' f 0 as
 #align list.mmap_with_index' List.mapIdxM'
+-/
 
 end MmapWithIndex
 
@@ -461,16 +493,20 @@ def lookmap (f : α → Option α) : List α → List α
 #align list.lookmap List.lookmap
 -/
 
+#print List.countp /-
 /-- `countp p l` is the number of elements of `l` that satisfy `p`. -/
 def countp (p : α → Prop) [DecidablePred p] : List α → Nat
   | [] => 0
   | x :: xs => if p x then succ (countp xs) else countp xs
 #align list.countp List.countp
+-/
 
+#print List.count /-
 /-- `count a l` is the number of occurrences of `a` in `l`. -/
 def count [DecidableEq α] (a : α) : List α → Nat :=
   countp (Eq a)
 #align list.count List.count
+-/
 
 #print List.isPrefix /-
 /-- `is_prefix l₁ l₂`, or `l₁ <+: l₂`, means that `l₁` is a prefix of `l₂`,
@@ -496,13 +532,10 @@ def isInfix (l₁ : List α) (l₂ : List α) : Prop :=
 #align list.is_infix List.isInfix
 -/
 
--- mathport name: «expr <+: »
 infixl:50 " <+: " => isPrefix
 
--- mathport name: «expr <:+ »
 infixl:50 " <:+ " => isSuffix
 
--- mathport name: «expr <:+: »
 infixl:50 " <:+: " => isInfix
 
 #print List.inits /-
@@ -527,10 +560,12 @@ def tails : List α → List (List α)
 #align list.tails List.tails
 -/
 
+#print List.sublists'Aux /-
 def sublists'Aux : List α → (List α → List β) → List (List β) → List (List β)
   | [], f, r => f [] :: r
   | a :: l, f, r => sublists'_aux l f (sublists'_aux l (f ∘ cons a) r)
 #align list.sublists'_aux List.sublists'Aux
+-/
 
 #print List.sublists' /-
 /-- `sublists' l` is the list of all (non-contiguous) sublists of `l`.
@@ -544,10 +579,12 @@ def sublists' (l : List α) : List (List α) :=
 #align list.sublists' List.sublists'
 -/
 
+#print List.sublistsAux /-
 def sublistsAux : List α → (List α → List β → List β) → List β
   | [], f => []
   | a :: l, f => f [a] (sublists_aux l fun ys r => f ys (f (a :: ys) r))
 #align list.sublists_aux List.sublistsAux
+-/
 
 #print List.sublists /-
 /-- `sublists l` is the list of all (non-contiguous) sublists of `l`; cf. `sublists'`
@@ -647,7 +684,6 @@ def permutationsAux2 (t : α) (ts : List α) (r : List β) : List α → (List 
 private def meas : (Σ' _ : List α, List α) → ℕ × ℕ
   | ⟨l, i⟩ => (length l + length i, length l)
 
--- mathport name: «expr ≺ »
 local infixl:50 " ≺ " => InvImage (Prod.Lex (· < ·) (· < ·)) meas
 
 #print List.permutationsAux.rec /-
@@ -764,7 +800,6 @@ def product (l₁ : List α) (l₂ : List β) : List (α × β) :=
 #align list.product List.product
 -/
 
--- mathport name: list.product
 infixr:82
   " ×ˢ " =>-- This notation binds more strongly than (pre)images, unions and intersections.
   List.product
@@ -955,6 +990,7 @@ def destutter (R : α → α → Prop) [DecidableRel R] : List α → List α
 #align list.destutter List.destutter
 -/
 
+#print List.range' /-
 /-- `range' s n` is the list of numbers `[s, s+1, ..., s+n-1]`.
   It is intended mainly for proving properties of `range` and `iota`. -/
 @[simp]
@@ -962,6 +998,7 @@ def range' : ℕ → ℕ → List ℕ
   | s, 0 => []
   | s, n + 1 => s :: range' (s + 1) n
 #align list.range' List.range'
+-/
 
 #print List.reduceOption /-
 /-- Drop `none`s from a list, and replace each remaining `some a` with `a`. -/
@@ -1040,6 +1077,7 @@ def choose (hp : ∃ a, a ∈ l ∧ p a) : α :=
 
 end Choose
 
+#print List.filterMapM /-
 /-- Filters and maps elements of a list -/
 def filterMapM {m : Type → Type v} [Monad m] {α β} (f : α → m (Option β)) : List α → m (List β)
   | [] => return []
@@ -1051,7 +1089,9 @@ def filterMapM {m : Type → Type v} [Monad m] {α β} (f : α → m (Option β)
         | none => t'
         | some x => x :: t'
 #align list.mmap_filter List.filterMapM
+-/
 
+#print List.mapDiagM /-
 /-- `mmap_upper_triangle f l` calls `f` on all elements in the upper triangular part of `l × l`.
 That is, for each `e ∈ l`, it will run `f e e` and then `f e e'`
 for each `e'` that appears after `e` in `l`.
@@ -1067,6 +1107,7 @@ def mapDiagM {m} [Monad m] {α β : Type u} (f : α → α → m β) : List α 
     let t ← t.mapDiagM
     return <| v :: l ++ t
 #align list.mmap_upper_triangle List.mapDiagM
+-/
 
 #print List.mapDiagM' /-
 /-- `mmap'_diag f l` calls `f` on all elements in the upper triangular part of `l × l`.
@@ -1315,6 +1356,7 @@ def takeList {α} : List α → List ℕ → List (List α) × List α
 #align list.take_list List.takeList
 -/
 
+#print List.toRBMap /-
 /-- `to_rbmap as` is the map that associates each index `i` of `as` with the
 corresponding element of `as`.
 
@@ -1325,6 +1367,7 @@ to_rbmap ['a', 'b', 'c'] = rbmap_of [(0, 'a'), (1, 'b'), (2, 'c')]
 def toRBMap {α : Type _} : List α → Rbmap ℕ α :=
   foldlIdx (fun i mapp a => mapp.insert i a) (mkRbmap ℕ α)
 #align list.to_rbmap List.toRBMap
+-/
 
 #print List.toChunksAux /-
 /-- Auxliary definition used to define `to_chunks`.

d2d8742b

bump to nightly-2023-06-01-16

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

b9c87c70

Diff

@@ -644,7 +644,7 @@ def permutationsAux2 (t : α) (ts : List α) (r : List β) : List α → (List 
 #align list.permutations_aux2 List.permutationsAux2
 -/
 
-private def meas : (Σ'_ : List α, List α) → ℕ × ℕ
+private def meas : (Σ' _ : List α, List α) → ℕ × ℕ
   | ⟨l, i⟩ => (length l + length i, length l)
 
 -- mathport name: «expr ≺ »
@@ -664,8 +664,8 @@ def permutationsAux.rec {C : List α → List α → Sort v} (H0 : ∀ is, C []
           (succ (length ts) + length is, length (t :: ts))
         by rw [Nat.succ_add] <;> exact Prod.Lex.right _ (lt_succ_self _)
     have h2 : ⟨is, []⟩ ≺ ⟨t :: ts, is⟩ := Prod.Lex.left _ _ (Nat.lt_add_of_pos_left (succ_pos _))
-    H1 t ts is (permutations_aux.rec ts (t :: is)) (permutations_aux.rec is [])termination_by'
-  ⟨(· ≺ ·), @InvImage.wf _ _ _ meas (WellFounded.prod_lex lt_wf lt_wf)⟩
+    H1 t ts is (permutations_aux.rec ts (t :: is)) (permutations_aux.rec is [])
+termination_by' ⟨(· ≺ ·), @InvImage.wf _ _ _ meas (WellFounded.prod_lex lt_wf lt_wf)⟩
 #align list.permutations_aux.rec List.permutationsAux.rec
 -/
 
@@ -773,7 +773,7 @@ infixr:82
 /-- `sigma l₁ l₂` is the list of dependent pairs `(a, b)` where `a ∈ l₁` and `b ∈ l₂ a`.
 
      sigma [1, 2] (λ_, [(5 : ℕ), 6]) = [(1, 5), (1, 6), (2, 5), (2, 6)] -/
-protected def sigma {σ : α → Type _} (l₁ : List α) (l₂ : ∀ a, List (σ a)) : List (Σa, σ a) :=
+protected def sigma {σ : α → Type _} (l₁ : List α) (l₂ : ∀ a, List (σ a)) : List (Σ a, σ a) :=
   l₁.bind fun a => (l₂ a).map <| Sigma.mk a
 #align list.sigma List.sigma
 -/
@@ -841,8 +841,8 @@ attribute [simp] pairwise.nil
 
 #print List.instDecidablePairwise /-
 instance instDecidablePairwise [DecidableRel R] (l : List α) : Decidable (Pairwise R l) := by
-  induction' l with hd tl ih <;>
-    [exact is_true pairwise.nil;exact decidable_of_iff' _ pairwise_cons]
+  induction' l with hd tl ih <;> [exact is_true pairwise.nil;
+    exact decidable_of_iff' _ pairwise_cons]
 #align list.decidable_pairwise List.instDecidablePairwise
 -/

d2d8742b

bump to nightly-2023-06-01-04

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

4d9eaa85

Diff

@@ -97,11 +97,9 @@ def head? : List α → Option α
 #align list.head' List.head?
 -/
 
-/- warning: list.to_array clashes with [anonymous] -> [anonymous]
-Case conversion may be inaccurate. Consider using '#align list.to_array [anonymous]ₓ'. -/
 /-- Convert a list into an array (whose length is the length of `l`). -/
-def [anonymous] (l : List α) : Array' l.length α where data v := l.nthLe v.1 v.2
-#align list.to_array [anonymous]
+def toArray (l : List α) : Array' l.length α where data v := l.nthLe v.1 v.2
+#align list.to_array List.toArray
 
 #print List.getD /-
 /-- "default" `nth` function: returns `d` instead of `none` in the case

d2d8742b

bump to nightly-2023-05-28-06

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

ba5d8b97

Diff

@@ -64,23 +64,11 @@ def splitOnPAux {α : Type u} (P : α → Prop) [DecidablePred P] :
   | h :: t, f => if P h then f [] :: split_on_p_aux t id else split_on_p_aux t fun l => f (h :: l)
 #align list.split_on_p_aux List.splitOnPAux
 
-/- warning: list.split_on_p -> List.splitOnP is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} (P : α -> Prop) [_inst_1 : DecidablePred.{succ u1} α P], (List.{u1} α) -> (List.{u1} (List.{u1} α))
-but is expected to have type
-  forall {α : Type.{u1}}, (α -> Bool) -> (List.{u1} α) -> (List.{u1} (List.{u1} α))
-Case conversion may be inaccurate. Consider using '#align list.split_on_p List.splitOnPₓ'. -/
 /-- Split a list at every element satisfying a predicate. -/
 def splitOnP {α : Type u} (P : α → Prop) [DecidablePred P] (l : List α) : List (List α) :=
   splitOnPAux P l id
 #align list.split_on_p List.splitOnP
 
-/- warning: list.split_on -> List.splitOn is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α], α -> (List.{u1} α) -> (List.{u1} (List.{u1} α))
-but is expected to have type
-  forall {α : Type.{u1}} [_inst_1 : BEq.{u1} α], α -> (List.{u1} α) -> (List.{u1} (List.{u1} α))
-Case conversion may be inaccurate. Consider using '#align list.split_on List.splitOnₓ'. -/
 /-- Split a list at every occurrence of an element.
 
     [1,1,2,3,2,4,4].split_on 2 = [[1,1],[3],[4,4]] -/
@@ -110,11 +98,6 @@ def head? : List α → Option α
 -/
 
 /- warning: list.to_array clashes with [anonymous] -> [anonymous]
-warning: list.to_array -> [anonymous] is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u_1}} (l : List.{u_1} α), Array'.{u_1} (List.length.{u_1} α l) α
-but is expected to have type
-  forall {α : Type.{u}} {l : Type.{v}}, (Nat -> α -> l) -> Nat -> (List.{u} α) -> (List.{v} l)
 Case conversion may be inaccurate. Consider using '#align list.to_array [anonymous]ₓ'. -/
 /-- Convert a list into an array (whose length is the length of `l`). -/
 def [anonymous] (l : List α) : Array' l.length α where data v := l.nthLe v.1 v.2
@@ -200,12 +183,6 @@ def takeI : ∀ n, List α → List α
 
 end Take'
 
-/- warning: list.take_while -> List.takeWhile is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} (p : α -> Prop) [_inst_1 : DecidablePred.{succ u1} α p], (List.{u1} α) -> (List.{u1} α)
-but is expected to have type
-  forall {α : Type.{u1}}, (α -> Bool) -> (List.{u1} α) -> (List.{u1} α)
-Case conversion may be inaccurate. Consider using '#align list.take_while List.takeWhileₓ'. -/
 /-- Get the longest initial segment of the list whose members all satisfy `p`.
 
      take_while (λ x, x < 3) [0, 2, 5, 1] = [0, 2] -/
@@ -297,12 +274,6 @@ def partitionMap (f : α → Sum β γ) : List α → List β × List γ
 #align list.partition_map List.partitionMap
 -/
 
-/- warning: list.find -> List.find? is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} (p : α -> Prop) [_inst_1 : DecidablePred.{succ u1} α p], (List.{u1} α) -> (Option.{u1} α)
-but is expected to have type
-  forall {α : Type.{u1}}, (α -> Bool) -> (List.{u1} α) -> (Option.{u1} α)
-Case conversion may be inaccurate. Consider using '#align list.find List.find?ₓ'. -/
 /-- `find p l` is the first element of `l` satisfying `p`, or `none` if no such
   element exists. -/
 def find? (p : α → Prop) [DecidablePred p] : List α → Option α
@@ -310,12 +281,6 @@ def find? (p : α → Prop) [DecidablePred p] : List α → Option α
   | a :: l => if p a then some a else find l
 #align list.find List.find?
 
-/- warning: list.mfind -> List.findM is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {m : Type.{u1} -> Type.{u2}} [_inst_1 : Monad.{u1, u2} m] [_inst_2 : Alternative.{u1, u2} m], (α -> (m PUnit.{succ u1})) -> (List.{u1} α) -> (m α)
-but is expected to have type
-  forall {α : Type.{u1}} {m : Type.{u1} -> Type.{u2}} [_inst_1 : Alternative.{u1, u2} m], (α -> (m PUnit.{succ u1})) -> (List.{u1} α) -> (m α)
-Case conversion may be inaccurate. Consider using '#align list.mfind List.findMₓ'. -/
 /-- `mfind tac l` returns the first element of `l` on which `tac` succeeds, and
 fails otherwise. -/
 def findM {α} {m : Type u → Type v} [Monad m] [Alternative m] (tac : α → m PUnit) : List α → m α :=
@@ -346,12 +311,6 @@ def findM? {α} (p : α → m Bool) (xs : List α) : m (Option α) :=
 #align list.mbfind List.findM?
 -/
 
-/- warning: list.many -> List.anyM is a dubious translation:
-lean 3 declaration is
-  forall {m : Type -> Type.{u2}} [_inst_1 : Monad.{0, u2} m] {α : Type.{u1}}, (α -> (m Bool)) -> (List.{u1} α) -> (m Bool)
-but is expected to have type
-  forall {m : Type -> Type.{u1}} [_inst_1 : Monad.{0, u1} m] {α : Type.{u2}}, (α -> (m Bool)) -> (List.{u2} α) -> (m Bool)
-Case conversion may be inaccurate. Consider using '#align list.many List.anyMₓ'. -/
 -- Implementing this via `mbfind` would give us less universe polymorphism.
 /-- `many p as` returns true iff `p` returns true for any element of `l`.
 `many` short-circuits, so if `p` returns true for any element of `l`, later
@@ -363,12 +322,6 @@ def anyM {α : Type u} (p : α → m Bool) : List α → m Bool
     if px then pure tt else many xs
 #align list.many List.anyM
 
-/- warning: list.mall -> List.allM is a dubious translation:
-lean 3 declaration is
-  forall {m : Type -> Type.{u2}} [_inst_1 : Monad.{0, u2} m] {α : Type.{u1}}, (α -> (m Bool)) -> (List.{u1} α) -> (m Bool)
-but is expected to have type
-  forall {m : Type -> Type.{u1}} [_inst_1 : Monad.{0, u1} m] {α : Type.{u2}}, (α -> (m Bool)) -> (List.{u2} α) -> (m Bool)
-Case conversion may be inaccurate. Consider using '#align list.mall List.allMₓ'. -/
 /-- `mall p as` returns true iff `p` returns true for all elements of `l`.
 `mall` short-circuits, so if `p` returns false for any element of `l`, later
 elements are not checked. This is a monadic version of `list.all`. -/
@@ -396,24 +349,12 @@ def andM : List (m Bool) → m Bool :=
 
 end
 
-/- warning: list.foldl_with_index_aux -> List.foldlWithIndexAux is a dubious translation:
-lean 3 declaration is
-  forall {α : Sort.{u1}} {β : Type.{u2}}, (Nat -> α -> β -> α) -> Nat -> α -> (List.{u2} β) -> α
-but is expected to have type
-  forall {α : Sort.{u2}} {β : Type.{u1}}, (Nat -> α -> β -> α) -> Nat -> α -> (List.{u1} β) -> α
-Case conversion may be inaccurate. Consider using '#align list.foldl_with_index_aux List.foldlWithIndexAuxₓ'. -/
 /-- Auxiliary definition for `foldl_with_index`. -/
 def foldlWithIndexAux {α : Sort _} {β : Type _} (f : ℕ → α → β → α) : ℕ → α → List β → α
   | _, a, [] => a
   | i, a, b :: l => foldl_with_index_aux (i + 1) (f i a b) l
 #align list.foldl_with_index_aux List.foldlWithIndexAux
 
-/- warning: list.foldl_with_index -> List.foldlIdx is a dubious translation:
-lean 3 declaration is
-  forall {α : Sort.{u1}} {β : Type.{u2}}, (Nat -> α -> β -> α) -> α -> (List.{u2} β) -> α
-but is expected to have type
-  forall {α : Sort.{u1}} {β : Type.{u2}}, (Nat -> α -> β -> α) -> α -> (List.{u2} β) -> (optParam.{1} Nat (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) -> α
-Case conversion may be inaccurate. Consider using '#align list.foldl_with_index List.foldlIdxₓ'. -/
 /-- Fold a list from left to right as with `foldl`, but the combining function
 also receives each element's index. -/
 def foldlIdx {α : Sort _} {β : Type _} (f : ℕ → α → β → α) (a : α) (l : List β) : α :=
@@ -426,47 +367,23 @@ def foldrWithIndexAux {α : Type _} {β : Sort _} (f : ℕ → α → β → β)
   | i, b, a :: l => f i a (foldr_with_index_aux (i + 1) b l)
 #align list.foldr_with_index_aux List.foldrWithIndexAux
 
-/- warning: list.foldr_with_index -> List.foldrIdx is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {β : Sort.{u2}}, (Nat -> α -> β -> β) -> β -> (List.{u1} α) -> β
-but is expected to have type
-  forall {α : Type.{u1}} {β : Sort.{u2}}, (Nat -> α -> β -> β) -> β -> (List.{u1} α) -> (optParam.{1} Nat (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) -> β
-Case conversion may be inaccurate. Consider using '#align list.foldr_with_index List.foldrIdxₓ'. -/
 /-- Fold a list from right to left as with `foldr`, but the combining function
 also receives each element's index. -/
 def foldrIdx {α : Type _} {β : Sort _} (f : ℕ → α → β → β) (b : β) (l : List α) : β :=
   foldrWithIndexAux f 0 b l
 #align list.foldr_with_index List.foldrIdx
 
-/- warning: list.find_indexes -> List.findIdxs is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} (p : α -> Prop) [_inst_1 : DecidablePred.{succ u1} α p], (List.{u1} α) -> (List.{0} Nat)
-but is expected to have type
-  forall {α : Type.{u1}}, (α -> Bool) -> (List.{u1} α) -> (List.{0} Nat)
-Case conversion may be inaccurate. Consider using '#align list.find_indexes List.findIdxsₓ'. -/
 /-- `find_indexes p l` is the list of indexes of elements of `l` that satisfy `p`. -/
 def findIdxs (p : α → Prop) [DecidablePred p] (l : List α) : List Nat :=
   foldrIdx (fun i a is => if p a then i :: is else is) [] l
 #align list.find_indexes List.findIdxs
 
-/- warning: list.indexes_values -> List.indexesValues is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} (p : α -> Prop) [_inst_1 : DecidablePred.{succ u1} α p], (List.{u1} α) -> (List.{u1} (Prod.{0, u1} Nat α))
-but is expected to have type
-  forall {α : Type.{u1}}, (α -> Bool) -> (List.{u1} α) -> (List.{u1} (Prod.{0, u1} Nat α))
-Case conversion may be inaccurate. Consider using '#align list.indexes_values List.indexesValuesₓ'. -/
 /-- Returns the elements of `l` that satisfy `p` together with their indexes in
 `l`. The returned list is ordered by index. -/
 def indexesValues (p : α → Prop) [DecidablePred p] (l : List α) : List (ℕ × α) :=
   foldrIdx (fun i a l => if p a then (i, a) :: l else l) [] l
 #align list.indexes_values List.indexesValues
 
-/- warning: list.indexes_of -> List.indexesOf is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α], α -> (List.{u1} α) -> (List.{0} Nat)
-but is expected to have type
-  forall {α : Type.{u1}} [_inst_1 : BEq.{u1} α], α -> (List.{u1} α) -> (List.{0} Nat)
-Case conversion may be inaccurate. Consider using '#align list.indexes_of List.indexesOfₓ'. -/
 /-- `indexes_of a l` is the list of all indexes of `a` in `l`. For example:
 ```
 indexes_of a [a, b, a, a] = [0, 2, 3]
@@ -508,47 +425,23 @@ section MmapWithIndex
 
 variable {m : Type v → Type w} [Applicative m]
 
-/- warning: list.mmap_with_index_aux -> List.mmapWithIndexAux is a dubious translation:
-lean 3 declaration is
-  forall {m : Type.{u1} -> Type.{u2}} [_inst_1 : Applicative.{u1, u2} m] {α : Type.{u3}} {β : Type.{u1}}, (Nat -> α -> (m β)) -> Nat -> (List.{u3} α) -> (m (List.{u1} β))
-but is expected to have type
-  forall {m : Type.{u2} -> Type.{u3}} [_inst_1 : Applicative.{u2, u3} m] {α : Type.{u1}} {β : Type.{u2}}, (Nat -> α -> (m β)) -> Nat -> (List.{u1} α) -> (m (List.{u2} β))
-Case conversion may be inaccurate. Consider using '#align list.mmap_with_index_aux List.mmapWithIndexAuxₓ'. -/
 /-- Auxiliary definition for `mmap_with_index`. -/
 def mmapWithIndexAux {α β} (f : ℕ → α → m β) : ℕ → List α → m (List β)
   | _, [] => pure []
   | i, a :: as => List.cons <$> f i a <*> mmap_with_index_aux (i + 1) as
 #align list.mmap_with_index_aux List.mmapWithIndexAux
 
-/- warning: list.mmap_with_index -> List.mapIdxM is a dubious translation:
-lean 3 declaration is
-  forall {m : Type.{u1} -> Type.{u2}} [_inst_1 : Applicative.{u1, u2} m] {α : Type.{u3}} {β : Type.{u1}}, (Nat -> α -> (m β)) -> (List.{u3} α) -> (m (List.{u1} β))
-but is expected to have type
-  forall {m : Type.{u3}} {_inst_1 : Type.{u1}} {α : Type.{u1} -> Type.{u2}} [β : Monad.{u1, u2} α], (List.{u3} m) -> (Nat -> m -> (α _inst_1)) -> (α (List.{u1} _inst_1))
-Case conversion may be inaccurate. Consider using '#align list.mmap_with_index List.mapIdxMₓ'. -/
 /-- Applicative variant of `map_with_index`. -/
 def mapIdxM {α β} (f : ℕ → α → m β) (as : List α) : m (List β) :=
   mmapWithIndexAux f 0 as
 #align list.mmap_with_index List.mapIdxM
 
-/- warning: list.mmap_with_index'_aux -> List.mapIdxMAux' is a dubious translation:
-lean 3 declaration is
-  forall {m : Type.{u1} -> Type.{u2}} [_inst_1 : Applicative.{u1, u2} m] {α : Type.{u3}}, (Nat -> α -> (m PUnit.{succ u1})) -> Nat -> (List.{u3} α) -> (m PUnit.{succ u1})
-but is expected to have type
-  forall {m : Type.{u1} -> Type.{u2}} [_inst_1 : Monad.{u1, u2} m] {α : Type.{u3}}, (Nat -> α -> (m PUnit.{succ u1})) -> Nat -> (List.{u3} α) -> (m PUnit.{succ u1})
-Case conversion may be inaccurate. Consider using '#align list.mmap_with_index'_aux List.mapIdxMAux'ₓ'. -/
 /-- Auxiliary definition for `mmap_with_index'`. -/
 def mapIdxMAux' {α} (f : ℕ → α → m PUnit) : ℕ → List α → m PUnit
   | _, [] => pure ⟨⟩
   | i, a :: as => f i a *> mmap_with_index'_aux (i + 1) as
 #align list.mmap_with_index'_aux List.mapIdxMAux'
 
-/- warning: list.mmap_with_index' -> List.mapIdxM' is a dubious translation:
-lean 3 declaration is
-  forall {m : Type.{u1} -> Type.{u2}} [_inst_1 : Applicative.{u1, u2} m] {α : Type.{u3}}, (Nat -> α -> (m PUnit.{succ u1})) -> (List.{u3} α) -> (m PUnit.{succ u1})
-but is expected to have type
-  forall {m : Type.{u1} -> Type.{u2}} [_inst_1 : Monad.{u1, u2} m] {α : Type.{u3}}, (Nat -> α -> (m PUnit.{succ u1})) -> (List.{u3} α) -> (m PUnit.{succ u1})
-Case conversion may be inaccurate. Consider using '#align list.mmap_with_index' List.mapIdxM'ₓ'. -/
 /-- A variant of `mmap_with_index` specialised to applicative actions which
 return `unit`. -/
 def mapIdxM' {α} (f : ℕ → α → m PUnit) (as : List α) : m PUnit :=
@@ -570,24 +463,12 @@ def lookmap (f : α → Option α) : List α → List α
 #align list.lookmap List.lookmap
 -/
 
-/- warning: list.countp -> List.countp is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} (p : α -> Prop) [_inst_1 : DecidablePred.{succ u1} α p], (List.{u1} α) -> Nat
-but is expected to have type
-  forall {α : Type.{u1}}, (α -> Bool) -> (List.{u1} α) -> Nat
-Case conversion may be inaccurate. Consider using '#align list.countp List.countpₓ'. -/
 /-- `countp p l` is the number of elements of `l` that satisfy `p`. -/
 def countp (p : α → Prop) [DecidablePred p] : List α → Nat
   | [] => 0
   | x :: xs => if p x then succ (countp xs) else countp xs
 #align list.countp List.countp
 
-/- warning: list.count -> List.count is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α], α -> (List.{u1} α) -> Nat
-but is expected to have type
-  forall {α : Type.{u1}} [_inst_1 : BEq.{u1} α], α -> (List.{u1} α) -> Nat
-Case conversion may be inaccurate. Consider using '#align list.count List.countₓ'. -/
 /-- `count a l` is the number of occurrences of `a` in `l`. -/
 def count [DecidableEq α] (a : α) : List α → Nat :=
   countp (Eq a)
@@ -648,12 +529,6 @@ def tails : List α → List (List α)
 #align list.tails List.tails
 -/
 
-/- warning: list.sublists'_aux -> List.sublists'Aux is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u_1}} {β : Type.{u_2}}, (List.{u_1} α) -> ((List.{u_1} α) -> (List.{u_2} β)) -> (List.{u_2} (List.{u_2} β)) -> (List.{u_2} (List.{u_2} β))
-but is expected to have type
-  forall {α : Type.{u}}, α -> (List.{u} (List.{u} α)) -> (List.{u} (List.{u} α)) -> (List.{u} (List.{u} α))
-Case conversion may be inaccurate. Consider using '#align list.sublists'_aux List.sublists'Auxₓ'. -/
 def sublists'Aux : List α → (List α → List β) → List (List β) → List (List β)
   | [], f, r => f [] :: r
   | a :: l, f, r => sublists'_aux l f (sublists'_aux l (f ∘ cons a) r)
@@ -671,12 +546,6 @@ def sublists' (l : List α) : List (List α) :=
 #align list.sublists' List.sublists'
 -/
 
-/- warning: list.sublists_aux -> List.sublistsAux is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u_1}} {β : Type.{u_2}}, (List.{u_1} α) -> ((List.{u_1} α) -> (List.{u_2} β) -> (List.{u_2} β)) -> (List.{u_2} β)
-but is expected to have type
-  forall {α : Type.{u}}, α -> (List.{u} (List.{u} α)) -> (List.{u} (List.{u} α))
-Case conversion may be inaccurate. Consider using '#align list.sublists_aux List.sublistsAuxₓ'. -/
 def sublistsAux : List α → (List α → List β → List β) → List β
   | [], f => []
   | a :: l, f => f [a] (sublists_aux l fun ys r => f ys (f (a :: ys) r))
@@ -1088,12 +957,6 @@ def destutter (R : α → α → Prop) [DecidableRel R] : List α → List α
 #align list.destutter List.destutter
 -/
 
-/- warning: list.range' -> List.range' is a dubious translation:
-lean 3 declaration is
-  Nat -> Nat -> (List.{0} Nat)
-but is expected to have type
-  Nat -> Nat -> (optParam.{1} Nat (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))) -> (List.{0} Nat)
-Case conversion may be inaccurate. Consider using '#align list.range' List.range'ₓ'. -/
 /-- `range' s n` is the list of numbers `[s, s+1, ..., s+n-1]`.
   It is intended mainly for proving properties of `range` and `iota`. -/
 @[simp]
@@ -1179,12 +1042,6 @@ def choose (hp : ∃ a, a ∈ l ∧ p a) : α :=
 
 end Choose
 
-/- warning: list.mmap_filter -> List.filterMapM is a dubious translation:
-lean 3 declaration is
-  forall {m : Type -> Type.{u1}} [_inst_1 : Monad.{0, u1} m] {α : Type.{u2}} {β : Type}, (α -> (m (Option.{0} β))) -> (List.{u2} α) -> (m (List.{0} β))
-but is expected to have type
-  forall {m : Type.{u1} -> Type.{u2}} [_inst_1 : Monad.{u1, u2} m] {α : Type.{u1}} {β : Type.{u1}}, (α -> (m (Option.{u1} β))) -> (List.{u1} α) -> (m (List.{u1} β))
-Case conversion may be inaccurate. Consider using '#align list.mmap_filter List.filterMapMₓ'. -/
 /-- Filters and maps elements of a list -/
 def filterMapM {m : Type → Type v} [Monad m] {α β} (f : α → m (Option β)) : List α → m (List β)
   | [] => return []
@@ -1197,12 +1054,6 @@ def filterMapM {m : Type → Type v} [Monad m] {α β} (f : α → m (Option β)
         | some x => x :: t'
 #align list.mmap_filter List.filterMapM
 
-/- warning: list.mmap_upper_triangle -> List.mapDiagM is a dubious translation:
-lean 3 declaration is
-  forall {m : Type.{u} -> Type.{u_1}} [_inst_1 : Monad.{u, u_1} m] {α : Type.{u}} {β : Type.{u}}, (α -> α -> (m β)) -> (List.{u} α) -> (m (List.{u} β))
-but is expected to have type
-  forall {m : Type.{u_1} -> Type.{u_2}} {_inst_1 : Type.{u_3}} {α : Type.{u_1}} [β : Monad.{u_1, u_2} m], (_inst_1 -> _inst_1 -> (m α)) -> (List.{u_3} _inst_1) -> (m (List.{u_1} α))
-Case conversion may be inaccurate. Consider using '#align list.mmap_upper_triangle List.mapDiagMₓ'. -/
 /-- `mmap_upper_triangle f l` calls `f` on all elements in the upper triangular part of `l × l`.
 That is, for each `e ∈ l`, it will run `f e e` and then `f e e'`
 for each `e'` that appears after `e` in `l`.
@@ -1466,12 +1317,6 @@ def takeList {α} : List α → List ℕ → List (List α) × List α
 #align list.take_list List.takeList
 -/
 
-/- warning: list.to_rbmap -> List.toRBMap is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u_1}}, (List.{u_1} α) -> (Rbmap.{0, u_1} Nat α (LT.lt.{0} Nat Nat.hasLt))
-but is expected to have type
-  forall {α : Type.{u_1}} {ᾰ : Type.{u_2}}, (List.{max u_2 u_1} (Prod.{u_1, u_2} α ᾰ)) -> (forall (cmp : α -> α -> Ordering), Std.RBMap.{u_1, u_2} α ᾰ cmp)
-Case conversion may be inaccurate. Consider using '#align list.to_rbmap List.toRBMapₓ'. -/
 /-- `to_rbmap as` is the map that associates each index `i` of `as` with the
 corresponding element of `as`.

d2d8742b

bump to nightly-2023-05-28-03

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

6c6011cf

Diff

@@ -779,7 +779,6 @@ def permutationsAux2 (t : α) (ts : List α) (r : List β) : List α → (List 
 
 private def meas : (Σ'_ : List α, List α) → ℕ × ℕ
   | ⟨l, i⟩ => (length l + length i, length l)
-#align list.meas list.meas
 
 -- mathport name: «expr ≺ »
 local infixl:50 " ≺ " => InvImage (Prod.Lex (· < ·) (· < ·)) meas

d2d8742b

bump to nightly-2023-05-24-06

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

fbc7b476

Diff

@@ -975,8 +975,8 @@ attribute [simp] pairwise.nil
 
 #print List.instDecidablePairwise /-
 instance instDecidablePairwise [DecidableRel R] (l : List α) : Decidable (Pairwise R l) := by
-  induction' l with hd tl ih <;> [exact is_true pairwise.nil,
-    exact decidable_of_iff' _ pairwise_cons]
+  induction' l with hd tl ih <;>
+    [exact is_true pairwise.nil;exact decidable_of_iff' _ pairwise_cons]
 #align list.decidable_pairwise List.instDecidablePairwise
 -/
 
@@ -1089,7 +1089,12 @@ def destutter (R : α → α → Prop) [DecidableRel R] : List α → List α
 #align list.destutter List.destutter
 -/
 
-#print List.range' /-
+/- warning: list.range' -> List.range' is a dubious translation:
+lean 3 declaration is
+  Nat -> Nat -> (List.{0} Nat)
+but is expected to have type
+  Nat -> Nat -> (optParam.{1} Nat (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))) -> (List.{0} Nat)
+Case conversion may be inaccurate. Consider using '#align list.range' List.range'ₓ'. -/
 /-- `range' s n` is the list of numbers `[s, s+1, ..., s+n-1]`.
   It is intended mainly for proving properties of `range` and `iota`. -/
 @[simp]
@@ -1097,7 +1102,6 @@ def range' : ℕ → ℕ → List ℕ
   | s, 0 => []
   | s, n + 1 => s :: range' (s + 1) n
 #align list.range' List.range'
--/
 
 #print List.reduceOption /-
 /-- Drop `none`s from a list, and replace each remaining `some a` with `a`. -/

d2d8742b

bump to nightly-2023-04-10-20

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

af46b02d

Diff

@@ -109,15 +109,16 @@ def head? : List α → Option α
 #align list.head' List.head?
 -/
 
-/- warning: list.to_array -> List.toArray is a dubious translation:
+/- warning: list.to_array clashes with [anonymous] -> [anonymous]
+warning: list.to_array -> [anonymous] is a dubious translation:
 lean 3 declaration is
-  forall {α : Type.{u1}} (l : List.{u1} α), Array'.{u1} (List.length.{u1} α l) α
+  forall {α : Type.{u_1}} (l : List.{u_1} α), Array'.{u_1} (List.length.{u_1} α l) α
 but is expected to have type
-  forall {α : Type.{u1}}, (List.{u1} α) -> (Array.{u1} α)
-Case conversion may be inaccurate. Consider using '#align list.to_array List.toArrayₓ'. -/
+  forall {α : Type.{u}} {l : Type.{v}}, (Nat -> α -> l) -> Nat -> (List.{u} α) -> (List.{v} l)
+Case conversion may be inaccurate. Consider using '#align list.to_array [anonymous]ₓ'. -/
 /-- Convert a list into an array (whose length is the length of `l`). -/
-def toArray (l : List α) : Array' l.length α where data v := l.nthLe v.1 v.2
-#align list.to_array List.toArray
+def [anonymous] (l : List α) : Array' l.length α where data v := l.nthLe v.1 v.2
+#align list.to_array [anonymous]
 
 #print List.getD /-
 /-- "default" `nth` function: returns `d` instead of `none` in the case

d2d8742b

bump to nightly-2023-03-05-03

mathlib commit https://github.com/leanprover-community/mathlib/commit/641b6a82006416ec431b2987b354af9311fed4f2

1345f149

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Parikshit Khanna, Jeremy Avigad, Leonardo de Moura, Floris van Doorn, Mario Carneiro
 
 ! This file was ported from Lean 3 source module data.list.defs
-! leanprover-community/mathlib commit 1447cae870f372074e480de1acbeb51de0077698
+! leanprover-community/mathlib commit d2d8742b0c21426362a9dacebc6005db895ca963
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -395,39 +395,45 @@ def andM : List (m Bool) → m Bool :=
 
 end
 
+/- warning: list.foldl_with_index_aux -> List.foldlWithIndexAux is a dubious translation:
+lean 3 declaration is
+  forall {α : Sort.{u1}} {β : Type.{u2}}, (Nat -> α -> β -> α) -> Nat -> α -> (List.{u2} β) -> α
+but is expected to have type
+  forall {α : Sort.{u2}} {β : Type.{u1}}, (Nat -> α -> β -> α) -> Nat -> α -> (List.{u1} β) -> α
+Case conversion may be inaccurate. Consider using '#align list.foldl_with_index_aux List.foldlWithIndexAuxₓ'. -/
 /-- Auxiliary definition for `foldl_with_index`. -/
-def foldlWithIndexAux (f : ℕ → α → β → α) : ℕ → α → List β → α
+def foldlWithIndexAux {α : Sort _} {β : Type _} (f : ℕ → α → β → α) : ℕ → α → List β → α
   | _, a, [] => a
   | i, a, b :: l => foldl_with_index_aux (i + 1) (f i a b) l
 #align list.foldl_with_index_aux List.foldlWithIndexAux
 
 /- warning: list.foldl_with_index -> List.foldlIdx is a dubious translation:
 lean 3 declaration is
-  forall {α : Type.{u1}} {β : Type.{u2}}, (Nat -> α -> β -> α) -> α -> (List.{u2} β) -> α
+  forall {α : Sort.{u1}} {β : Type.{u2}}, (Nat -> α -> β -> α) -> α -> (List.{u2} β) -> α
 but is expected to have type
   forall {α : Sort.{u1}} {β : Type.{u2}}, (Nat -> α -> β -> α) -> α -> (List.{u2} β) -> (optParam.{1} Nat (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) -> α
 Case conversion may be inaccurate. Consider using '#align list.foldl_with_index List.foldlIdxₓ'. -/
 /-- Fold a list from left to right as with `foldl`, but the combining function
 also receives each element's index. -/
-def foldlIdx (f : ℕ → α → β → α) (a : α) (l : List β) : α :=
+def foldlIdx {α : Sort _} {β : Type _} (f : ℕ → α → β → α) (a : α) (l : List β) : α :=
   foldlWithIndexAux f 0 a l
 #align list.foldl_with_index List.foldlIdx
 
 /-- Auxiliary definition for `foldr_with_index`. -/
-def foldrWithIndexAux (f : ℕ → α → β → β) : ℕ → β → List α → β
+def foldrWithIndexAux {α : Type _} {β : Sort _} (f : ℕ → α → β → β) : ℕ → β → List α → β
   | _, b, [] => b
   | i, b, a :: l => f i a (foldr_with_index_aux (i + 1) b l)
 #align list.foldr_with_index_aux List.foldrWithIndexAux
 
 /- warning: list.foldr_with_index -> List.foldrIdx is a dubious translation:
 lean 3 declaration is
-  forall {α : Type.{u1}} {β : Type.{u2}}, (Nat -> α -> β -> β) -> β -> (List.{u1} α) -> β
+  forall {α : Type.{u1}} {β : Sort.{u2}}, (Nat -> α -> β -> β) -> β -> (List.{u1} α) -> β
 but is expected to have type
   forall {α : Type.{u1}} {β : Sort.{u2}}, (Nat -> α -> β -> β) -> β -> (List.{u1} α) -> (optParam.{1} Nat (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) -> β
 Case conversion may be inaccurate. Consider using '#align list.foldr_with_index List.foldrIdxₓ'. -/
 /-- Fold a list from right to left as with `foldr`, but the combining function
 also receives each element's index. -/
-def foldrIdx (f : ℕ → α → β → β) (b : β) (l : List α) : β :=
+def foldrIdx {α : Type _} {β : Sort _} (f : ℕ → α → β → β) (b : β) (l : List α) : β :=
   foldrWithIndexAux f 0 b l
 #align list.foldr_with_index List.foldrIdx

1447cae8

bump to nightly-2023-02-21-16

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

1107b979

Changes in mathlib4

mathlib3

mathlib4

d2d8742b

chore: remove autoImplicit from more files (#11798)

and reduce its scope in a few other instances. Mostly in CategoryTheory and Data this time; some Combinatorics also.

Co-authored-by: Richard Osborn <richardosborn@mac.com>

3bb1d613

Diff

@@ -19,8 +19,6 @@ This file contains various definitions on lists. It does not contain
 proofs about these definitions, those are contained in other files in `Data.List`
 -/
 
-set_option autoImplicit true
-
 -- Porting note
 -- Many of the definitions in `Data.List.Defs` were already defined upstream in `Std4`
 -- These have been annotated with `#align`s
@@ -314,14 +312,15 @@ instance instSProd : SProd (List α) (List β) (List (α × β)) where
 
 section Chain
 
-instance decidableChain [DecidableRel R] (a : α) (l : List α) :
+instance decidableChain {R : α → α → Prop} [DecidableRel R] (a : α) (l : List α) :
     Decidable (Chain R a l) := by
   induction l generalizing a with
   | nil => simp only [List.Chain.nil]; infer_instance
   | cons a as ih => haveI := ih; simp only [List.chain_cons]; infer_instance
 #align list.decidable_chain List.decidableChain
 
-instance decidableChain' [DecidableRel R] (l : List α) : Decidable (Chain' R l) := by
+instance decidableChain' {R : α → α → Prop} [DecidableRel R] (l : List α) :
+    Decidable (Chain' R l) := by
   cases l <;> dsimp only [List.Chain'] <;> infer_instance
 #align list.decidable_chain' List.decidableChain'

d2d8742b

chore: replace λ by fun (#11301)

Per the style guidelines, λ is disallowed in mathlib. This is close to exhaustive; I left some tactic code alone when it seemed to me that tactic could be upstreamed soon.

Notes

In lines I was modifying anyway, I also converted => to ↦.
Also contains some mild in-passing indentation fixes in Mathlib/Order/SupClosed.
Some doc comments still contained Lean 3 syntax λ x, , which I also replaced.

af0f54a9

Diff

@@ -515,7 +515,7 @@ These can also be written in terms of `List.zip` or `List.zipWith`.
 For example, `zipWith3 f xs ys zs` could also be written as
 `zipWith id (zipWith f xs ys) zs`
 or as
-`(zip xs <| zip ys zs).map <| λ ⟨x, y, z⟩, f x y z`.
+`(zip xs <| zip ys zs).map <| fun ⟨x, y, z⟩ ↦ f x y z`.
 -/
 
 /-- Ternary version of `List.zipWith`. -/

d2d8742b

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

@@ -217,7 +217,7 @@ def permutationsAux2 (t : α) (ts : List α) (r : List β) : List α → (List 
     (y :: us, f (t :: y :: us) :: zs)
 #align list.permutations_aux2 List.permutationsAux2
 
--- porting note: removed `[elab_as_elim]` per Mario C
+-- Porting note: removed `[elab_as_elim]` per Mario C
 -- https://leanprover.zulipchat.com/#narrow/stream/287929-mathlib4/topic/Status.20of.20data.2Elist.2Edefs.3F/near/313571979
 /-- A recursor for pairs of lists. To have `C l₁ l₂` for all `l₁`, `l₂`, it suffices to have it for
 `l₂ = []` and to be able to pour the elements of `l₁` into `l₂`. -/

d2d8742b

chore: classify added to ease automation porting notes (#10689)

Classifies by adding issue number (#10688) to porting notes claiming anything semantically equivalent to added to ease automation.
Enforce singular convention converting "porting notes" to "porting note".

b06068c3

Diff

@@ -21,7 +21,7 @@ proofs about these definitions, those are contained in other files in `Data.List
 
 set_option autoImplicit true
 
--- Porting notes
+-- Porting note
 -- Many of the definitions in `Data.List.Defs` were already defined upstream in `Std4`
 -- These have been annotated with `#align`s
 -- To make this easier for review, the `#align`s have been placed in order of occurrence
@@ -500,7 +500,7 @@ def map₂Right (f : Option α → β → γ) (as : List α) (bs : List β) : Li
 #align list.to_chunks_aux List.toChunksAux
 #align list.to_chunks List.toChunks
 
--- porting notes -- was `unsafe` but removed for Lean 4 port
+-- porting note -- was `unsafe` but removed for Lean 4 port
 -- TODO: naming is awkward...
 /-- Asynchronous version of `List.map`.
 -/

d2d8742b

chore: change from plural to singular in porting notes (#10761)

0f21e517

Diff

@@ -49,7 +49,7 @@ instance [DecidableEq α] : SDiff (List α) :=
 #noalign list.to_array
 
 #align list.nthd List.getD
--- porting notes: see
+-- Porting note: see
 -- https://leanprover.zulipchat.com/#narrow/stream/287929-mathlib4/topic/List.2Ehead/near/313204716
 -- for the fooI naming convention.
 /-- "Inhabited" `get` function: returns `default` instead of `none` in the case
@@ -151,7 +151,7 @@ end foldIdxM
 
 section mapIdxM
 
--- porting notes: This was defined in `mathlib` with an `Applicative`
+-- Porting note: This was defined in `mathlib` with an `Applicative`
 -- constraint on `m` and have been `#align`ed to the `Std` versions defined
 -- with a `Monad` typeclass constraint.
 -- Since all `Monad`s are `Applicative` this won't cause issues

d2d8742b

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

@@ -226,8 +226,8 @@ def permutationsAux.rec {C : List α → List α → Sort v} (H0 : ∀ is, C []
   | [], is => H0 is
   | t :: ts, is =>
       H1 t ts is (permutationsAux.rec H0 H1 ts (t :: is)) (permutationsAux.rec H0 H1 is [])
-  termination_by _ ts is => (length ts + length is, length ts)
-  decreasing_by simp_wf; omega
+  termination_by ts is => (length ts + length is, length ts)
+  decreasing_by all_goals (simp_wf; omega)
 #align list.permutations_aux.rec List.permutationsAux.rec
 
 /-- An auxiliary function for defining `permutations`. `permutationsAux ts is` is the set of all

d2d8742b

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

@@ -5,7 +5,6 @@ Authors: Parikshit Khanna, Jeremy Avigad, Leonardo de Moura, Floris van Doorn, M
 -/
 import Mathlib.Init.Data.Nat.Notation
 import Mathlib.Control.Functor
-import Mathlib.Logic.Basic
 import Mathlib.Data.SProd
 import Mathlib.Util.CompileInductive
 import Std.Tactic.Lint.Basic

d2d8742b

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,7 +3,6 @@ Copyright (c) 2014 Parikshit Khanna. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Parikshit Khanna, Jeremy Avigad, Leonardo de Moura, Floris van Doorn, Mario Carneiro
 -/
-import Mathlib.Data.List.Defs
 import Mathlib.Algebra.Group.Defs
 
 #align_import data.list.defs from "leanprover-community/mathlib"@"d2d8742b0c21426362a9dacebc6005db895ca963"

d2d8742b

chore: use omega in decreasing_by proofs (#9688)

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

30030d81

Diff

@@ -228,7 +228,7 @@ def permutationsAux.rec {C : List α → List α → Sort v} (H0 : ∀ is, C []
   | t :: ts, is =>
       H1 t ts is (permutationsAux.rec H0 H1 ts (t :: is)) (permutationsAux.rec H0 H1 is [])
   termination_by _ ts is => (length ts + length is, length ts)
-  decreasing_by simp_wf; simp [Nat.succ_add]; decreasing_tactic
+  decreasing_by simp_wf; omega
 #align list.permutations_aux.rec List.permutationsAux.rec
 
 /-- An auxiliary function for defining `permutations`. `permutationsAux ts is` is the set of all

d2d8742b

chore(*): replace $ with <| (#9319)

See Zulip thread for the discussion.

9f6d3388

Diff

@@ -516,7 +516,7 @@ These can also be written in terms of `List.zip` or `List.zipWith`.
 For example, `zipWith3 f xs ys zs` could also be written as
 `zipWith id (zipWith f xs ys) zs`
 or as
-`(zip xs $ zip ys zs).map $ λ ⟨x, y, z⟩, f x y z`.
+`(zip xs <| zip ys zs).map <| λ ⟨x, y, z⟩, f x y z`.
 -/
 
 /-- Ternary version of `List.zipWith`. -/

d2d8742b

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

Subset of #9319

3694e27d

Diff

@@ -79,7 +79,7 @@ def takeI [Inhabited α] (n : Nat) (l : List α) : List α :=
 /-- `findM tac l` returns the first element of `l` on which `tac` succeeds, and
 fails otherwise. -/
 def findM {α} {m : Type u → Type v} [Alternative m] (tac : α → m PUnit) : List α → m α :=
-  List.firstM <| fun a => (tac a) $> a
+  List.firstM fun a => (tac a) $> a
 #align list.mfind List.findM
 
 /-- `findM? p l` returns the first element `a` of `l` for which `p a` returns

d2d8742b

chore: reduce imports of Data.List.Defs (#8635)

Currently Data.List.Defs depends on Algebra.Group.Defs, rather unnecessarily.

(This then prevents importing Data.List.Defs into Tactic.Common, without breaking various assert_not_exists statements.)

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: thorimur <68410468+thorimur@users.noreply.github.com>

7df4ff91

Diff

@@ -3,9 +3,8 @@ Copyright (c) 2014 Parikshit Khanna. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Parikshit Khanna, Jeremy Avigad, Leonardo de Moura, Floris van Doorn, Mario Carneiro
 -/
-import Mathlib.Algebra.Group.Defs
+import Mathlib.Init.Data.Nat.Notation
 import Mathlib.Control.Functor
-import Mathlib.Data.Nat.Basic
 import Mathlib.Logic.Basic
 import Mathlib.Data.SProd
 import Mathlib.Util.CompileInductive
@@ -74,37 +73,6 @@ def takeI [Inhabited α] (n : Nat) (l : List α) : List α :=
 #align list.take_while List.takeWhile
 #align list.scanl List.scanl
 #align list.scanr List.scanr
-
-/-- Product of a list.
-
-     `List.prod [a, b, c] = ((1 * a) * b) * c` -/
-def prod [Mul α] [One α] : List α → α :=
-  foldl (· * ·) 1
-#align list.prod List.prod
-
--- Later this will be tagged with `to_additive`, but this can't be done yet because of imports.
--- dependencies.
-/-- Sum of a list.
-
-     `List.sum [a, b, c] = ((0 + a) + b) + c` -/
-def sum [Add α] [Zero α] : List α → α :=
-  foldl (· + ·) 0
-#align list.sum List.sum
-
-/-- The alternating sum of a list. -/
-def alternatingSum {G : Type*} [Zero G] [Add G] [Neg G] : List G → G
-  | [] => 0
-  | g :: [] => g
-  | g :: h :: t => g + -h + alternatingSum t
-#align list.alternating_sum List.alternatingSum
-
-/-- The alternating product of a list. -/
-def alternatingProd {G : Type*} [One G] [Mul G] [Inv G] : List G → G
-  | [] => 1
-  | g :: [] => g
-  | g :: h :: t => g * h⁻¹ * alternatingProd t
-#align list.alternating_prod List.alternatingProd
-
 #align list.partition_map List.partitionMap
 #align list.find List.find?

d2d8742b

chore: reduce imports of Data.List.Defs (#8635)

Currently Data.List.Defs depends on Algebra.Group.Defs, rather unnecessarily.

(This then prevents importing Data.List.Defs into Tactic.Common, without breaking various assert_not_exists statements.)

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: thorimur <68410468+thorimur@users.noreply.github.com>

7df4ff91

d2d8742b

fix: make List.choose 'more' reducible (#8753)

The pattern match (on the And) was blocking (some kinds of) reduction. This is presumably because eta reduction doesn't apply in Prop, as described in this Zulip thread.

Zulip thread that reported this.

561c0059

Diff

@@ -410,10 +410,11 @@ def chooseX : ∀ l : List α, ∀ _ : ∃ a, a ∈ l ∧ p a, { a // a ∈ l 
   | l :: ls, hp =>
     if pl : p l then ⟨l, ⟨mem_cons.mpr <| Or.inl rfl, pl⟩⟩
     else
-      let ⟨a, ⟨a_mem_ls, pa⟩⟩ :=
+      -- pattern matching on `hx` too makes this not reducible!
+      let ⟨a, ha⟩ :=
         chooseX ls
           (hp.imp fun _ ⟨o, h₂⟩ => ⟨(mem_cons.mp o).resolve_left fun e => pl <| e ▸ h₂, h₂⟩)
-      ⟨a, ⟨mem_cons.mpr <| Or.inr a_mem_ls, pa⟩⟩
+      ⟨a, mem_cons.mpr <| Or.inr ha.1, ha.2⟩
 #align list.choose_x List.chooseX
 
 /-- Given a decidable predicate `p` and a proof of existence of `a ∈ l` such that `p a`,

d2d8742b

chore: bump for std4#241 (#6975)

depends on: https://github.com/leanprover/std4/pull/241

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

2577ef78

Diff

@@ -446,15 +446,7 @@ def mapDiagM' {m} [Monad m] {α} (f : α → α → m Unit) : List α → m Unit
 --   | h :: t => (f h h >> t.mapM' (f h)) >> t.mapDiagM'
 #align list.mmap'_diag List.mapDiagM'
 
-/-- Map each element of a `List` to an action, evaluate these actions in order,
-    and collect the results.
--/
-protected def traverse {F : Type u → Type v} [Applicative F]
-    {α : Type*} {β : Type u} (f : α → F β) : List α → F (List β)
-  | [] => pure []
-  | x :: xs => List.cons <$> f x <*> List.traverse f xs
 #align list.traverse List.traverse
-
 #align list.get_rest List.getRest
 #align list.slice List.dropSlice

d2d8742b

refactor: List.All₂ to List.Forall (#7797)

This renames List.All₂ to List.Forall, because the ₂ is highly confusing when it usually means “two lists”, and we had users on Zulip not find List.Forall because of that (https://leanprover.zulipchat.com/#narrow/stream/217875-Is-there-code-for-X.3F/topic/Is.20there.20List.2EForall.E2.82.82.2C.20but.20for.20one.20list.3F.20.28In.20library.20Std.29/near/397551365)

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

004800e4

Diff

@@ -220,14 +220,14 @@ end mapIdxM
 #align list.sublists List.sublists
 #align list.forall₂ List.Forall₂
 
-/-- `l.All₂ p` is equivalent to `∀ a ∈ l, p a`, but unfolds directly to a conjunction, i.e.
-`List.All₂ p [0, 1, 2] = p 0 ∧ p 1 ∧ p 2`. -/
+/-- `l.Forall p` is equivalent to `∀ a ∈ l, p a`, but unfolds directly to a conjunction, i.e.
+`List.Forall p [0, 1, 2] = p 0 ∧ p 1 ∧ p 2`. -/
 @[simp]
-def All₂ (p : α → Prop) : List α → Prop
+def Forall (p : α → Prop) : List α → Prop
   | [] => True
   | x :: [] => p x
-  | x :: l => p x ∧ All₂ p l
-#align list.all₂ List.All₂
+  | x :: l => p x ∧ Forall p l
+#align list.all₂ List.Forall
 
 #align list.transpose List.transpose
 #align list.sections List.sections

d2d8742b

docs: capitalize List.All in it's own docstring (#7784)

97c0e220

Diff

@@ -220,7 +220,7 @@ end mapIdxM
 #align list.sublists List.sublists
 #align list.forall₂ List.Forall₂
 
-/-- `l.all₂ p` is equivalent to `∀ a ∈ l, p a`, but unfolds directly to a conjunction, i.e.
+/-- `l.All₂ p` is equivalent to `∀ a ∈ l, p a`, but unfolds directly to a conjunction, i.e.
 `List.All₂ p [0, 1, 2] = p 0 ∧ p 1 ∧ p 2`. -/
 @[simp]
 def All₂ (p : α → Prop) : List α → Prop

d2d8742b

chore: remove many Type _ before the colon (#7718)

We have turned to Type* instead of Type _, but many of them remained in mathlib because the straight replacement did not work. In general, having Type _ before the colon is a code smell, though, as it hides which types should be in the same universe and which shouldn't, and is not very robust.

This PR replaces most of the remaining Type _ before the colon (except those in category theory) by Type* or Type u. This has uncovered a few bugs (where declarations were not as polymorphic as they should be).

I had to increase heartbeats at two places when replacing Type _ by Type*, but I think it's worth it as it's really more robust.

fe9572d2

Diff

@@ -449,8 +449,8 @@ def mapDiagM' {m} [Monad m] {α} (f : α → α → m Unit) : List α → m Unit
 /-- Map each element of a `List` to an action, evaluate these actions in order,
     and collect the results.
 -/
-protected def traverse {F : Type u → Type v} [Applicative F] {α β : Type _} (f : α → F β) :
-    List α → F (List β)
+protected def traverse {F : Type u → Type v} [Applicative F]
+    {α : Type*} {β : Type u} (f : α → F β) : List α → F (List β)
   | [] => pure []
   | x :: xs => List.cons <$> f x <*> List.traverse f xs
 #align list.traverse List.traverse

d2d8742b

chore: bump std (#7602)

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

8de3e102

Diff

@@ -211,9 +211,9 @@ end mapIdxM
 #align list.lookmap List.lookmap
 #align list.countp List.countP
 #align list.count List.count
-#align list.is_prefix List.isPrefix
-#align list.is_suffix List.isSuffix
-#align list.is_infix List.isInfix
+#align list.is_prefix List.IsPrefix
+#align list.is_suffix List.IsSuffix
+#align list.is_infix List.IsInfix
 #align list.inits List.inits
 #align list.tails List.tails
 #align list.sublists' List.sublists'

d2d8742b

chore: fix some cases in names (#7469)

And fix some names in comments where this revealed issues

be0d066c

Diff

@@ -298,7 +298,7 @@ def permutations'Aux (t : α) : List α → List (List α)
 
 /-- List of all permutations of `l`. This version of `permutations` is less efficient but has
 simpler definitional equations. The permutations are in a different order,
-but are equal up to permutation, as shown by `list.permutations_perm_permutations'`.
+but are equal up to permutation, as shown by `List.permutations_perm_permutations'`.
 
      permutations [1, 2, 3] =
        [[1, 2, 3], [2, 1, 3], [2, 3, 1],

d2d8742b

chore: exactly 4 spaces in theorems (#7328)

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

d3263b23

Diff

@@ -436,14 +436,14 @@ Example: suppose `l = [1, 2, 3]`. `mapDiagM' f l` will evaluate, in this order,
 `f 1 1`, `f 1 2`, `f 1 3`, `f 2 2`, `f 2 3`, `f 3 3`.
 -/
 def mapDiagM' {m} [Monad m] {α} (f : α → α → m Unit) : List α → m Unit
--- as ported:
---   | [] => return ()
---   | h :: t => (f h h >> t.mapM' (f h)) >> t.mapDiagM'
   | [] => return ()
   | h :: t => do
     _ ← f h h
     _ ← t.mapM' (f h)
     t.mapDiagM' f
+-- as ported:
+--   | [] => return ()
+--   | h :: t => (f h h >> t.mapM' (f h)) >> t.mapDiagM'
 #align list.mmap'_diag List.mapDiagM'
 
 /-- Map each element of a `List` to an action, evaluate these actions in order,

d2d8742b

style: a linter for colons (#6761)

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

69a3de31

Diff

@@ -449,8 +449,8 @@ def mapDiagM' {m} [Monad m] {α} (f : α → α → m Unit) : List α → m Unit
 /-- Map each element of a `List` to an action, evaluate these actions in order,
     and collect the results.
 -/
-protected def traverse {F : Type u → Type v} [Applicative F] {α β : Type _} (f : α → F β)
-    : List α → F (List β)
+protected def traverse {F : Type u → Type v} [Applicative F] {α β : Type _} (f : α → F β) :
+    List α → F (List β)
   | [] => pure []
   | x :: xs => List.cons <$> f x <*> List.traverse f xs
 #align list.traverse List.traverse

d2d8742b

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

@@ -209,7 +209,7 @@ def mapIdxM' {α} (f : ℕ → α → m PUnit) (as : List α) : m PUnit :=
 end mapIdxM
 
 #align list.lookmap List.lookmap
-#align list.countp List.countp
+#align list.countp List.countP
 #align list.count List.count
 #align list.is_prefix List.isPrefix
 #align list.is_suffix List.isSuffix

d2d8742b

fix: disable autoImplicit globally (#6528)

Autoimplicits are highly controversial and also defeat the performance-improving work in #6474.

The intent of this PR is to make autoImplicit opt-in on a per-file basis, by disabling it in the lakefile and enabling it again with set_option autoImplicit true in the few files that rely on it.

That also keeps this PR small, as opposed to attempting to "fix" files to not need it any more.

I claim that many of the uses of autoImplicit in these files are accidental; situations such as:

Assuming variables are in scope, but pasting the lemma in the wrong section
Pasting in a lemma from a scratch file without checking to see if the variable names are consistent with the rest of the file
Making a copy-paste error between lemmas and forgetting to add an explicit arguments.

Having set_option autoImplicit false as the default prevents these types of mistake being made in the 90% of files where autoImplicits are not used at all, and causes them to be caught by CI during review.

I think there were various points during the port where we encouraged porters to delete the universes u v lines; I think having autoparams for universe variables only would cover a lot of the cases we actually use them, while avoiding any real shortcomings.

A Zulip poll (after combining overlapping votes accordingly) was in favor of this change with 5:5:18 as the no:dontcare:yes vote ratio.

While this PR was being reviewed, a handful of files gained some more likely-accidental autoImplicits. In these places, set_option autoImplicit true has been placed locally within a section, rather than at the top of the file.

0c24f831

Diff

@@ -21,6 +21,8 @@ This file contains various definitions on lists. It does not contain
 proofs about these definitions, those are contained in other files in `Data.List`
 -/
 
+set_option autoImplicit true
+
 -- Porting notes
 -- Many of the definitions in `Data.List.Defs` were already defined upstream in `Std4`
 -- These have been annotated with `#align`s

d2d8742b

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

@@ -33,7 +33,7 @@ open Function Nat
 
 universe u v w x
 
-variable {α β γ δ ε ζ : Type _}
+variable {α β γ δ ε ζ : Type*}
 
 instance [DecidableEq α] : SDiff (List α) :=
   ⟨List.diff⟩
@@ -90,14 +90,14 @@ def sum [Add α] [Zero α] : List α → α :=
 #align list.sum List.sum
 
 /-- The alternating sum of a list. -/
-def alternatingSum {G : Type _} [Zero G] [Add G] [Neg G] : List G → G
+def alternatingSum {G : Type*} [Zero G] [Add G] [Neg G] : List G → G
   | [] => 0
   | g :: [] => g
   | g :: h :: t => g + -h + alternatingSum t
 #align list.alternating_sum List.alternatingSum
 
 /-- The alternating product of a list. -/
-def alternatingProd {G : Type _} [One G] [Mul G] [Inv G] : List G → G
+def alternatingProd {G : Type*} [One G] [Mul G] [Inv G] : List G → G
   | [] => 1
   | g :: [] => g
   | g :: h :: t => g * h⁻¹ * alternatingProd t

d2d8742b

chore: ensure all instances referred to directly have explicit names (#6423)

Per https://github.com/leanprover/lean4/issues/2343, we are going to need to change the automatic generation of instance names, as they become too long.

This PR ensures that everywhere in Mathlib that refers to an instance by name, that name is given explicitly, rather than being automatically generated.

There are four exceptions, which are now commented, with links to https://github.com/leanprover/lean4/issues/2343.

This was implemented by running Mathlib against a modified Lean that appended _ᾰ to all automatically generated names, and fixing everything.

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

65a35f78

Diff

@@ -588,5 +588,4 @@ def replaceIf : List α → List Bool → List α → List α
 #align list.map_with_prefix_suffix List.mapWithPrefixSuffix
 #align list.map_with_complement List.mapWithComplement
 
-
 end List

d2d8742b

chore: move some List aligns to a better location (#6056)

a211e856

Diff

@@ -38,6 +38,7 @@ variable {α β γ δ ε ζ : Type _}
 instance [DecidableEq α] : SDiff (List α) :=
   ⟨List.diff⟩
 
+#align list.replicate List.replicate
 #align list.split_at List.splitAt
 #align list.split_on_p List.splitOnP
 #align list.split_on List.splitOn

d2d8742b

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,11 +2,6 @@
 Copyright (c) 2014 Parikshit Khanna. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Parikshit Khanna, Jeremy Avigad, Leonardo de Moura, Floris van Doorn, Mario Carneiro
-
-! This file was ported from Lean 3 source module data.list.defs
-! leanprover-community/mathlib commit d2d8742b0c21426362a9dacebc6005db895ca963
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Algebra.Group.Defs
 import Mathlib.Control.Functor
@@ -17,6 +12,8 @@ import Mathlib.Util.CompileInductive
 import Std.Tactic.Lint.Basic
 import Std.Data.RBMap.Basic
 
+#align_import data.list.defs from "leanprover-community/mathlib"@"d2d8742b0c21426362a9dacebc6005db895ca963"
+
 /-!
 ## Definitions on lists

d2d8742b

chore: bump to nightly-2023-05-31 (#4530)

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Mario Carneiro <di.gama@gmail.com> Co-authored-by: Floris van Doorn <fpvdoorn@gmail.com> Co-authored-by: Jeremy Tan Jie Rui <reddeloostw@gmail.com> Co-authored-by: Alex J Best <alex.j.best@gmail.com>

01da6a3c

Diff

@@ -343,15 +343,10 @@ instance instSProd : SProd (List α) (List β) (List (α × β)) where
 #align list.pw_filter List.pwFilter
 #align list.chain List.Chain
 #align list.chain' List.Chain'
+#align list.chain_cons List.chain_cons
 
 section Chain
 
-@[simp]
-theorem chain_cons {a b : α} {l : List α} : Chain R a (b :: l) ↔ R a b ∧ Chain R b l :=
-  ⟨fun p ↦ by cases p with | cons n p => exact ⟨n, p⟩,
-   fun ⟨n, p⟩ ↦ p.cons n⟩
-#align list.chain_cons List.chain_cons
-
 instance decidableChain [DecidableRel R] (a : α) (l : List α) :
     Decidable (Chain R a l) := by
   induction l generalizing a with

d2d8742b

refactor: use the typeclass SProd to implement overloaded notation · ×ˢ · (#4200)

Currently, the following notations are changed from · ×ˢ · because Lean 4 can't deal with ambiguous notations. | Definition | Notation | | :

Co-authored-by: Jeremy Tan Jie Rui <reddeloostw@gmail.com> Co-authored-by: Kyle Miller <kmill31415@gmail.com> Co-authored-by: Chris Hughes <chrishughes24@gmail.com>

6c01dc6e

Diff

@@ -12,6 +12,7 @@ import Mathlib.Algebra.Group.Defs
 import Mathlib.Control.Functor
 import Mathlib.Data.Nat.Basic
 import Mathlib.Logic.Basic
+import Mathlib.Data.SProd
 import Mathlib.Util.CompileInductive
 import Std.Tactic.Lint.Basic
 import Std.Data.RBMap.Basic
@@ -325,10 +326,13 @@ def extractp (p : α → Prop) [DecidablePred p] : List α → Option α × List
 
 #align list.revzip List.revzip
 #align list.product List.product
+
 /-- Notation for calculating the product of a `List`
 -/
--- This notation binds more strongly than (pre)images, unions and intersections.
-infixr:82 " ×ˢ " => List.product
+
+instance instSProd : SProd (List α) (List β) (List (α × β)) where
+  sprod := List.product
+
 #align list.sigma List.sigma
 #align list.of_fn List.ofFn
 #align list.of_fn_nth_val List.ofFnNthVal

d2d8742b

feat: add compile_inductive% and compile_def% commands (#4097)

Add a #compile inductive command to compile the recursors of an inductive type, which works by creating a recursive definition and using @[csimp].

Co-authored-by: Parth Shastri <31370288+cppio@users.noreply.github.com> Co-authored-by: Mario Carneiro <di.gama@gmail.com>

63c31ccb

Diff

@@ -12,6 +12,7 @@ import Mathlib.Algebra.Group.Defs
 import Mathlib.Control.Functor
 import Mathlib.Data.Nat.Basic
 import Mathlib.Logic.Basic
+import Mathlib.Util.CompileInductive
 import Std.Tactic.Lint.Basic
 import Std.Data.RBMap.Basic
 
@@ -32,32 +33,6 @@ namespace List
 
 open Function Nat
 
-section recursor_workarounds
-/-- A computable version of `List.rec`. Workaround until Lean has native support for this. -/
-def recC.{u_1, u} {α : Type u} {motive : List α → Sort u_1} (nil : motive [])
-  (cons : (head : α) → (tail : List α) → motive tail → motive (head :: tail)) :
-    (l : List α) → motive l
-| [] => nil
-| (x :: xs) => cons x xs (List.recC nil cons xs)
-
-@[csimp]
-lemma rec_eq_recC : @List.rec = @List.recC := by
-  ext α motive nil cons l
-  induction l with
-  | nil => rfl
-  | cons x xs ih =>
-    rw [List.recC, ←ih]
-
-/-- A computable version of `List._sizeOf_inst`. -/
-def _sizeOf_instC.{u} (α : Type u) [SizeOf α] : SizeOf (List α) where
-  sizeOf t := List.rec 1 (fun head _ tail_ih => 1 + SizeOf.sizeOf head + tail_ih) t
-
-@[csimp]
-lemma _sizeOfinst_eq_sizeOfinstC : @List._sizeOf_inst = @List._sizeOf_instC := by
-  simp [List._sizeOf_1, List._sizeOf_instC, _sizeOf_inst]
-
-end recursor_workarounds
-
 universe u v w x
 
 variable {α β γ δ ε ζ : Type _}

d2d8742b

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

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

27d257fc

Diff

@@ -101,7 +101,7 @@ def takeI [Inhabited α] (n : Nat) (l : List α) : List α :=
 
 /-- Product of a list.
 
-     `prod [a, b, c] = ((1 * a) * b) * c` -/
+     `List.prod [a, b, c] = ((1 * a) * b) * c` -/
 def prod [Mul α] [One α] : List α → α :=
   foldl (· * ·) 1
 #align list.prod List.prod
@@ -110,7 +110,7 @@ def prod [Mul α] [One α] : List α → α :=
 -- dependencies.
 /-- Sum of a list.
 
-     `sum [a, b, c] = ((0 + a) + b) + c` -/
+     `List.sum [a, b, c] = ((0 + a) + b) + c` -/
 def sum [Add α] [Zero α] : List α → α :=
   foldl (· + ·) 0
 #align list.sum List.sum
@@ -225,7 +225,7 @@ def mapIdxMAux' {α} (f : ℕ → α → m PUnit) : ℕ → List α → m PUnit
 #align list.mmap_with_index'_aux List.mapIdxMAux'
 
 /-- A variant of `mapIdxM` specialised to applicative actions which
-return `unit`. -/
+return `Unit`. -/
 def mapIdxM' {α} (f : ℕ → α → m PUnit) (as : List α) : m PUnit :=
   mapIdxMAux' f 0 as
 #align list.mmap_with_index' List.mapIdxM'
@@ -245,7 +245,7 @@ end mapIdxM
 #align list.forall₂ List.Forall₂
 
 /-- `l.all₂ p` is equivalent to `∀ a ∈ l, p a`, but unfolds directly to a conjunction, i.e.
-`list.all₂ p [0, 1, 2] = p 0 ∧ p 1 ∧ p 2`. -/
+`List.All₂ p [0, 1, 2] = p 0 ∧ p 1 ∧ p 2`. -/
 @[simp]
 def All₂ (p : α → Prop) : List α → Prop
   | [] => True

d2d8742b

feat: port Init.IteSimp (#3368)

Co-authored-by: samaritan <shreyasss94@gmail.com>

f7ed2abd

Diff

@@ -70,7 +70,10 @@ instance [DecidableEq α] : SDiff (List α) :=
 #align list.split_on List.splitOn
 #align list.concat List.concat
 #align list.head' List.head?
-#align list.to_array List.toArray
+
+-- mathlib3 `array` is not ported.
+#noalign list.to_array
+
 #align list.nthd List.getD
 -- porting notes: see
 -- https://leanprover.zulipchat.com/#narrow/stream/287929-mathlib4/topic/List.2Ehead/near/313204716

d2d8742b

feat: bump Data/List/Defs SHA (#3249)

Both https://github.com/leanprover-community/mathlib/pull/18182 and https://github.com/leanprover-community/mathlib/pull/18543 are backports, and as such no other modification needs to be made to this file.

c070d281

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Parikshit Khanna, Jeremy Avigad, Leonardo de Moura, Floris van Doorn, Mario Carneiro
 
 ! This file was ported from Lean 3 source module data.list.defs
-! leanprover-community/mathlib commit 1fc36cc9c8264e6e81253f88be7fb2cb6c92d76a
+! leanprover-community/mathlib commit d2d8742b0c21426362a9dacebc6005db895ca963
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/

1fc36cc9

fix: make List.rec and Nat.rec computable (#1720)

This works around https://github.com/leanprover/lean4/issues/2049. By manually adding compiler support for these recursors, we make a large number of porting notes redundant.

19e2b8d2

Diff

@@ -32,6 +32,32 @@ namespace List
 
 open Function Nat
 
+section recursor_workarounds
+/-- A computable version of `List.rec`. Workaround until Lean has native support for this. -/
+def recC.{u_1, u} {α : Type u} {motive : List α → Sort u_1} (nil : motive [])
+  (cons : (head : α) → (tail : List α) → motive tail → motive (head :: tail)) :
+    (l : List α) → motive l
+| [] => nil
+| (x :: xs) => cons x xs (List.recC nil cons xs)
+
+@[csimp]
+lemma rec_eq_recC : @List.rec = @List.recC := by
+  ext α motive nil cons l
+  induction l with
+  | nil => rfl
+  | cons x xs ih =>
+    rw [List.recC, ←ih]
+
+/-- A computable version of `List._sizeOf_inst`. -/
+def _sizeOf_instC.{u} (α : Type u) [SizeOf α] : SizeOf (List α) where
+  sizeOf t := List.rec 1 (fun head _ tail_ih => 1 + SizeOf.sizeOf head + tail_ih) t
+
+@[csimp]
+lemma _sizeOfinst_eq_sizeOfinstC : @List._sizeOf_inst = @List._sizeOf_instC := by
+  simp [List._sizeOf_1, List._sizeOf_instC, _sizeOf_inst]
+
+end recursor_workarounds
+
 universe u v w x
 
 variable {α β γ δ ε ζ : Type _}
@@ -344,14 +370,14 @@ theorem chain_cons {a b : α} {l : List α} : Chain R a (b :: l) ↔ R a b ∧ C
    fun ⟨n, p⟩ ↦ p.cons n⟩
 #align list.chain_cons List.chain_cons
 
-noncomputable instance decidableChain [DecidableRel R] (a : α) (l : List α) :
+instance decidableChain [DecidableRel R] (a : α) (l : List α) :
     Decidable (Chain R a l) := by
   induction l generalizing a with
   | nil => simp only [List.Chain.nil]; infer_instance
   | cons a as ih => haveI := ih; simp only [List.chain_cons]; infer_instance
 #align list.decidable_chain List.decidableChain
 
-noncomputable instance decidableChain' [DecidableRel R] (l : List α) : Decidable (Chain' R l) := by
+instance decidableChain' [DecidableRel R] (l : List α) : Decidable (Chain' R l) := by
   cases l <;> dsimp only [List.Chain'] <;> infer_instance
 #align list.decidable_chain' List.decidableChain'

1fc36cc9

feat: port Data.List.Sublists (#1494)

Co-authored-by: qawbecrdtey <qawbecrdtey@kaist.ac.kr> Co-authored-by: ChrisHughes24 <chrishughes24@gmail.com>

fb6c6c41

Diff

@@ -215,14 +215,6 @@ end mapIdxM
 #align list.sublists List.sublists
 #align list.forall₂ List.Forall₂
 
-/-- Definition of a `sublists` function with an explicit list construction function
-    Used in `Data.Lists.Sublists`: TODO: move there when ported.
--/
-def sublistsAux₁ : List α → (List α → List β) → List β
-  | [], _ => []
-  | a :: l, f => f [a] ++ sublistsAux₁ l fun ys => f ys ++ f (a :: ys)
-#align list.sublists_aux₁ List.sublistsAux₁
-
 /-- `l.all₂ p` is equivalent to `∀ a ∈ l, p a`, but unfolds directly to a conjunction, i.e.
 `list.all₂ p [0, 1, 2] = p 0 ∧ p 1 ∧ p 2`. -/
 @[simp]

1fc36cc9

chore: update to 2023-01-10 nightly (#1447)

depends on: https://github.com/leanprover/std4/pull/83
depends on: https://github.com/JLimperg/aesop/pull/38

835b2b6b

Diff

@@ -105,7 +105,7 @@ def alternatingProd {G : Type _} [One G] [Mul G] [Inv G] : List G → G
 
 /-- `findM tac l` returns the first element of `l` on which `tac` succeeds, and
 fails otherwise. -/
-def findM {α} {m : Type u → Type v} [Monad m] [Alternative m] (tac : α → m PUnit) : List α → m α :=
+def findM {α} {m : Type u → Type v} [Alternative m] (tac : α → m PUnit) : List α → m α :=
   List.firstM <| fun a => (tac a) $> a
 #align list.mfind List.findM

1fc36cc9

feat: port Data.List.Permutation (#1445)

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

99b6ebcc

Diff

@@ -249,7 +249,7 @@ defined) is the list of lists of the form `insert_nth n t (ys ++ ts)` for `0 ≤
 def permutationsAux2 (t : α) (ts : List α) (r : List β) : List α → (List α → β) → List α × List β
   | [], _ => (ts, r)
   | y :: ys, f =>
-    let (us, zs) := permutationsAux2 t ys r ys (fun x: List α => f (y :: x))
+    let (us, zs) := permutationsAux2 t ts r ys (fun x: List α => f (y :: x))
     (y :: us, f (t :: y :: us) :: zs)
 #align list.permutations_aux2 List.permutationsAux2

1fc36cc9

feat: port Data.List.Infix (#1350)

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

9f4e5f90

Diff

@@ -209,16 +209,6 @@ end mapIdxM
 #align list.is_prefix List.isPrefix
 #align list.is_suffix List.isSuffix
 #align list.is_infix List.isInfix
-/-- Notation for `List.isPrefix`
--/
-infixl:50 " <+: " => isPrefix
-/--  Notation for `List.isSuffix`
--/
-infixl:50 " <:+ " => isSuffix
-/-- Notation for `List.isInfix`
--/
-infixl:50 " <:+: " => isInfix
-
 #align list.inits List.inits
 #align list.tails List.tails
 #align list.sublists' List.sublists'

1fc36cc9

feat port: Data.List.Basic (#966)

cf9386b5

Notes so far There are various problems with theorems already having been ported. Sometimes there was a change in universe level order, implicit argument order, or explicit arguments order or explicicity of arguments. In these situations I did the following. --Ignore the error and align the old lemma when the difference between the two was just universe. --Align the old lemma with the new lemma but incluce a porting note when the difference was the order of implicit arguments --Make a new lemma with a ' at the end when the difference was to do with explicit arguments.

I also added a bunch of definitions that were not imported, possibly with the wrong names. These definitions are repeat, ret, empty, init, last, ilast

There is a question to be answered about what to do with list.nth_le, which is discussed on Zulip

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: ChrisHughes24 <chrishughes24@gmail.com> Co-authored-by: Johan Commelin <johan@commelin.net> Co-authored-by: Siddhartha Gadgil <siddhartha.gadgil@gmail.com>

f0c99391

Diff

@@ -324,11 +324,7 @@ def permutations' : List α → List (List α)
 
 end Permutations
 
-/-- `erasep p l` removes the first element of `l` satisfying the predicate `p`. -/
-def erasep (p : α → Prop) [DecidablePred p] : List α → List α
-  | [] => []
-  | a :: l => if p a then l else a :: erasep p l
-#align list.erasep List.erasep
+#align list.erasep List.erasePₓ -- prop -> bool
 
 /-- `extractp p l` returns a pair of an element `a` of `l` satisfying the predicate
   `p`, and `l`, with `a` removed. If there is no such element `a` it returns `(none, l)`. -/
@@ -409,8 +405,10 @@ def destutter (R : α → α → Prop) [DecidableRel R] : List α → List α
 
 #align list.range' List.range'
 #align list.reduce_option List.reduceOption
+-- Porting note: replace ilast' by getLastD
 #align list.ilast' List.ilast'
-#align list.last' List.last'
+-- Porting note: remove last' from Std
+#align list.last' List.getLast?
 #align list.rotate List.rotate
 #align list.rotate' List.rotate'

1fc36cc9

chore: fix more casing errors per naming scheme (#1232)

I've avoided anything under Tactic or test.

In correcting the names, I found Option.isNone_iff_eq_none duplicated between Std and Mathlib, so the Mathlib one has been removed.

Co-authored-by: Reid Barton <rwbarton@gmail.com>

31a56f75

Diff

@@ -189,13 +189,13 @@ section mapIdxM
 
 variable {m : Type v → Type w} [Monad m]
 
-/-- Auxiliary definition for `mmap_with_index'`. -/
+/-- Auxiliary definition for `mapIdxM'`. -/
 def mapIdxMAux' {α} (f : ℕ → α → m PUnit) : ℕ → List α → m PUnit
   | _, [] => pure ⟨⟩
   | i, a :: as => f i a *> mapIdxMAux' f (i + 1) as
 #align list.mmap_with_index'_aux List.mapIdxMAux'
 
-/-- A variant of `mmap_with_index` specialised to applicative actions which
+/-- A variant of `mapIdxM` specialised to applicative actions which
 return `unit`. -/
 def mapIdxM' {α} (f : ℕ → α → m PUnit) (as : List α) : m PUnit :=
   mapIdxMAux' f 0 as

1fc36cc9

chore: fix docstrings in Data.List.Defs (#1166)

73e7cc55

Diff

@@ -475,15 +475,15 @@ protected def traverse {F : Type u → Type v} [Applicative F] {α β : Type _}
 #align list.get_rest List.getRest
 #align list.slice List.dropSlice
 
-/-- Left-biased version of `list.map₂`. `map₂_left' f as bs` applies `f` to each
+/-- Left-biased version of `List.map₂`. `map₂Left' f as bs` applies `f` to each
 pair of elements `aᵢ ∈ as` and `bᵢ ∈ bs`. If `bs` is shorter than `as`, `f` is
 applied to `none` for the remaining `aᵢ`. Returns the results of the `f`
 applications and the remaining `bs`.
 
 ```
-map₂_left' prod.mk [1, 2] ['a'] = ([(1, some 'a'), (2, none)], [])
+map₂Left' prod.mk [1, 2] ['a'] = ([(1, some 'a'), (2, none)], [])
 
-map₂_left' prod.mk [1] ['a', 'b'] = ([(1, some 'a')], ['b'])
+map₂Left' prod.mk [1] ['a', 'b'] = ([(1, some 'a')], ['b'])
 ```
 -/
 @[simp]
@@ -495,15 +495,15 @@ def map₂Left' (f : α → Option β → γ) : List α → List β → List γ
     (f a (some b) :: rec'.fst, rec'.snd)
 #align list.map₂_left' List.map₂Left'
 
-/-- Right-biased version of `list.map₂`. `map₂_right' f as bs` applies `f` to each
+/-- Right-biased version of `List.map₂`. `map₂Right' f as bs` applies `f` to each
 pair of elements `aᵢ ∈ as` and `bᵢ ∈ bs`. If `as` is shorter than `bs`, `f` is
 applied to `none` for the remaining `bᵢ`. Returns the results of the `f`
 applications and the remaining `as`.
 
 ```
-map₂_right' prod.mk [1] ['a', 'b'] = ([(some 1, 'a'), (none, 'b')], [])
+map₂Right' prod.mk [1] ['a', 'b'] = ([(some 1, 'a'), (none, 'b')], [])
 
-map₂_right' prod.mk [1, 2] ['a'] = ([(some 1, 'a')], [2])
+map₂Right' prod.mk [1, 2] ['a'] = ([(some 1, 'a')], [2])
 ```
 -/
 def map₂Right' (f : Option α → β → γ) (as : List α) (bs : List β) : List γ × List α :=
@@ -567,27 +567,27 @@ def mapAsyncChunked {α β} (f : α → β) (xs : List α) (chunk_size := 1024)
 
 
 /-!
-We add some n-ary versions of `list.zip_with` for functions with more than two arguments.
-These can also be written in terms of `list.zip` or `list.zip_with`.
-For example, `zip_with3 f xs ys zs` could also be written as
-`zip_with id (zip_with f xs ys) zs`
+We add some n-ary versions of `List.zipWith` for functions with more than two arguments.
+These can also be written in terms of `List.zip` or `List.zipWith`.
+For example, `zipWith3 f xs ys zs` could also be written as
+`zipWith id (zipWith f xs ys) zs`
 or as
 `(zip xs $ zip ys zs).map $ λ ⟨x, y, z⟩, f x y z`.
 -/
 
-/-- Ternary version of `list.zip_with`. -/
+/-- Ternary version of `List.zipWith`. -/
 def zipWith3 (f : α → β → γ → δ) : List α → List β → List γ → List δ
   | x :: xs, y :: ys, z :: zs => f x y z :: zipWith3 f xs ys zs
   | _, _, _ => []
 #align list.zip_with3 List.zipWith3
 
-/-- Quaternary version of `list.zip_with`. -/
+/-- Quaternary version of `list.zipWith`. -/
 def zipWith4 (f : α → β → γ → δ → ε) : List α → List β → List γ → List δ → List ε
   | x :: xs, y :: ys, z :: zs, u :: us => f x y z u :: zipWith4 f xs ys zs us
   | _, _, _, _ => []
 #align list.zip_with4 List.zipWith4
 
-/-- Quinary version of `list.zip_with`. -/
+/-- Quinary version of `list.zipWith`. -/
 def zipWith5 (f : α → β → γ → δ → ε → ζ) : List α → List β → List γ → List δ → List ε → List ζ
   | x :: xs, y :: ys, z :: zs, u :: us, v :: vs => f x y z u v :: zipWith5 f xs ys zs us vs
   | _, _, _, _, _ => []
@@ -595,7 +595,7 @@ def zipWith5 (f : α → β → γ → δ → ε → ζ) : List α → List β 
 
 /-- Given a starting list `old`, a list of booleans and a replacement list `new`,
 read the items in `old` in succession and either replace them with the next element of `new` or
-not, according as to whether the corresponding boolean is `tt` or `ff`. -/
+not, according as to whether the corresponding boolean is `true` or `false`. -/
 def replaceIf : List α → List Bool → List α → List α
   | l, _, [] => l
   | [], _, _ => []

1fc36cc9

fix: Data.List.Defs (#1118)

Fixes some problems surrounding Data.List.Defs that were affecting the ongoing port of Data.List.Basic.

introduces takeI as a faithful port of take' and fixes the align
- take' was previously erroneously aligned with takeD. takeD uses an explicitly-provided argument as a default whereas takeI usesInhabited's default.
reverses the dependency Data.List.Chain → Data.List.Defs to Data.List.Defs → Data.List.Chain
- This was causing a circular dependency for Data.List.Basic when it attempted to import Data.List.Defs.
- We move chain_cons from Data.List.Chain into Data.List.Defs.
- All of these changes are in keeping mathlib3's original structure.
- We have to supplement Control.Traversable.Basic's imports, since it was previously relying on Data.Option.Defs via Data.List.Defs ← Data.List.Chain ← ...

See this Zulip conversation for more context.

b9e19018

Diff

@@ -10,7 +10,6 @@ Authors: Parikshit Khanna, Jeremy Avigad, Leonardo de Moura, Floris van Doorn, M
 -/
 import Mathlib.Algebra.Group.Defs
 import Mathlib.Control.Functor
-import Mathlib.Data.List.Chain
 import Mathlib.Data.Nat.Basic
 import Mathlib.Logic.Basic
 import Std.Tactic.Lint.Basic
@@ -50,18 +49,23 @@ instance [DecidableEq α] : SDiff (List α) :=
 -- porting notes: see
 -- https://leanprover.zulipchat.com/#narrow/stream/287929-mathlib4/topic/List.2Ehead/near/313204716
 -- for the fooI naming convention.
-/-- "inhabited" `get` function: returns `default` instead of `none` in the case
+/-- "Inhabited" `get` function: returns `default` instead of `none` in the case
   that the index is out of bounds. -/
 def getI [Inhabited α] (l : List α) (n : Nat) : α :=
   getD l n default
 #align list.inth List.getI
 
+/-- "Inhabited" `take` function: Take `n` elements from a list `l`. If `l` has less than `n`
+  elements, append `n - length l` elements `default`. -/
+def takeI [Inhabited α] (n : Nat) (l : List α) : List α :=
+  takeD n l default
+#align list.take' List.takeI
+
 #align list.modify_nth_tail List.modifyNthTail
 #align list.modify_head List.modifyHead
 #align list.modify_nth List.modifyNth
 #align list.modify_last List.modifyLast
 #align list.insert_nth List.insertNth
-#align list.take' List.takeD
 #align list.take_while List.takeWhile
 #align list.scanl List.scanl
 #align list.scanr List.scanr
@@ -353,10 +357,15 @@ infixr:82 " ×ˢ " => List.product
 #align list.pw_filter List.pwFilter
 #align list.chain List.Chain
 #align list.chain' List.Chain'
-#align list.chain_cons List.chain_cons
 
 section Chain
 
+@[simp]
+theorem chain_cons {a b : α} {l : List α} : Chain R a (b :: l) ↔ R a b ∧ Chain R b l :=
+  ⟨fun p ↦ by cases p with | cons n p => exact ⟨n, p⟩,
+   fun ⟨n, p⟩ ↦ p.cons n⟩
+#align list.chain_cons List.chain_cons
+
 noncomputable instance decidableChain [DecidableRel R] (a : α) (l : List α) :
     Decidable (Chain R a l) := by
   induction l generalizing a with

1fc36cc9

chore: add source headers to ported theory files (#1094)

The script used to do this is included. The yaml file was obtained from https://raw.githubusercontent.com/wiki/leanprover-community/mathlib/mathlib4-port-status.md

f168625e

Diff

@@ -2,6 +2,11 @@
 Copyright (c) 2014 Parikshit Khanna. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Parikshit Khanna, Jeremy Avigad, Leonardo de Moura, Floris van Doorn, Mario Carneiro
+
+! This file was ported from Lean 3 source module data.list.defs
+! leanprover-community/mathlib commit 1fc36cc9c8264e6e81253f88be7fb2cb6c92d76a
+! Please do not edit these lines, except to modify the commit id
+! if you have ported upstream changes.
 -/
 import Mathlib.Algebra.Group.Defs
 import Mathlib.Control.Functor

`data.list.defs` ⟷ `Mathlib.Data.List.BigOperators.Defs`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 4

data.list.defs ⟷ Mathlib.Data.List.BigOperators.Defs

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 4

`data.list.defs` ⟷ `Mathlib.Data.List.BigOperators.Defs`