Documentation

Mathlib.Data.List.Basic

Basic properties of lists #

@[deprecated]
theorem List.le_eq_not_gt {α : Type u} [LT α] (l₁ : List α) (l₂ : List α) :
(l₁ l₂) = ¬l₂ < l₁

implies not > for lists.

instance List.uniqueOfIsEmpty {α : Type u} [IsEmpty α] :

There is only one list of an empty type

Equations
  • List.uniqueOfIsEmpty = { toInhabited := instInhabitedList, uniq := }
Equations
  • =
Equations
  • =
@[simp]
theorem List.cons_injective {α : Type u} {a : α} :
theorem List.singleton_injective {α : Type u} :
Function.Injective fun (a : α) => [a]
theorem List.set_of_mem_cons {α : Type u} (l : List α) (a : α) :
{x : α | x a :: l} = insert a {x : α | x l}

mem #

theorem Decidable.List.eq_or_ne_mem_of_mem {α : Type u} [DecidableEq α] {a : α} {b : α} {l : List α} (h : a b :: l) :
a = b a b a l
theorem List.mem_pair {α : Type u} {a : α} {b : α} {c : α} :
a [b, c] a = b a = c
@[deprecated List.append_of_mem]
theorem List.mem_split {α : Type u_1} {a : α} {l : List α} :
a l∃ (s : List α), ∃ (t : List α), l = s ++ a :: t

Alias of List.append_of_mem.


See also eq_append_cons_of_mem, which proves a stronger version in which the initial list must not contain the element.

@[simp]
theorem List.mem_map_of_injective {α : Type u} {β : Type v} {f : αβ} (H : Function.Injective f) {a : α} {l : List α} :
f a List.map f l a l
@[simp]
theorem Function.Involutive.exists_mem_and_apply_eq_iff {α : Type u} {f : αα} (hf : Function.Involutive f) (x : α) (l : List α) :
(∃ (y : α), y l f y = x) f x l
theorem List.mem_map_of_involutive {α : Type u} {f : αα} (hf : Function.Involutive f) {a : α} {l : List α} :
a List.map f l f a l

length #

theorem List.length_pos_of_ne_nil {α : Type u_1} {l : List α} :
l []0 < l.length

Alias of the reverse direction of List.length_pos.

theorem List.length_pos_iff_ne_nil {α : Type u} {l : List α} :
0 < l.length l []
theorem List.exists_of_length_succ {α : Type u} {n : } (l : List α) :
l.length = n + 1∃ (h : α), ∃ (t : List α), l = h :: t
@[simp]
theorem List.length_injective {α : Type u} [Subsingleton α] :
Function.Injective List.length
theorem List.length_eq_two {α : Type u} {l : List α} :
l.length = 2 ∃ (a : α), ∃ (b : α), l = [a, b]
theorem List.length_eq_three {α : Type u} {l : List α} :
l.length = 3 ∃ (a : α), ∃ (b : α), ∃ (c : α), l = [a, b, c]

set-theoretic notation of lists #

instance List.instSingletonList {α : Type u} :
Singleton α (List α)
Equations
  • List.instSingletonList = { singleton := fun (x : α) => [x] }
Equations
  • List.instInsertOfDecidableEq_mathlib = { insert := List.insert }
Equations
  • =
theorem List.singleton_eq {α : Type u} (x : α) :
{x} = [x]
theorem List.insert_neg {α : Type u} [DecidableEq α] {x : α} {l : List α} (h : ¬x l) :
insert x l = x :: l
theorem List.insert_pos {α : Type u} [DecidableEq α] {x : α} {l : List α} (h : x l) :
insert x l = l
theorem List.doubleton_eq {α : Type u} [DecidableEq α] {x : α} {y : α} (h : x y) :
{x, y} = [x, y]

bounded quantifiers over lists #

theorem List.forall_mem_of_forall_mem_cons {α : Type u} {p : αProp} {a : α} {l : List α} (h : ∀ (x : α), x a :: lp x) (x : α) :
x lp x
theorem List.exists_mem_cons_of {α : Type u} {p : αProp} {a : α} (l : List α) (h : p a) :
∃ (x : α), x a :: l p x
theorem List.exists_mem_cons_of_exists {α : Type u} {p : αProp} {a : α} {l : List α} :
(∃ (x : α), x l p x)∃ (x : α), x a :: l p x
theorem List.or_exists_of_exists_mem_cons {α : Type u} {p : αProp} {a : α} {l : List α} :
(∃ (x : α), x a :: l p x)p a ∃ (x : α), x l p x
theorem List.exists_mem_cons_iff {α : Type u} (p : αProp) (a : α) (l : List α) :
(∃ (x : α), x a :: l p x) p a ∃ (x : α), x l p x

list subset #

theorem List.cons_subset_of_subset_of_mem {α : Type u} {a : α} {l : List α} {m : List α} (ainm : a m) (lsubm : l m) :
a :: l m
theorem List.append_subset_of_subset_of_subset {α : Type u} {l₁ : List α} {l₂ : List α} {l : List α} (l₁subl : l₁ l) (l₂subl : l₂ l) :
l₁ ++ l₂ l
theorem List.map_subset_iff {α : Type u} {β : Type v} {l₁ : List α} {l₂ : List α} (f : αβ) (h : Function.Injective f) :
List.map f l₁ List.map f l₂ l₁ l₂

append #

theorem List.append_eq_has_append {α : Type u} {L₁ : List α} {L₂ : List α} :
L₁.append L₂ = L₁ ++ L₂
@[deprecated List.append_cancel_left]
theorem List.append_left_cancel {α : Type u_1} {as : List α} {bs : List α} {cs : List α} (h : as ++ bs = as ++ cs) :
bs = cs

Alias of List.append_cancel_left.

@[deprecated List.append_cancel_right]
theorem List.append_right_cancel {α : Type u_1} {as : List α} {bs : List α} {cs : List α} (h : as ++ bs = cs ++ bs) :
as = cs

Alias of List.append_cancel_right.

theorem List.append_right_injective {α : Type u} (s : List α) :
Function.Injective fun (t : List α) => s ++ t
theorem List.append_left_injective {α : Type u} (t : List α) :
Function.Injective fun (s : List α) => s ++ t

replicate #

theorem List.eq_replicate_length {α : Type u} {a : α} {l : List α} :
l = List.replicate l.length a ∀ (b : α), b lb = a
theorem List.replicate_add {α : Type u} (m : ) (n : ) (a : α) :
theorem List.replicate_succ' {α : Type u} (n : ) (a : α) :
theorem List.replicate_subset_singleton {α : Type u} (n : ) (a : α) :
theorem List.subset_singleton_iff {α : Type u} {a : α} {L : List α} :
L [a] ∃ (n : ), L = List.replicate n a
theorem List.replicate_right_inj {α : Type u} {a : α} {b : α} {n : } (hn : n 0) :
theorem List.replicate_right_inj' {α : Type u} {a : α} {b : α} {n : } :
theorem List.replicate_left_inj {α : Type u} {a : α} {n : } {m : } :

pure #

theorem List.mem_pure {α : Type u} (x : α) (y : α) :
x pure y x = y

bind #

@[simp]
theorem List.bind_eq_flatMap {α : Type u_2} {β : Type u_2} (f : αList β) (l : List α) :
l >>= f = l.flatMap f
@[deprecated List.bind_eq_flatMap]
theorem List.bind_eq_bind {α : Type u_2} {β : Type u_2} (f : αList β) (l : List α) :
l >>= f = l.flatMap f

Alias of List.bind_eq_flatMap.

concat #

reverse #

theorem List.reverse_cons' {α : Type u} (a : α) (l : List α) :
(a :: l).reverse = l.reverse.concat a
theorem List.reverse_concat' {α : Type u} (l : List α) (a : α) :
(l ++ [a]).reverse = a :: l.reverse
@[simp]
theorem List.reverse_singleton {α : Type u} (a : α) :
[a].reverse = [a]
@[simp]
theorem List.reverse_involutive {α : Type u} :
Function.Involutive List.reverse
@[simp]
theorem List.reverse_injective {α : Type u} :
Function.Injective List.reverse
theorem List.concat_eq_reverse_cons {α : Type u} (a : α) (l : List α) :
l.concat a = (a :: l.reverse).reverse
theorem List.map_reverseAux {α : Type u} {β : Type v} (f : αβ) (l₁ : List α) (l₂ : List α) :
List.map f (l₁.reverseAux l₂) = (List.map f l₁).reverseAux (List.map f l₂)

getLast #

theorem List.getLast_append_singleton {α : Type u} {a : α} (l : List α) :
(l ++ [a]).getLast = a
theorem List.getLast_append' {α : Type u} (l₁ : List α) (l₂ : List α) (h : l₂ []) :
(l₁ ++ l₂).getLast = l₂.getLast h
theorem List.getLast_concat' {α : Type u} {a : α} (l : List α) :
(l.concat a).getLast = a
@[simp]
theorem List.getLast_singleton' {α : Type u} (a : α) :
[a].getLast = a
@[simp]
theorem List.getLast_cons_cons {α : Type u} (a₁ : α) (a₂ : α) (l : List α) :
(a₁ :: a₂ :: l).getLast = (a₂ :: l).getLast
theorem List.dropLast_append_getLast {α : Type u} {l : List α} (h : l []) :
l.dropLast ++ [l.getLast h] = l
theorem List.getLast_congr {α : Type u} {l₁ : List α} {l₂ : List α} (h₁ : l₁ []) (h₂ : l₂ []) (h₃ : l₁ = l₂) :
l₁.getLast h₁ = l₂.getLast h₂
theorem List.getLast_replicate_succ {α : Type u} (m : ) (a : α) :
(List.replicate (m + 1) a).getLast = a
theorem List.getLast_filter {α : Type u} {p : αBool} (l : List α) (hlp : List.filter p l []) :
p (l.getLast ) = true(List.filter p l).getLast hlp = l.getLast

If the last element of l does not satisfy p, then it is also the last element of l.filter p.

getLast? #

@[deprecated List.getLast?_eq_none_iff]
theorem List.getLast?_eq_none {α : Type u_1} {xs : List α} :
xs.getLast? = none xs = []

Alias of List.getLast?_eq_none_iff.

@[deprecated List.getLast?_eq_none]
theorem List.getLast?_isNone {α : Type u_1} {xs : List α} :
xs.getLast? = none xs = []

Alias of List.getLast?_eq_none_iff.


Alias of List.getLast?_eq_none_iff.

theorem List.mem_getLast?_eq_getLast {α : Type u} {l : List α} {x : α} :
x l.getLast?∃ (h : l []), x = l.getLast h
theorem List.getLast?_eq_getLast_of_ne_nil {α : Type u} {l : List α} (h : l []) :
l.getLast? = some (l.getLast h)
theorem List.mem_getLast?_cons {α : Type u} {x : α} {y : α} {l : List α} :
x l.getLast?x (y :: l).getLast?
theorem List.dropLast_append_getLast? {α : Type u} {l : List α} (a : α) :
a l.getLast?l.dropLast ++ [a] = l
theorem List.getLastI_eq_getLast? {α : Type u} [Inhabited α] (l : List α) :
l.getLastI = l.getLast?.iget
theorem List.getLast?_append_cons {α : Type u} (l₁ : List α) (a : α) (l₂ : List α) :
(l₁ ++ a :: l₂).getLast? = (a :: l₂).getLast?
theorem List.getLast?_append_of_ne_nil {α : Type u} (l₁ : List α) {l₂ : List α} :
l₂ [](l₁ ++ l₂).getLast? = l₂.getLast?
theorem List.mem_getLast?_append_of_mem_getLast? {α : Type u} {l₁ : List α} {l₂ : List α} {x : α} (h : x l₂.getLast?) :
x (l₁ ++ l₂).getLast?

head(!?) and tail #

@[simp]
theorem List.head!_nil {α : Type u} [Inhabited α] :
[].head! = default
@[simp]
theorem List.head_cons_tail {α : Type u} (x : List α) (h : x []) :
x.head h :: x.tail = x
theorem List.head_eq_getElem_zero {α : Type u} {l : List α} (hl : l []) :
l.head hl = l[0]
theorem List.head!_eq_head? {α : Type u} [Inhabited α] (l : List α) :
l.head! = l.head?.iget
theorem List.eq_cons_of_mem_head? {α : Type u} {x : α} {l : List α} :
x l.head?l = x :: l.tail
@[simp]
theorem List.head!_cons {α : Type u} [Inhabited α] (a : α) (l : List α) :
(a :: l).head! = a
@[simp]
theorem List.head!_append {α : Type u} [Inhabited α] (t : List α) {s : List α} (h : s []) :
(s ++ t).head! = s.head!
theorem List.mem_head?_append_of_mem_head? {α : Type u} {s : List α} {t : List α} {x : α} (h : x s.head?) :
x (s ++ t).head?
theorem List.head?_append_of_ne_nil {α : Type u} (l₁ : List α) {l₂ : List α} :
l₁ [](l₁ ++ l₂).head? = l₁.head?
theorem List.tail_append_singleton_of_ne_nil {α : Type u} {a : α} {l : List α} (h : l []) :
(l ++ [a]).tail = l.tail ++ [a]
theorem List.cons_head?_tail {α : Type u} {l : List α} {a : α} :
a l.head?a :: l.tail = l
theorem List.head!_mem_head? {α : Type u} [Inhabited α] {l : List α} :
l []l.head! l.head?
theorem List.cons_head!_tail {α : Type u} [Inhabited α] {l : List α} (h : l []) :
l.head! :: l.tail = l
theorem List.head!_mem_self {α : Type u} [Inhabited α] {l : List α} (h : l []) :
l.head! l
theorem List.get_eq_get? {α : Type u} (l : List α) (i : Fin l.length) :
l.get i = (l.get? i).get
theorem List.exists_mem_iff_getElem {α : Type u} {l : List α} {p : αProp} :
(∃ (x : α), x l p x) ∃ (i : ), ∃ (x : i < l.length), p l[i]
theorem List.forall_mem_iff_getElem {α : Type u} {l : List α} {p : αProp} :
(∀ (x : α), x lp x) ∀ (i : ) (x : i < l.length), p l[i]
theorem List.getElem_cons {α : Type u} {l : List α} {a : α} {n : } (h : n < (a :: l).length) :
(a :: l)[n] = if hn : n = 0 then a else l[n - 1]
theorem List.get_tail {α : Type u} (l : List α) (i : ) (h : i < l.tail.length) (h' : optParam (i + 1 < l.length) ) :
l.tail.get i, h = l.get i + 1, h'
@[deprecated]
theorem List.get_cons {α : Type u} {l : List α} {a : α} {n : } (hl : n < (a :: l).length) :
(a :: l).get n, hl = if hn : n = 0 then a else l.get n - 1,

Induction from the right #

@[irreducible]
def List.reverseRecOn {α : Type u} {motive : List αSort u_2} (l : List α) (nil : motive []) (append_singleton : (l : List α) → (a : α) → motive lmotive (l ++ [a])) :
motive l

Induction principle from the right for lists: if a property holds for the empty list, and for l ++ [a] if it holds for l, then it holds for all lists. The principle is given for a Sort-valued predicate, i.e., it can also be used to construct data.

Equations
  • One or more equations did not get rendered due to their size.
Instances For
    @[simp]
    theorem List.reverseRecOn_nil {α : Type u} {motive : List αSort u_2} (nil : motive []) (append_singleton : (l : List α) → (a : α) → motive lmotive (l ++ [a])) :
    List.reverseRecOn [] nil append_singleton = nil
    @[simp]
    theorem List.reverseRecOn_concat {α : Type u} {motive : List αSort u_2} (x : α) (xs : List α) (nil : motive []) (append_singleton : (l : List α) → (a : α) → motive lmotive (l ++ [a])) :
    List.reverseRecOn (xs ++ [x]) nil append_singleton = append_singleton xs x (List.reverseRecOn xs nil append_singleton)
    @[irreducible]
    def List.bidirectionalRec {α : Type u} {motive : List αSort u_2} (nil : motive []) (singleton : (a : α) → motive [a]) (cons_append : (a : α) → (l : List α) → (b : α) → motive lmotive (a :: (l ++ [b]))) (l : List α) :
    motive l

    Bidirectional induction principle for lists: if a property holds for the empty list, the singleton list, and a :: (l ++ [b]) from l, then it holds for all lists. This can be used to prove statements about palindromes. The principle is given for a Sort-valued predicate, i.e., it can also be used to construct data.

    Equations
    Instances For
      @[simp]
      theorem List.bidirectionalRec_nil {α : Type u} {motive : List αSort u_2} (nil : motive []) (singleton : (a : α) → motive [a]) (cons_append : (a : α) → (l : List α) → (b : α) → motive lmotive (a :: (l ++ [b]))) :
      List.bidirectionalRec nil singleton cons_append [] = nil
      @[simp]
      theorem List.bidirectionalRec_singleton {α : Type u} {motive : List αSort u_2} (nil : motive []) (singleton : (a : α) → motive [a]) (cons_append : (a : α) → (l : List α) → (b : α) → motive lmotive (a :: (l ++ [b]))) (a : α) :
      List.bidirectionalRec nil singleton cons_append [a] = singleton a
      @[simp]
      theorem List.bidirectionalRec_cons_append {α : Type u} {motive : List αSort u_2} (nil : motive []) (singleton : (a : α) → motive [a]) (cons_append : (a : α) → (l : List α) → (b : α) → motive lmotive (a :: (l ++ [b]))) (a : α) (l : List α) (b : α) :
      List.bidirectionalRec nil singleton cons_append (a :: (l ++ [b])) = cons_append a l b (List.bidirectionalRec nil singleton cons_append l)
      @[reducible, inline]
      abbrev List.bidirectionalRecOn {α : Type u} {C : List αSort u_2} (l : List α) (H0 : C []) (H1 : (a : α) → C [a]) (Hn : (a : α) → (l : List α) → (b : α) → C lC (a :: (l ++ [b]))) :
      C l

      Like bidirectionalRec, but with the list parameter placed first.

      Equations
      Instances For

        sublists #

        theorem List.Sublist.cons_cons {α : Type u} {l₁ : List α} {l₂ : List α} (a : α) (s : l₁.Sublist l₂) :
        (a :: l₁).Sublist (a :: l₂)
        theorem List.cons_sublist_cons' {α : Type u} {l₁ : List α} {l₂ : List α} {a : α} {b : α} :
        (a :: l₁).Sublist (b :: l₂) (a :: l₁).Sublist l₂ a = b l₁.Sublist l₂
        theorem List.sublist_cons_of_sublist {α : Type u} {l₁ : List α} {l₂ : List α} (a : α) (h : l₁.Sublist l₂) :
        l₁.Sublist (a :: l₂)
        @[deprecated]
        theorem List.sublist_of_cons_sublist_cons {α : Type u} {l₁ : List α} {l₂ : List α} {a : α} (h : (a :: l₁).Sublist (a :: l₂)) :
        l₁.Sublist l₂
        @[deprecated List.cons_sublist_cons]
        theorem List.cons_sublist_cons_iff :
        ∀ {α : Type u_1} {a : α} {l₁ l₂ : List α}, (a :: l₁).Sublist (a :: l₂) l₁.Sublist l₂

        Alias of List.cons_sublist_cons.

        theorem List.sublist_nil_iff_eq_nil {α : Type u_1} {l : List α} :
        l.Sublist [] l = []

        Alias of List.sublist_nil.

        @[simp]
        theorem List.sublist_singleton {α : Type u} {l : List α} {a : α} :
        l.Sublist [a] l = [] l = [a]
        theorem List.Sublist.antisymm {α : Type u} {l₁ : List α} {l₂ : List α} (s₁ : l₁.Sublist l₂) (s₂ : l₂.Sublist l₁) :
        l₁ = l₂
        instance List.decidableSublist {α : Type u} [DecidableEq α] (l₁ : List α) (l₂ : List α) :
        Decidable (l₁.Sublist l₂)
        Equations

        indexOf #

        @[simp]
        theorem List.indexOf_cons_self {α : Type u} [DecidableEq α] (a : α) (l : List α) :
        List.indexOf a (a :: l) = 0
        theorem List.indexOf_cons_eq {α : Type u} [DecidableEq α] {a : α} {b : α} (l : List α) :
        b = aList.indexOf a (b :: l) = 0
        @[simp]
        theorem List.indexOf_cons_ne {α : Type u} [DecidableEq α] {a : α} {b : α} (l : List α) :
        b aList.indexOf a (b :: l) = (List.indexOf a l).succ
        theorem List.indexOf_eq_length {α : Type u} [DecidableEq α] {a : α} {l : List α} :
        List.indexOf a l = l.length ¬a l
        @[simp]
        theorem List.indexOf_of_not_mem {α : Type u} [DecidableEq α] {l : List α} {a : α} :
        ¬a lList.indexOf a l = l.length
        theorem List.indexOf_le_length {α : Type u} [DecidableEq α] {a : α} {l : List α} :
        List.indexOf a l l.length
        theorem List.indexOf_lt_length {α : Type u} [DecidableEq α] {a : α} {l : List α} :
        List.indexOf a l < l.length a l
        theorem List.indexOf_append_of_mem {α : Type u} {l₁ : List α} {l₂ : List α} [DecidableEq α] {a : α} (h : a l₁) :
        List.indexOf a (l₁ ++ l₂) = List.indexOf a l₁
        theorem List.indexOf_append_of_not_mem {α : Type u} {l₁ : List α} {l₂ : List α} [DecidableEq α] {a : α} (h : ¬a l₁) :
        List.indexOf a (l₁ ++ l₂) = l₁.length + List.indexOf a l₂

        nth element #

        @[simp]
        theorem List.getElem?_length {α : Type u} (l : List α) :
        l[l.length]? = none
        @[deprecated List.getElem?_length]
        theorem List.get?_length {α : Type u} (l : List α) :
        l.get? l.length = none
        @[deprecated List.get?_inj]
        theorem List.get?_injective {i : } :
        ∀ {α : Type u_1} {xs : List α} {j : }, i < xs.lengthxs.Nodupxs.get? i = xs.get? ji = j

        Alias of List.get?_inj.

        theorem List.getElem_map_rev {α : Type u} {β : Type v} (f : αβ) {l : List α} {n : } {h : n < l.length} :
        f l[n] = (List.map f l)[n]

        A version of getElem_map that can be used for rewriting.

        @[deprecated List.getElem_map_rev]
        theorem List.get_map_rev {α : Type u} {β : Type v} (f : αβ) {l : List α} {n : Fin l.length} :
        f (l.get n) = (List.map f l).get n,

        A version of get_map that can be used for rewriting.

        theorem List.get_length_sub_one {α : Type u} {l : List α} (h : l.length - 1 < l.length) :
        l.get l.length - 1, h = l.getLast
        theorem List.take_one_drop_eq_of_lt_length {α : Type u} {l : List α} {n : } (h : n < l.length) :
        List.take 1 (List.drop n l) = [l.get n, h]
        theorem List.ext_get?' {α : Type u} {l₁ : List α} {l₂ : List α} (h' : ∀ (n : ), n < l₁.length l₂.lengthl₁.get? n = l₂.get? n) :
        l₁ = l₂
        theorem List.ext_get?_iff {α : Type u} {l₁ : List α} {l₂ : List α} :
        l₁ = l₂ ∀ (n : ), l₁.get? n = l₂.get? n
        theorem List.ext_get_iff {α : Type u} {l₁ : List α} {l₂ : List α} :
        l₁ = l₂ l₁.length = l₂.length ∀ (n : ) (h₁ : n < l₁.length) (h₂ : n < l₂.length), l₁.get n, h₁ = l₂.get n, h₂
        theorem List.ext_get?_iff' {α : Type u} {l₁ : List α} {l₂ : List α} :
        l₁ = l₂ ∀ (n : ), n < l₁.length l₂.lengthl₁.get? n = l₂.get? n
        @[simp]
        theorem List.getElem_indexOf {α : Type u} [DecidableEq α] {a : α} {l : List α} (h : List.indexOf a l < l.length) :
        l[List.indexOf a l] = a
        theorem List.indexOf_get {α : Type u} [DecidableEq α] {a : α} {l : List α} (h : List.indexOf a l < l.length) :
        l.get List.indexOf a l, h = a
        @[simp]
        theorem List.getElem?_indexOf {α : Type u} [DecidableEq α] {a : α} {l : List α} (h : a l) :
        l[List.indexOf a l]? = some a
        theorem List.indexOf_get? {α : Type u} [DecidableEq α] {a : α} {l : List α} (h : a l) :
        l.get? (List.indexOf a l) = some a
        theorem List.indexOf_inj {α : Type u} [DecidableEq α] {l : List α} {x : α} {y : α} (hx : x l) (hy : y l) :
        @[deprecated List.getElem_reverse]
        theorem List.get_reverse {α : Type u} (l : List α) (i : ) (h1 : l.length - 1 - i < l.reverse.length) (h2 : i < l.length) :
        l.reverse.get l.length - 1 - i, h1 = l.get i, h2
        theorem List.get_reverse' {α : Type u} (l : List α) (n : Fin l.reverse.length) (hn' : l.length - 1 - n < l.length) :
        l.reverse.get n = l.get l.length - 1 - n, hn'
        theorem List.eq_cons_of_length_one {α : Type u} {l : List α} (h : l.length = 1) :
        l = [l.get 0, ]
        theorem List.modifyTailIdx_modifyTailIdx {α : Type u} {f : List αList α} {g : List αList α} (m : ) (n : ) (l : List α) :
        List.modifyTailIdx g (m + n) (List.modifyTailIdx f n l) = List.modifyTailIdx (fun (l : List α) => List.modifyTailIdx g m (f l)) n l
        @[deprecated List.modifyTailIdx_modifyTailIdx]
        theorem List.modifyNthTail_modifyNthTail {α : Type u} {f : List αList α} {g : List αList α} (m : ) (n : ) (l : List α) :
        List.modifyTailIdx g (m + n) (List.modifyTailIdx f n l) = List.modifyTailIdx (fun (l : List α) => List.modifyTailIdx g m (f l)) n l

        Alias of List.modifyTailIdx_modifyTailIdx.

        theorem List.modifyTailIdx_modifyTailIdx_le {α : Type u} {f : List αList α} {g : List αList α} (m : ) (n : ) (l : List α) (h : n m) :
        List.modifyTailIdx g m (List.modifyTailIdx f n l) = List.modifyTailIdx (fun (l : List α) => List.modifyTailIdx g (m - n) (f l)) n l
        @[deprecated List.modifyTailIdx_modifyTailIdx_le]
        theorem List.modifyNthTail_modifyNthTail_le {α : Type u} {f : List αList α} {g : List αList α} (m : ) (n : ) (l : List α) (h : n m) :
        List.modifyTailIdx g m (List.modifyTailIdx f n l) = List.modifyTailIdx (fun (l : List α) => List.modifyTailIdx g (m - n) (f l)) n l

        Alias of List.modifyTailIdx_modifyTailIdx_le.

        theorem List.modifyTailIdx_modifyTailIdx_same {α : Type u} {f : List αList α} {g : List αList α} (n : ) (l : List α) :
        @[deprecated List.modifyTailIdx_modifyTailIdx_same]
        theorem List.modifyNthTail_modifyNthTail_same {α : Type u} {f : List αList α} {g : List αList α} (n : ) (l : List α) :

        Alias of List.modifyTailIdx_modifyTailIdx_same.

        @[deprecated List.eraseIdx_eq_modifyTailIdx]
        theorem List.removeNth_eq_nthTail {α : Type u_1} (n : ) (l : List α) :
        l.eraseIdx n = List.modifyTailIdx List.tail n l

        Alias of List.eraseIdx_eq_modifyTailIdx.

        @[deprecated List.modify_eq_set]
        theorem List.modifyNth_eq_set {α : Type u_1} [Inhabited α] (f : αα) (n : ) (l : List α) :
        List.modify f n l = l.set n (f (l[n]?.getD default))

        Alias of List.modify_eq_set.

        @[simp]
        theorem List.getElem_set_of_ne {α : Type u} {l : List α} {i : } {j : } (h : i j) (a : α) (hj : j < (l.set i a).length) :
        (l.set i a)[j] = l[j]
        @[deprecated List.getElem_set_of_ne]
        theorem List.get_set_of_ne {α : Type u} {l : List α} {i : } {j : } (h : i j) (a : α) (hj : j < (l.set i a).length) :
        (l.set i a).get j, hj = l.get j,

        map #

        @[deprecated List.map_congr_left]
        theorem List.map_congr :
        ∀ {α : Type u_1} {l : List α} {α_1 : Type u_2} {f g : αα_1}, (∀ (a : α), a lf a = g a)List.map f l = List.map g l

        Alias of List.map_congr_left.

        theorem List.flatMap_pure_eq_map {α : Type u} {β : Type v} (f : αβ) (l : List α) :
        l.flatMap (pure f) = List.map f l
        @[deprecated List.flatMap_pure_eq_map]
        theorem List.bind_pure_eq_map {α : Type u} {β : Type v} (f : αβ) (l : List α) :
        l.flatMap (pure f) = List.map f l

        Alias of List.flatMap_pure_eq_map.

        @[deprecated List.flatMap_pure_eq_map]
        theorem List.bind_ret_eq_map {α : Type u} {β : Type v} (f : αβ) (l : List α) :
        l.bind (List.ret f) = List.map f l
        theorem List.flatMap_congr {α : Type u} {β : Type v} {l : List α} {f : αList β} {g : αList β} (h : ∀ (x : α), x lf x = g x) :
        l.flatMap f = l.flatMap g
        @[deprecated List.flatMap_congr]
        theorem List.bind_congr {α : Type u} {β : Type v} {l : List α} {f : αList β} {g : αList β} (h : ∀ (x : α), x lf x = g x) :
        l.flatMap f = l.flatMap g

        Alias of List.flatMap_congr.

        theorem List.infix_flatMap_of_mem {α : Type u} {a : α} {as : List α} (h : a as) (f : αList α) :
        f a <:+: as.flatMap f
        @[deprecated List.infix_flatMap_of_mem]
        theorem List.infix_bind_of_mem {α : Type u} {a : α} {as : List α} (h : a as) (f : αList α) :
        f a <:+: as.flatMap f

        Alias of List.infix_flatMap_of_mem.

        @[simp]
        theorem List.map_eq_map {α : Type u_2} {β : Type u_2} (f : αβ) (l : List α) :
        f <$> l = List.map f l
        theorem List.comp_map {α : Type u} {β : Type v} {γ : Type w} (h : βγ) (g : αβ) (l : List α) :
        List.map (h g) l = List.map h (List.map g l)

        A single List.map of a composition of functions is equal to composing a List.map with another List.map, fully applied. This is the reverse direction of List.map_map.

        @[simp]
        theorem List.map_comp_map {α : Type u} {β : Type v} {γ : Type w} (g : βγ) (f : αβ) :

        Composing a List.map with another List.map is equal to a single List.map of composed functions.

        theorem Function.LeftInverse.list_map {α : Type u} {β : Type v} {f : αβ} {g : βα} (h : Function.LeftInverse f g) :
        theorem Function.RightInverse.list_map {α : Type u} {β : Type v} {f : αβ} {g : βα} (h : Function.RightInverse f g) :
        @[simp]
        theorem List.map_leftInverse_iff {α : Type u} {β : Type v} {f : αβ} {g : βα} :
        @[simp]
        theorem List.map_rightInverse_iff {α : Type u} {β : Type v} {f : αβ} {g : βα} :
        theorem Function.Injective.list_map {α : Type u} {β : Type v} {f : αβ} (h : Function.Injective f) :
        @[simp]
        theorem List.map_injective_iff {α : Type u} {β : Type v} {f : αβ} :
        theorem Function.Surjective.list_map {α : Type u} {β : Type v} {f : αβ} (h : Function.Surjective f) :
        @[simp]
        theorem List.map_surjective_iff {α : Type u} {β : Type v} {f : αβ} :
        theorem Function.Bijective.list_map {α : Type u} {β : Type v} {f : αβ} (h : Function.Bijective f) :
        @[simp]
        theorem List.map_bijective_iff {α : Type u} {β : Type v} {f : αβ} :
        theorem List.eq_of_mem_map_const {α : Type u} {β : Type v} {b₁ : β} {b₂ : β} {l : List α} (h : b₁ List.map (Function.const α b₂) l) :
        b₁ = b₂

        zipWith #

        theorem List.nil_zipWith {α : Type u} {β : Type v} {γ : Type w} (f : αβγ) (l : List β) :
        List.zipWith f [] l = []
        theorem List.zipWith_nil {α : Type u} {β : Type v} {γ : Type w} (f : αβγ) (l : List α) :
        List.zipWith f l [] = []
        @[simp]
        theorem List.zipWith_flip {α : Type u} {β : Type v} {γ : Type w} (f : αβγ) (as : List α) (bs : List β) :
        List.zipWith (flip f) bs as = List.zipWith f as bs

        take, drop #

        @[simp]
        theorem List.take_eq_self_iff {α : Type u} (x : List α) {n : } :
        List.take n x = x x.length n
        @[simp]
        theorem List.take_self_eq_iff {α : Type u} (x : List α) {n : } :
        x = List.take n x x.length n
        @[simp]
        theorem List.take_eq_left_iff {α : Type u} {x : List α} {y : List α} {n : } :
        List.take n (x ++ y) = List.take n x y = [] n x.length
        @[simp]
        theorem List.left_eq_take_iff {α : Type u} {x : List α} {y : List α} {n : } :
        List.take n x = List.take n (x ++ y) y = [] n x.length
        @[simp]
        theorem List.drop_take_append_drop {α : Type u} (x : List α) (m : ) (n : ) :
        @[simp]
        theorem List.drop_take_append_drop' {α : Type u} (x : List α) (m : ) (n : ) :

        Compared to drop_take_append_drop, the order of summands is swapped.

        @[simp]
        theorem List.take_concat_get' {α : Type u} (l : List α) (i : ) (h : i < l.length) :
        List.take i l ++ [l[i]] = List.take (i + 1) l

        take_concat_get in simp normal form

        theorem List.eq_nil_or_concat' {α : Type u} (l : List α) :
        l = [] ∃ (L : List α), ∃ (b : α), l = L ++ [b]

        eq_nil_or_concat in simp normal form

        theorem List.cons_getElem_drop_succ {α : Type u} {l : List α} {n : } {h : n < l.length} :
        l[n] :: List.drop (n + 1) l = List.drop n l
        theorem List.cons_get_drop_succ {α : Type u} {l : List α} {n : Fin l.length} :
        l.get n :: List.drop (n + 1) l = List.drop (↑n) l
        @[simp]
        theorem List.takeI_length {α : Type u} [Inhabited α] (n : ) (l : List α) :
        (List.takeI n l).length = n
        @[simp]
        theorem List.takeI_nil {α : Type u} [Inhabited α] (n : ) :
        List.takeI n [] = List.replicate n default
        theorem List.takeI_eq_take {α : Type u} [Inhabited α] {n : } {l : List α} :
        n l.lengthList.takeI n l = List.take n l
        @[simp]
        theorem List.takeI_left {α : Type u} [Inhabited α] (l₁ : List α) (l₂ : List α) :
        List.takeI l₁.length (l₁ ++ l₂) = l₁
        theorem List.takeI_left' {α : Type u} [Inhabited α] {l₁ : List α} {l₂ : List α} {n : } (h : l₁.length = n) :
        List.takeI n (l₁ ++ l₂) = l₁
        @[simp]
        theorem List.takeD_length {α : Type u} (n : ) (l : List α) (a : α) :
        (List.takeD n l a).length = n
        theorem List.takeD_eq_take {α : Type u} {n : } {l : List α} (a : α) :
        n l.lengthList.takeD n l a = List.take n l
        @[simp]
        theorem List.takeD_left {α : Type u} (l₁ : List α) (l₂ : List α) (a : α) :
        List.takeD l₁.length (l₁ ++ l₂) a = l₁
        theorem List.takeD_left' {α : Type u} {l₁ : List α} {l₂ : List α} {n : } {a : α} (h : l₁.length = n) :
        List.takeD n (l₁ ++ l₂) a = l₁

        foldl, foldr #

        theorem List.foldl_ext {α : Type u} {β : Type v} (f : αβα) (g : αβα) (a : α) {l : List β} (H : ∀ (a : α) (b : β), b lf a b = g a b) :
        List.foldl f a l = List.foldl g a l
        theorem List.foldr_ext {α : Type u} {β : Type v} (f : αββ) (g : αββ) (b : β) {l : List α} (H : ∀ (a : α), a l∀ (b : β), f a b = g a b) :
        List.foldr f b l = List.foldr g b l
        theorem List.foldl_concat {α : Type u} {β : Type v} (f : βαβ) (b : β) (x : α) (xs : List α) :
        List.foldl f b (xs ++ [x]) = f (List.foldl f b xs) x
        theorem List.foldr_concat {α : Type u} {β : Type v} (f : αββ) (b : β) (x : α) (xs : List α) :
        List.foldr f b (xs ++ [x]) = List.foldr f (f x b) xs
        theorem List.foldl_fixed' {α : Type u} {β : Type v} {f : αβα} {a : α} (hf : ∀ (b : β), f a b = a) (l : List β) :
        List.foldl f a l = a
        theorem List.foldr_fixed' {α : Type u} {β : Type v} {f : αββ} {b : β} (hf : ∀ (a : α), f a b = b) (l : List α) :
        List.foldr f b l = b
        @[simp]
        theorem List.foldl_fixed {α : Type u} {β : Type v} {a : α} (l : List β) :
        List.foldl (fun (a : α) (x : β) => a) a l = a
        @[simp]
        theorem List.foldr_fixed {α : Type u} {β : Type v} {b : β} (l : List α) :
        List.foldr (fun (x : α) (b : β) => b) b l = b
        theorem List.foldr_eta {α : Type u} (l : List α) :
        List.foldr List.cons [] l = l
        theorem List.reverse_foldl {α : Type u} {l : List α} :
        (List.foldl (fun (t : List α) (h : α) => h :: t) [] l).reverse = l
        theorem List.foldl_hom₂ {ι : Type u_1} {α : Type u} {β : Type v} {γ : Type w} (l : List ι) (f : αβγ) (op₁ : αια) (op₂ : βιβ) (op₃ : γιγ) (a : α) (b : β) (h : ∀ (a : α) (b : β) (i : ι), f (op₁ a i) (op₂ b i) = op₃ (f a b) i) :
        List.foldl op₃ (f a b) l = f (List.foldl op₁ a l) (List.foldl op₂ b l)
        theorem List.foldr_hom₂ {ι : Type u_1} {α : Type u} {β : Type v} {γ : Type w} (l : List ι) (f : αβγ) (op₁ : ιαα) (op₂ : ιββ) (op₃ : ιγγ) (a : α) (b : β) (h : ∀ (a : α) (b : β) (i : ι), f (op₁ i a) (op₂ i b) = op₃ i (f a b)) :
        List.foldr op₃ (f a b) l = f (List.foldr op₁ a l) (List.foldr op₂ b l)
        theorem List.injective_foldl_comp {α : Type u} {l : List (αα)} {f : αα} (hl : ∀ (f : αα), f lFunction.Injective f) (hf : Function.Injective f) :
        Function.Injective (List.foldl Function.comp f l)
        theorem List.append_cons_inj_of_not_mem {α : Type u} {x₁ : List α} {x₂ : List α} {z₁ : List α} {z₂ : List α} {a₁ : α} {a₂ : α} (notin_x : ¬a₂ x₁) (notin_z : ¬a₂ z₁) :
        x₁ ++ a₁ :: z₁ = x₂ ++ a₂ :: z₂ x₁ = x₂ a₁ = a₂ z₁ = z₂

        Consider two lists l₁ and l₂ with designated elements a₁ and a₂ somewhere in them: l₁ = x₁ ++ [a₁] ++ z₁ and l₂ = x₂ ++ [a₂] ++ z₂. Assume the designated element a₂ is present in neither x₁ nor z₁. We conclude that the lists are equal (l₁ = l₂) if and only if their respective parts are equal (x₁ = x₂ ∧ a₁ = a₂ ∧ z₁ = z₂).

        theorem List.length_scanl {α : Type u} {β : Type v} {f : βαβ} (a : β) (l : List α) :
        (List.scanl f a l).length = l.length + 1
        @[simp]
        theorem List.scanl_nil {α : Type u} {β : Type v} {f : βαβ} (b : β) :
        List.scanl f b [] = [b]
        @[simp]
        theorem List.scanl_cons {α : Type u} {β : Type v} {f : βαβ} {b : β} {a : α} {l : List α} :
        List.scanl f b (a :: l) = [b] ++ List.scanl f (f b a) l
        @[simp]
        theorem List.getElem?_scanl_zero {α : Type u} {β : Type v} {f : βαβ} {b : β} {l : List α} :
        (List.scanl f b l)[0]? = some b
        @[deprecated List.getElem?_scanl_zero]
        theorem List.get?_zero_scanl {α : Type u} {β : Type v} {f : βαβ} {b : β} {l : List α} :
        (List.scanl f b l).get? 0 = some b
        @[simp]
        theorem List.getElem_scanl_zero {α : Type u} {β : Type v} {f : βαβ} {b : β} {l : List α} {h : 0 < (List.scanl f b l).length} :
        (List.scanl f b l)[0] = b
        @[deprecated List.getElem_scanl_zero]
        theorem List.get_zero_scanl {α : Type u} {β : Type v} {f : βαβ} {b : β} {l : List α} {h : 0 < (List.scanl f b l).length} :
        (List.scanl f b l).get 0, h = b
        theorem List.get?_succ_scanl {α : Type u} {β : Type v} {f : βαβ} {b : β} {l : List α} {i : } :
        (List.scanl f b l).get? (i + 1) = ((List.scanl f b l).get? i).bind fun (x : β) => Option.map (fun (y : α) => f x y) (l.get? i)
        theorem List.getElem_succ_scanl {α : Type u} {β : Type v} {f : βαβ} {b : β} {l : List α} {i : } (h : i + 1 < (List.scanl f b l).length) :
        (List.scanl f b l)[i + 1] = f (List.scanl f b l)[i] l[i]
        @[deprecated List.getElem_succ_scanl]
        theorem List.get_succ_scanl {α : Type u} {β : Type v} {f : βαβ} {b : β} {l : List α} {i : } {h : i + 1 < (List.scanl f b l).length} :
        (List.scanl f b l).get i + 1, h = f ((List.scanl f b l).get i, ) (l.get i, )
        @[simp]
        theorem List.scanr_nil {α : Type u} {β : Type v} (f : αββ) (b : β) :
        List.scanr f b [] = [b]
        @[simp]
        theorem List.scanr_cons {α : Type u} {β : Type v} (f : αββ) (b : β) (a : α) (l : List α) :
        List.scanr f b (a :: l) = List.foldr f b (a :: l) :: List.scanr f b l
        theorem List.foldl1_eq_foldr1 {α : Type u} {f : ααα} [hassoc : Std.Associative f] (a : α) (b : α) (l : List α) :
        List.foldl f a (l ++ [b]) = List.foldr f b (a :: l)
        theorem List.foldl_eq_of_comm_of_assoc {α : Type u} {f : ααα} [hcomm : Std.Commutative f] [hassoc : Std.Associative f] (a : α) (b : α) (l : List α) :
        List.foldl f a (b :: l) = f b (List.foldl f a l)
        theorem List.foldl_eq_foldr {α : Type u} {f : ααα} [Std.Commutative f] [Std.Associative f] (a : α) (l : List α) :
        List.foldl f a l = List.foldr f a l
        theorem List.foldl_eq_of_comm' {α : Type u} {β : Type v} {f : αβα} (hf : ∀ (a : α) (b c : β), f (f a b) c = f (f a c) b) (a : α) (b : β) (l : List β) :
        List.foldl f a (b :: l) = f (List.foldl f a l) b
        theorem List.foldl_eq_foldr' {α : Type u} {β : Type v} {f : αβα} (hf : ∀ (a : α) (b c : β), f (f a b) c = f (f a c) b) (a : α) (l : List β) :
        List.foldl f a l = List.foldr (flip f) a l
        theorem List.foldr_eq_of_comm' {α : Type u} {β : Type v} {f : αββ} (hf : ∀ (a b : α) (c : β), f a (f b c) = f b (f a c)) (a : β) (b : α) (l : List α) :
        List.foldr f a (b :: l) = List.foldr f (f b a) l
        theorem List.foldl_op_eq_op_foldr_assoc {α : Type u} {op : ααα} [ha : Std.Associative op] {l : List α} {a₁ : α} {a₂ : α} :
        op (List.foldl op a₁ l) a₂ = op a₁ (List.foldr (fun (x1 x2 : α) => op x1 x2) a₂ l)
        theorem List.foldl_assoc_comm_cons {α : Type u} {op : ααα} [ha : Std.Associative op] [hc : Std.Commutative op] {l : List α} {a₁ : α} {a₂ : α} :
        List.foldl op a₂ (a₁ :: l) = op a₁ (List.foldl op a₂ l)

        foldlM, foldrM, mapM #

        theorem List.foldrM_eq_foldr {α : Type u} {β : Type v} {m : Type v → Type w} [Monad m] [LawfulMonad m] (f : αβm β) (b : β) (l : List α) :
        List.foldrM f b l = List.foldr (fun (a : α) (mb : m β) => mb >>= f a) (pure b) l
        theorem List.foldlM_eq_foldl {α : Type u} {β : Type v} {m : Type v → Type w} [Monad m] [LawfulMonad m] (f : βαm β) (b : β) (l : List α) :
        List.foldlM f b l = List.foldl (fun (mb : m β) (a : α) => do let bmb f b a) (pure b) l

        intersperse #

        @[simp]
        theorem List.intersperse_singleton {α : Type u} (a : α) (b : α) :
        @[simp]
        theorem List.intersperse_cons_cons {α : Type u} (a : α) (b : α) (c : α) (tl : List α) :
        List.intersperse a (b :: c :: tl) = b :: a :: List.intersperse a (c :: tl)

        splitAt and splitOn #

        @[deprecated List.splitAt_eq]
        theorem List.splitAt_eq_take_drop {α : Type u_1} (n : ) (l : List α) :

        Alias of List.splitAt_eq.

        @[simp]
        theorem List.splitOn_nil {α : Type u} [DecidableEq α] (a : α) :
        List.splitOn a [] = [[]]
        @[simp]
        theorem List.splitOnP_nil {α : Type u} (p : αBool) :
        List.splitOnP p [] = [[]]
        theorem List.splitOnP.go_ne_nil {α : Type u} (p : αBool) (xs : List α) (acc : List α) :
        List.splitOnP.go p xs acc []
        theorem List.splitOnP.go_acc {α : Type u} (p : αBool) (xs : List α) (acc : List α) :
        List.splitOnP.go p xs acc = List.modifyHead (fun (x : List α) => acc.reverse ++ x) (List.splitOnP p xs)
        theorem List.splitOnP_ne_nil {α : Type u} (p : αBool) (xs : List α) :
        @[simp]
        theorem List.splitOnP_cons {α : Type u} (p : αBool) (x : α) (xs : List α) :
        List.splitOnP p (x :: xs) = if p x = true then [] :: List.splitOnP p xs else List.modifyHead (List.cons x) (List.splitOnP p xs)
        theorem List.splitOnP_spec {α : Type u} (p : αBool) (as : List α) :
        (List.zipWith (fun (x1 x2 : List α) => x1 ++ x2) (List.splitOnP p as) (List.map (fun (x : α) => [x]) (List.filter p as) ++ [[]])).flatten = as

        The original list L can be recovered by flattening the lists produced by splitOnP p L, interspersed with the elements L.filter p.

        theorem List.splitOnP_spec.flatten_zipWith {α : Type u} {xs : List (List α)} {ys : List (List α)} {a : α} (hxs : xs []) (hys : ys []) :
        (List.zipWith (fun (x x_1 : List α) => x ++ x_1) (List.modifyHead (List.cons a) xs) ys).flatten = a :: (List.zipWith (fun (x x_1 : List α) => x ++ x_1) xs ys).flatten
        theorem List.splitOnP_eq_single {α : Type u} (p : αBool) (xs : List α) (h : ∀ (x : α), x xs¬p x = true) :
        List.splitOnP p xs = [xs]

        If no element satisfies p in the list xs, then xs.splitOnP p = [xs]

        theorem List.splitOnP_first {α : Type u} (p : αBool) (xs : List α) (h : ∀ (x : α), x xs¬p x = true) (sep : α) (hsep : p sep = true) (as : List α) :
        List.splitOnP p (xs ++ sep :: as) = xs :: List.splitOnP p as

        When a list of the form [...xs, sep, ...as] is split on p, the first element is xs, assuming no element in xs satisfies p but sep does satisfy p

        theorem List.intercalate_splitOn {α : Type u} (xs : List α) (x : α) [DecidableEq α] :
        [x].intercalate (List.splitOn x xs) = xs

        intercalate [x] is the left inverse of splitOn x

        theorem List.splitOn_intercalate {α : Type u} (ls : List (List α)) [DecidableEq α] (x : α) (hx : ∀ (l : List α), l ls¬x l) (hls : ls []) :
        List.splitOn x ([x].intercalate ls) = ls

        splitOn x is the left inverse of intercalate [x], on the domain consisting of each nonempty list of lists ls whose elements do not contain x

        modifyLast #

        theorem List.modifyLast.go_append_one {α : Type u} (f : αα) (a : α) (tl : List α) (r : Array α) :
        List.modifyLast.go f (tl ++ [a]) r = r.toListAppend (List.modifyLast.go f (tl ++ [a]) #[])
        theorem List.modifyLast_append_one {α : Type u} (f : αα) (a : α) (l : List α) :
        List.modifyLast f (l ++ [a]) = l ++ [f a]
        theorem List.modifyLast_append {α : Type u} (f : αα) (l₁ : List α) (l₂ : List α) :
        l₂ []List.modifyLast f (l₁ ++ l₂) = l₁ ++ List.modifyLast f l₂

        map for partial functions #

        theorem List.sizeOf_lt_sizeOf_of_mem {α : Type u} [SizeOf α] {x : α} {l : List α} (hx : x l) :
        @[deprecated List.attach_map_coe]
        theorem List.attach_map_coe' {α : Type u_1} {β : Type u_2} (l : List α) (f : αβ) :
        List.map (fun (i : { i : α // i l }) => f i) l.attach = List.map f l

        Alias of List.attach_map_coe.

        @[deprecated List.attach_map_val]
        theorem List.attach_map_val' {α : Type u_1} {β : Type u_2} (l : List α) (f : αβ) :
        List.map (fun (i : { x : α // x l }) => f i) l.attach = List.map f l

        Alias of List.attach_map_val.

        find #

        @[deprecated List.mem_of_find?_eq_some]
        theorem List.find?_mem :
        ∀ {α : Type u_1} {p : αBool} {a : α} {l : List α}, List.find? p l = some aa l

        Alias of List.mem_of_find?_eq_some.

        lookmap #

        theorem List.lookmap.go_append {α : Type u} (f : αOption α) (l : List α) (acc : Array α) :
        List.lookmap.go f l acc = acc.toListAppend (List.lookmap f l)
        @[simp]
        theorem List.lookmap_nil {α : Type u} (f : αOption α) :
        List.lookmap f [] = []
        @[simp]
        theorem List.lookmap_cons_none {α : Type u} (f : αOption α) {a : α} (l : List α) (h : f a = none) :
        @[simp]
        theorem List.lookmap_cons_some {α : Type u} (f : αOption α) {a : α} {b : α} (l : List α) (h : f a = some b) :
        List.lookmap f (a :: l) = b :: l
        theorem List.lookmap_some {α : Type u} (l : List α) :
        List.lookmap some l = l
        theorem List.lookmap_none {α : Type u} (l : List α) :
        List.lookmap (fun (x : α) => none) l = l
        theorem List.lookmap_congr {α : Type u} {f : αOption α} {g : αOption α} {l : List α} :
        (∀ (a : α), a lf a = g a)List.lookmap f l = List.lookmap g l
        theorem List.lookmap_of_forall_not {α : Type u} (f : αOption α) {l : List α} (H : ∀ (a : α), a lf a = none) :
        theorem List.lookmap_map_eq {α : Type u} {β : Type v} (f : αOption α) (g : αβ) (h : ∀ (a b : α), b f ag a = g b) (l : List α) :
        theorem List.lookmap_id' {α : Type u} (f : αOption α) (h : ∀ (a b : α), b f aa = b) (l : List α) :
        theorem List.length_lookmap {α : Type u} (f : αOption α) (l : List α) :
        (List.lookmap f l).length = l.length

        filter #

        theorem List.length_eq_length_filter_add {α : Type u} {l : List α} (f : αBool) :
        l.length = (List.filter f l).length + (List.filter (fun (x : α) => !f x) l).length

        filterMap #

        theorem List.filterMap_eq_flatMap_toList {α : Type u} {β : Type v} (f : αOption β) (l : List α) :
        List.filterMap f l = l.flatMap fun (a : α) => (f a).toList
        @[deprecated List.filterMap_eq_flatMap_toList]
        theorem List.filterMap_eq_bind_toList {α : Type u} {β : Type v} (f : αOption β) (l : List α) :
        List.filterMap f l = l.flatMap fun (a : α) => (f a).toList

        Alias of List.filterMap_eq_flatMap_toList.

        theorem List.filterMap_congr {α : Type u} {β : Type v} {f : αOption β} {g : αOption β} {l : List α} (h : ∀ (x : α), x lf x = g x) :
        theorem List.filterMap_eq_map_iff_forall_eq_some {α : Type u} {β : Type v} {f : αOption β} {g : αβ} {l : List α} :
        List.filterMap f l = List.map g l ∀ (x : α), x lf x = some (g x)

        filter #

        theorem List.filter_singleton {α : Type u} {p : αBool} {a : α} :
        List.filter p [a] = bif p a then [a] else []
        theorem List.filter_eq_foldr {α : Type u} (p : αBool) (l : List α) :
        List.filter p l = List.foldr (fun (a : α) (out : List α) => bif p a then a :: out else out) [] l
        @[simp]
        theorem List.filter_subset' {α : Type u} {p : αBool} (l : List α) :
        theorem List.of_mem_filter {α : Type u} {p : αBool} {a : α} {l : List α} (h : a List.filter p l) :
        p a = true
        theorem List.mem_of_mem_filter {α : Type u} {p : αBool} {a : α} {l : List α} (h : a List.filter p l) :
        a l
        theorem List.mem_filter_of_mem {α : Type u} {p : αBool} {a : α} {l : List α} (h₁ : a l) (h₂ : p a = true) :
        theorem List.monotone_filter_left {α : Type u} (p : αBool) ⦃l : List α ⦃l' : List α (h : l l') :
        theorem List.monotone_filter_right {α : Type u} (l : List α) ⦃p : αBool ⦃q : αBool (h : ∀ (a : α), p a = trueq a = true) :
        (List.filter p l).Sublist (List.filter q l)
        theorem List.map_filter' {α : Type u} {β : Type v} (p : αBool) {f : αβ} (hf : Function.Injective f) (l : List α) [DecidablePred fun (b : β) => ∃ (a : α), p a = true f a = b] :
        List.map f (List.filter p l) = List.filter (fun (b : β) => decide (∃ (a : α), p a = true f a = b)) (List.map f l)
        theorem List.filter_attach' {α : Type u} (l : List α) (p : { a : α // a l }Bool) [DecidableEq α] :
        List.filter p l.attach = List.map (Subtype.map id ) (List.filter (fun (x : α) => decide (∃ (h : x l), p x, h = true)) l).attach
        theorem List.filter_attach {α : Type u} (l : List α) (p : αBool) :
        List.filter (fun (x : { x : α // x l }) => p x) l.attach = List.map (Subtype.map id ) (List.filter p l).attach
        theorem List.filter_comm {α : Type u} (p : αBool) (q : αBool) (l : List α) :
        @[simp]
        theorem List.filter_true {α : Type u} (l : List α) :
        List.filter (fun (x : α) => true) l = l
        @[simp]
        theorem List.filter_false {α : Type u} (l : List α) :
        List.filter (fun (x : α) => false) l = []
        theorem List.span.loop_eq_take_drop {α : Type u} (p : αBool) (l₁ : List α) (l₂ : List α) :
        List.span.loop p l₁ l₂ = (l₂.reverse ++ List.takeWhile p l₁, List.dropWhile p l₁)
        @[simp]
        theorem List.span_eq_take_drop {α : Type u} (p : αBool) (l : List α) :
        theorem List.dropWhile_get_zero_not {α : Type u} (p : αBool) (l : List α) (hl : 0 < (List.dropWhile p l).length) :
        ¬p ((List.dropWhile p l).get 0, hl) = true
        @[deprecated List.getElem_cons]
        theorem List.nthLe_cons {α : Type u} {l : List α} {a : α} {n : } (h : n < (a :: l).length) :
        (a :: l)[n] = if hn : n = 0 then a else l[n - 1]

        Alias of List.getElem_cons.

        @[deprecated List.dropWhile_get_zero_not]
        theorem List.dropWhile_nthLe_zero_not {α : Type u} (p : αBool) (l : List α) (hl : 0 < (List.dropWhile p l).length) :
        ¬p ((List.dropWhile p l).get 0, hl) = true

        Alias of List.dropWhile_get_zero_not.

        @[simp]
        theorem List.dropWhile_eq_nil_iff {α : Type u} {p : αBool} {l : List α} :
        List.dropWhile p l = [] ∀ (x : α), x lp x = true
        @[simp]
        theorem List.takeWhile_eq_self_iff {α : Type u} {p : αBool} {l : List α} :
        List.takeWhile p l = l ∀ (x : α), x lp x = true
        @[simp]
        theorem List.takeWhile_eq_nil_iff {α : Type u} {p : αBool} {l : List α} :
        List.takeWhile p l = [] ∀ (hl : 0 < l.length), ¬p (l.get 0, hl) = true
        theorem List.mem_takeWhile_imp {α : Type u} {p : αBool} {l : List α} {x : α} (hx : x List.takeWhile p l) :
        p x = true
        theorem List.takeWhile_takeWhile {α : Type u} (p : αBool) (q : αBool) (l : List α) :
        List.takeWhile p (List.takeWhile q l) = List.takeWhile (fun (a : α) => decide (p a = true q a = true)) l
        theorem List.takeWhile_idem {α : Type u} {p : αBool} {l : List α} :

        erasep #

        @[simp]
        theorem List.length_eraseP_add_one {α : Type u} {p : αBool} {l : List α} {a : α} (al : a l) (pa : p a = true) :
        (List.eraseP p l).length + 1 = l.length

        erase #

        @[simp]
        theorem List.length_erase_add_one {α : Type u} [DecidableEq α] {a : α} {l : List α} (h : a l) :
        (l.erase a).length + 1 = l.length
        theorem List.map_erase {α : Type u} {β : Type v} [DecidableEq α] [DecidableEq β] {f : αβ} (finj : Function.Injective f) {a : α} (l : List α) :
        List.map f (l.erase a) = (List.map f l).erase (f a)
        theorem List.map_foldl_erase {α : Type u} {β : Type v} [DecidableEq α] [DecidableEq β] {f : αβ} (finj : Function.Injective f) {l₁ : List α} {l₂ : List α} :
        List.map f (List.foldl List.erase l₁ l₂) = List.foldl (fun (l : List β) (a : α) => l.erase (f a)) (List.map f l₁) l₂
        theorem List.erase_getElem {ι : Type u_1} [DecidableEq ι] {l : List ι} {i : } (hi : i < l.length) :
        (l.erase l[i]).Perm (l.eraseIdx i)
        @[deprecated List.erase_getElem]
        theorem List.erase_get {ι : Type u_1} [DecidableEq ι] {l : List ι} (i : Fin l.length) :
        (l.erase (l.get i)).Perm (l.eraseIdx i)
        theorem List.length_eraseIdx_add_one {ι : Type u_1} {l : List ι} {i : } (h : i < l.length) :
        (l.eraseIdx i).length + 1 = l.length

        diff #

        @[simp]
        theorem List.map_diff {α : Type u} {β : Type v} [DecidableEq α] [DecidableEq β] {f : αβ} (finj : Function.Injective f) {l₁ : List α} {l₂ : List α} :
        List.map f (l₁.diff l₂) = (List.map f l₁).diff (List.map f l₂)
        theorem List.erase_diff_erase_sublist_of_sublist {α : Type u} [DecidableEq α] {a : α} {l₁ : List α} {l₂ : List α} :
        l₁.Sublist l₂((l₂.erase a).diff (l₁.erase a)).Sublist (l₂.diff l₁)
        theorem List.choose_spec {α : Type u} (p : αProp) [DecidablePred p] (l : List α) (hp : ∃ (a : α), a l p a) :
        List.choose p l hp l p (List.choose p l hp)
        theorem List.choose_mem {α : Type u} (p : αProp) [DecidablePred p] (l : List α) (hp : ∃ (a : α), a l p a) :
        List.choose p l hp l
        theorem List.choose_property {α : Type u} (p : αProp) [DecidablePred p] (l : List α) (hp : ∃ (a : α), a l p a) :
        p (List.choose p l hp)

        map₂Left' #

        @[simp]
        theorem List.map₂Left'_nil_right {α : Type u} {β : Type v} {γ : Type w} (f : αOption βγ) (as : List α) :
        List.map₂Left' f as [] = (List.map (fun (a : α) => f a none) as, [])

        map₂Right' #

        @[simp]
        theorem List.map₂Right'_nil_left {α : Type u} {β : Type v} {γ : Type w} (f : Option αβγ) (bs : List β) :
        List.map₂Right' f [] bs = (List.map (f none) bs, [])
        @[simp]
        theorem List.map₂Right'_nil_right {α : Type u} {β : Type v} {γ : Type w} (f : Option αβγ) (as : List α) :
        List.map₂Right' f as [] = ([], as)
        @[simp]
        theorem List.map₂Right'_nil_cons {α : Type u} {β : Type v} {γ : Type w} (f : Option αβγ) (b : β) (bs : List β) :
        List.map₂Right' f [] (b :: bs) = (f none b :: List.map (f none) bs, [])
        @[simp]
        theorem List.map₂Right'_cons_cons {α : Type u} {β : Type v} {γ : Type w} (f : Option αβγ) (a : α) (as : List α) (b : β) (bs : List β) :
        List.map₂Right' f (a :: as) (b :: bs) = let r := List.map₂Right' f as bs; (f (some a) b :: r.1, r.2)

        zipLeft' #

        @[simp]
        theorem List.zipLeft'_nil_right {α : Type u} {β : Type v} (as : List α) :
        as.zipLeft' [] = (List.map (fun (a : α) => (a, none)) as, [])
        @[simp]
        theorem List.zipLeft'_nil_left {α : Type u} {β : Type v} (bs : List β) :
        [].zipLeft' bs = ([], bs)
        @[simp]
        theorem List.zipLeft'_cons_nil {α : Type u} {β : Type v} (a : α) (as : List α) :
        (a :: as).zipLeft' [] = ((a, none) :: List.map (fun (a : α) => (a, none)) as, [])
        @[simp]
        theorem List.zipLeft'_cons_cons {α : Type u} {β : Type v} (a : α) (as : List α) (b : β) (bs : List β) :
        (a :: as).zipLeft' (b :: bs) = let r := as.zipLeft' bs; ((a, some b) :: r.1, r.2)

        zipRight' #

        @[simp]
        theorem List.zipRight'_nil_left {α : Type u} {β : Type v} (bs : List β) :
        [].zipRight' bs = (List.map (fun (b : β) => (none, b)) bs, [])
        @[simp]
        theorem List.zipRight'_nil_right {α : Type u} {β : Type v} (as : List α) :
        as.zipRight' [] = ([], as)
        @[simp]
        theorem List.zipRight'_nil_cons {α : Type u} {β : Type v} (b : β) (bs : List β) :
        [].zipRight' (b :: bs) = ((none, b) :: List.map (fun (b : β) => (none, b)) bs, [])
        @[simp]
        theorem List.zipRight'_cons_cons {α : Type u} {β : Type v} (a : α) (as : List α) (b : β) (bs : List β) :
        (a :: as).zipRight' (b :: bs) = let r := as.zipRight' bs; ((some a, b) :: r.1, r.2)

        map₂Left #

        @[simp]
        theorem List.map₂Left_nil_right {α : Type u} {β : Type v} {γ : Type w} (f : αOption βγ) (as : List α) :
        List.map₂Left f as [] = List.map (fun (a : α) => f a none) as
        theorem List.map₂Left_eq_map₂Left' {α : Type u} {β : Type v} {γ : Type w} (f : αOption βγ) (as : List α) (bs : List β) :
        List.map₂Left f as bs = (List.map₂Left' f as bs).1
        theorem List.map₂Left_eq_zipWith {α : Type u} {β : Type v} {γ : Type w} (f : αOption βγ) (as : List α) (bs : List β) :
        as.length bs.lengthList.map₂Left f as bs = List.zipWith (fun (a : α) (b : β) => f a (some b)) as bs

        map₂Right #

        @[simp]
        theorem List.map₂Right_nil_left {α : Type u} {β : Type v} {γ : Type w} (f : Option αβγ) (bs : List β) :
        List.map₂Right f [] bs = List.map (f none) bs
        @[simp]
        theorem List.map₂Right_nil_right {α : Type u} {β : Type v} {γ : Type w} (f : Option αβγ) (as : List α) :
        List.map₂Right f as [] = []
        @[simp]
        theorem List.map₂Right_nil_cons {α : Type u} {β : Type v} {γ : Type w} (f : Option αβγ) (b : β) (bs : List β) :
        List.map₂Right f [] (b :: bs) = f none b :: List.map (f none) bs
        @[simp]
        theorem List.map₂Right_cons_cons {α : Type u} {β : Type v} {γ : Type w} (f : Option αβγ) (a : α) (as : List α) (b : β) (bs : List β) :
        List.map₂Right f (a :: as) (b :: bs) = f (some a) b :: List.map₂Right f as bs
        theorem List.map₂Right_eq_map₂Right' {α : Type u} {β : Type v} {γ : Type w} (f : Option αβγ) (as : List α) (bs : List β) :
        theorem List.map₂Right_eq_zipWith {α : Type u} {β : Type v} {γ : Type w} (f : Option αβγ) (as : List α) (bs : List β) (h : bs.length as.length) :
        List.map₂Right f as bs = List.zipWith (fun (a : α) (b : β) => f (some a) b) as bs

        zipLeft #

        @[simp]
        theorem List.zipLeft_nil_right {α : Type u} {β : Type v} (as : List α) :
        as.zipLeft [] = List.map (fun (a : α) => (a, none)) as
        @[simp]
        theorem List.zipLeft_nil_left {α : Type u} {β : Type v} (bs : List β) :
        [].zipLeft bs = []
        @[simp]
        theorem List.zipLeft_cons_nil {α : Type u} {β : Type v} (a : α) (as : List α) :
        (a :: as).zipLeft [] = (a, none) :: List.map (fun (a : α) => (a, none)) as
        @[simp]
        theorem List.zipLeft_cons_cons {α : Type u} {β : Type v} (a : α) (as : List α) (b : β) (bs : List β) :
        (a :: as).zipLeft (b :: bs) = (a, some b) :: as.zipLeft bs
        theorem List.zipLeft_eq_zipLeft' {α : Type u} {β : Type v} (as : List α) (bs : List β) :
        as.zipLeft bs = (as.zipLeft' bs).1

        zipRight #

        @[simp]
        theorem List.zipRight_nil_left {α : Type u} {β : Type v} (bs : List β) :
        [].zipRight bs = List.map (fun (b : β) => (none, b)) bs
        @[simp]
        theorem List.zipRight_nil_right {α : Type u} {β : Type v} (as : List α) :
        as.zipRight [] = []
        @[simp]
        theorem List.zipRight_nil_cons {α : Type u} {β : Type v} (b : β) (bs : List β) :
        [].zipRight (b :: bs) = (none, b) :: List.map (fun (b : β) => (none, b)) bs
        @[simp]
        theorem List.zipRight_cons_cons {α : Type u} {β : Type v} (a : α) (as : List α) (b : β) (bs : List β) :
        (a :: as).zipRight (b :: bs) = (some a, b) :: as.zipRight bs
        theorem List.zipRight_eq_zipRight' {α : Type u} {β : Type v} (as : List α) (bs : List β) :
        as.zipRight bs = (as.zipRight' bs).1

        Forall #

        @[simp]
        theorem List.forall_cons {α : Type u} (p : αProp) (x : α) (l : List α) :
        List.Forall p (x :: l) p x List.Forall p l
        theorem List.forall_iff_forall_mem {α : Type u} {p : αProp} {l : List α} :
        List.Forall p l ∀ (x : α), x lp x
        theorem List.Forall.imp {α : Type u} {p : αProp} {q : αProp} (h : ∀ (x : α), p xq x) {l : List α} :
        @[simp]
        theorem List.forall_map_iff {α : Type u} {β : Type v} {l : List α} {p : βProp} (f : αβ) :
        Equations

        Miscellaneous lemmas #

        theorem List.get_attach {α : Type u} (L : List α) (i : Fin L.attach.length) :
        (L.attach.get i) = L.get i,
        @[simp]
        theorem List.mem_map_swap {α : Type u} {β : Type v} (x : α) (y : β) (xs : List (α × β)) :
        (y, x) List.map Prod.swap xs (x, y) xs
        theorem List.dropSlice_eq {α : Type u} (xs : List α) (n : ) (m : ) :
        List.dropSlice n m xs = List.take n xs ++ List.drop (n + m) xs
        @[simp]
        theorem List.length_dropSlice {α : Type u} (i : ) (j : ) (xs : List α) :
        (List.dropSlice i j xs).length = xs.length - j (xs.length - i)
        theorem List.length_dropSlice_lt {α : Type u} (i : ) (j : ) (hj : 0 < j) (xs : List α) (hi : i < xs.length) :
        (List.dropSlice i j xs).length < xs.length
        @[deprecated]
        theorem List.sizeOf_dropSlice_lt {α : Type u} [SizeOf α] (i : ) (j : ) (hj : 0 < j) (xs : List α) (hi : i < xs.length) :
        theorem List.disjoint_pmap {α : Type u} {β : Type v} {p : αProp} {f : (a : α) → p aβ} {s : List α} {t : List α} (hs : ∀ (a : α), a sp a) (ht : ∀ (a : α), a tp a) (hf : ∀ (a a' : α) (ha : p a) (ha' : p a'), f a ha = f a' ha'a = a') (h : s.Disjoint t) :
        (List.pmap f s hs).Disjoint (List.pmap f t ht)

        The images of disjoint lists under a partially defined map are disjoint

        theorem List.disjoint_map {α : Type u} {β : Type v} {f : αβ} {s : List α} {t : List α} (hf : Function.Injective f) (h : s.Disjoint t) :
        (List.map f s).Disjoint (List.map f t)

        The images of disjoint lists under an injective map are disjoint

        theorem List.Disjoint.map {α : Type u} {β : Type v} {f : αβ} {s : List α} {t : List α} (hf : Function.Injective f) (h : s.Disjoint t) :
        (List.map f s).Disjoint (List.map f t)

        Alias of List.disjoint_map.


        The images of disjoint lists under an injective map are disjoint

        theorem List.Disjoint.of_map {α : Type u} {β : Type v} {f : αβ} {s : List α} {t : List α} (h : (List.map f s).Disjoint (List.map f t)) :
        s.Disjoint t
        theorem List.Disjoint.map_iff {α : Type u} {β : Type v} {f : αβ} {s : List α} {t : List α} (hf : Function.Injective f) :
        (List.map f s).Disjoint (List.map f t) s.Disjoint t
        theorem List.Perm.disjoint_left {α : Type u} {l₁ : List α} {l₂ : List α} {l : List α} (p : l₁.Perm l₂) :
        l₁.Disjoint l l₂.Disjoint l
        theorem List.Perm.disjoint_right {α : Type u} {l₁ : List α} {l₂ : List α} {l : List α} (p : l₁.Perm l₂) :
        l.Disjoint l₁ l.Disjoint l₂
        @[simp]
        theorem List.disjoint_reverse_left {α : Type u} {l₁ : List α} {l₂ : List α} :
        l₁.reverse.Disjoint l₂ l₁.Disjoint l₂
        @[simp]
        theorem List.disjoint_reverse_right {α : Type u} {l₁ : List α} {l₂ : List α} :
        l₁.Disjoint l₂.reverse l₁.Disjoint l₂
        theorem List.lookup_graph {α : Type u} {β : Type v} [BEq α] [LawfulBEq α] (f : αβ) {a : α} {as : List α} (h : a as) :
        List.lookup a (List.map (fun (x : α) => (x, f x)) as) = some (f a)