Documentation

Mathlib.Data.List.Basic

Basic properties of lists #

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

There is only one list of an empty type

Equations
  • List.uniqueOfIsEmpty = let src := instInhabitedList; { toInhabited := src, uniq := (_ : ∀ (l : List α), l = default) }
Equations
Equations
@[simp]
theorem List.cons_injective {α : Type u} {a : α} :
theorem List.singleton_injective {α : Type u} :
Function.Injective fun (a : α) => [a]
theorem List.singleton_inj {α : Type u} {a : α} {b : α} :
[a] = [b] a = b
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
theorem List.mem_split {α : Type u} {a : α} {l : List α} (h : a l) :
∃ (s : List α), ∃ (t : List α), l = s ++ a :: t
@[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
theorem List.map_bind {α : Type u} {β : Type v} {γ : Type w} (g : βList γ) (f : αβ) (l : List α) :
List.bind (List.map f l) g = List.bind l fun (a : α) => g (f a)

length #

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

Alias of the reverse direction of List.length_pos.

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

Alias of the forward direction of List.length_pos.

theorem List.length_pos_iff_ne_nil {α : Type u} {l : List α} :
0 < List.length l l []
theorem List.exists_of_length_succ {α : Type u} {n : } (l : List α) :
List.length l = 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 α} :
List.length l = 2 ∃ (a : α), ∃ (b : α), l = [a, b]
theorem List.length_eq_three {α : Type u} {l : List α} :
List.length l = 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] }
instance List.instInsertList {α : Type u} [DecidableEq α] :
Insert α (List α)
Equations
  • List.instInsertList = { insert := List.insert }
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.not_exists_mem_nil {α : Type u} (p : αProp) :
¬∃ (x : α), x [] p 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 #

Equations
@[deprecated List.subset_append_of_subset_right]
theorem List.subset_append_of_subset_right' {α : Type u} (l : List α) (l₁ : List α) (l₂ : List α) :
l l₂l l₁ ++ l₂
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.eq_nil_of_subset_nil {α : Type u_1} {l : List α} :
l []l = []

Alias of the forward direction of List.subset_nil.

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 α} :
List.append L₁ L₂ = L₁ ++ L₂
theorem List.append_eq_cons_iff {α : Type u} {a : List α} {b : List α} {c : List α} {x : α} :
a ++ b = x :: c a = [] b = x :: c ∃ (a' : List α), a = x :: a' c = a' ++ b
theorem List.cons_eq_append_iff {α : Type u} {a : List α} {b : List α} {c : List α} {x : α} :
x :: c = a ++ b a = [] b = x :: c ∃ (a' : List α), a = x :: a' c = a' ++ b
@[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 #

@[simp]
theorem List.replicate_zero {α : Type u} (a : α) :
theorem List.replicate_one {α : Type u} (a : α) :
theorem List.eq_replicate_length {α : Type u} {a : α} {l : List α} :
l = List.replicate (List.length l) 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
@[simp]
theorem List.map_replicate {α : Type u} {β : Type v} (f : αβ) (n : ) (a : α) :
@[simp]
theorem List.tail_replicate {α : Type u} (a : α) (n : ) :
@[simp]
theorem List.join_replicate_nil {α : Type u} (n : ) :
theorem List.replicate_right_inj {α : Type u} {a : α} {b : α} {n : } (hn : n 0) :
@[simp]
theorem List.replicate_right_inj' {α : Type u} {a : α} {b : α} {n : } :
@[simp]
theorem List.replicate_left_inj {α : Type u} {a : α} {n : } {m : } :

pure #

@[simp]
theorem List.mem_pure {α : Type u_2} (x : α) (y : α) :
x pure y x = y

bind #

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

concat #

@[deprecated List.concat_eq_append]
theorem List.concat_eq_append' {α : Type u} (a : α) (l : List α) :
List.concat l a = l ++ [a]
@[deprecated List.length_concat]
theorem List.length_concat' {α : Type u} (a : α) (l : List α) :

reverse #

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

empty #

theorem List.isEmpty_iff_eq_nil {α : Type u} {l : List α} :

dropLast #

getLast #

@[simp]
theorem List.getLast_cons {α : Type u} {a : α} {l : List α} (h : l []) :
List.getLast (a :: l) (_ : a :: l []) = List.getLast l h
theorem List.getLast_append_singleton {α : Type u} {a : α} (l : List α) :
List.getLast (l ++ [a]) (_ : l ++ [a] []) = a
theorem List.getLast_append' {α : Type u} (l₁ : List α) (l₂ : List α) (h : l₂ []) :
List.getLast (l₁ ++ l₂) (_ : l₁ ++ l₂ []) = List.getLast l₂ h
theorem List.getLast_concat' {α : Type u} {a : α} (l : List α) :
@[simp]
theorem List.getLast_singleton' {α : Type u} (a : α) :
List.getLast [a] (_ : [a] []) = a
theorem List.getLast_cons_cons {α : Type u} (a₁ : α) (a₂ : α) (l : List α) :
List.getLast (a₁ :: a₂ :: l) (_ : a₁ :: a₂ :: l []) = List.getLast (a₂ :: l) (_ : a₂ :: l [])
theorem List.dropLast_append_getLast {α : Type u} {l : List α} (h : l []) :
theorem List.getLast_congr {α : Type u} {l₁ : List α} {l₂ : List α} (h₁ : l₁ []) (h₂ : l₂ []) (h₃ : l₁ = l₂) :
List.getLast l₁ h₁ = List.getLast l₂ h₂
theorem List.getLast_replicate_succ {α : Type u} (m : ) (a : α) :
List.getLast (List.replicate (m + 1) a) (_ : List.replicate (m + 1) a []) = a

getLast? #

@[simp]
theorem List.getLast?_cons_cons {α : Type u} (a : α) (b : α) (l : List α) :
@[simp]
theorem List.getLast?_isNone {α : Type u} {l : List α} :
@[simp]
theorem List.getLast?_isSome {α : Type u} {l : List α} :
theorem List.mem_getLast?_eq_getLast {α : Type u} {l : List α} {x : α} :
x List.getLast? l∃ (h : l []), x = List.getLast l h
theorem List.mem_getLast?_cons {α : Type u} {x : α} {y : α} {l : List α} :
theorem List.mem_of_mem_getLast? {α : Type u} {l : List α} {a : α} (ha : a List.getLast? l) :
a l
theorem List.dropLast_append_getLast? {α : Type u} {l : List α} (a : α) :
@[simp]
theorem List.getLast?_append_cons {α : Type u} (l₁ : List α) (a : α) (l₂ : List α) :
List.getLast? (l₁ ++ a :: l₂) = List.getLast? (a :: l₂)
theorem List.getLast?_append_of_ne_nil {α : Type u} (l₁ : List α) {l₂ : List α} :
l₂ []List.getLast? (l₁ ++ l₂) = List.getLast? l₂
theorem List.getLast?_append {α : Type u} {l₁ : List α} {l₂ : List α} {x : α} (h : x List.getLast? l₂) :
x List.getLast? (l₁ ++ l₂)

head(!?) and tail #

theorem List.eq_cons_of_mem_head? {α : Type u} {x : α} {l : List α} :
x List.head? ll = x :: List.tail l
theorem List.mem_of_mem_head? {α : Type u} {x : α} {l : List α} (h : x List.head? l) :
x l
@[simp]
theorem List.head!_cons {α : Type u} [Inhabited α] (a : α) (l : List α) :
List.head! (a :: l) = a
@[simp]
theorem List.head!_append {α : Type u} [Inhabited α] (t : List α) {s : List α} (h : s []) :
theorem List.head?_append {α : Type u} {s : List α} {t : List α} {x : α} (h : x List.head? s) :
x List.head? (s ++ t)
theorem List.head?_append_of_ne_nil {α : Type u} (l₁ : List α) {l₂ : List α} :
l₁ []List.head? (l₁ ++ l₂) = List.head? l₁
theorem List.tail_append_singleton_of_ne_nil {α : Type u} {a : α} {l : List α} (h : l []) :
List.tail (l ++ [a]) = List.tail l ++ [a]
theorem List.cons_head?_tail {α : Type u} {l : List α} {a : α} :
a List.head? la :: List.tail l = l
theorem List.head!_mem_head? {α : Type u} [Inhabited α] {l : List α} :
theorem List.cons_head!_tail {α : Type u} [Inhabited α] {l : List α} (h : l []) :
theorem List.head!_mem_self {α : Type u} [Inhabited α] {l : List α} (h : l []) :
theorem List.head_mem {α : Type u} {l : List α} (h : l []) :
@[simp]
theorem List.head?_map {α : Type u} {β : Type v} (f : αβ) (l : List α) :
theorem List.tail_append_of_ne_nil {α : Type u} (l : List α) (l' : List α) (h : l []) :
List.tail (l ++ l') = List.tail l ++ l'
@[simp]
theorem List.nthLe_tail {α : Type u} (l : List α) (i : ) (h : i < List.length (List.tail l)) (h' : optParam (i + 1 < List.length l) (_ : i + 1 < List.length l)) :
List.nthLe (List.tail l) i h = List.nthLe l (i + 1) h'
theorem List.nthLe_cons_aux {α : Type u} {l : List α} {a : α} {n : } (hn : n 0) (h : n < List.length (a :: l)) :
theorem List.nthLe_cons {α : Type u} {l : List α} {a : α} {n : } (hl : n < List.length (a :: l)) :
List.nthLe (a :: l) n hl = if hn : n = 0 then a else List.nthLe l (n - 1) (_ : n - 1 < List.length l)
@[simp]
theorem List.modifyHead_modifyHead {α : Type u} (l : List α) (f : αα) (g : αα) :

Induction from the right #

def List.reverseRecOn {α : Type u} {C : List αSort u_2} (l : List α) (H0 : C []) (H1 : (l : List α) → (a : α) → C lC (l ++ [a])) :
C 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
    def List.bidirectionalRec {α : Type u} {C : List αSort u_2} (H0 : C []) (H1 : (a : α) → C [a]) (Hn : (a : α) → (l : List α) → (b : α) → C lC (a :: (l ++ [b]))) (l : List α) :
    C 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
      def 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 : List.Sublist l₁ l₂) :
        List.Sublist (a :: l₁) (a :: l₂)
        theorem List.sublist_cons_of_sublist {α : Type u} (a : α) {l₁ : List α} {l₂ : List α} :
        List.Sublist l₁ l₂List.Sublist l₁ (a :: l₂)
        theorem List.sublist_of_cons_sublist_cons {α : Type u} {l₁ : List α} {l₂ : List α} {a : α} :
        List.Sublist (a :: l₁) (a :: l₂)List.Sublist l₁ l₂
        theorem List.cons_sublist_cons_iff {α : Type u} {l₁ : List α} {l₂ : List α} {a : α} :
        List.Sublist (a :: l₁) (a :: l₂) List.Sublist l₁ l₂
        theorem List.eq_nil_of_sublist_nil {α : Type u} {l : List α} (s : List.Sublist l []) :
        l = []
        theorem List.sublist_nil_iff_eq_nil {α : Type u_1} {l : List α} :
        List.Sublist l [] l = []

        Alias of List.sublist_nil.

        @[simp]
        theorem List.sublist_singleton {α : Type u} {l : List α} {a : α} :
        List.Sublist l [a] l = [] l = [a]
        theorem List.sublist_replicate_iff {α : Type u} {l : List α} {a : α} {n : } :
        List.Sublist l (List.replicate n a) ∃ (k : ), k n l = List.replicate k a
        theorem List.Sublist.antisymm {α : Type u} {l₁ : List α} {l₂ : List α} (s₁ : List.Sublist l₁ l₂) (s₂ : List.Sublist l₂ l₁) :
        l₁ = l₂
        instance List.decidableSublist {α : Type u} [DecidableEq α] (l₁ : List α) (l₂ : List α) :
        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) = Nat.succ (List.indexOf a l)
        theorem List.indexOf_eq_length {α : Type u} [DecidableEq α] {a : α} {l : List α} :
        @[simp]
        theorem List.indexOf_of_not_mem {α : Type u} [DecidableEq α] {l : List α} {a : α} :
        theorem List.indexOf_le_length {α : Type u} [DecidableEq α] {a : α} {l : List α} :
        theorem List.indexOf_lt_length {α : Type u} [DecidableEq α] {a : α} {l : List α} :
        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₂) = List.length l₁ + List.indexOf a l₂

        nth element #

        @[deprecated List.get_of_mem]
        theorem List.nthLe_of_mem {α : Type u} {a : α} {l : List α} (h : a l) :
        ∃ (n : ), ∃ (h : n < List.length l), List.nthLe l n h = a
        @[deprecated List.get?_eq_get]
        theorem List.nthLe_get? {α : Type u} {l : List α} {n : } (h : n < List.length l) :
        @[simp]
        theorem List.get?_length {α : Type u} (l : List α) :
        @[deprecated List.get?_eq_some]
        theorem List.get?_eq_some' {α : Type u} {l : List α} {n : } {a : α} :
        List.get? l n = some a ∃ (h : n < List.length l), List.nthLe l n h = a
        @[deprecated List.get_mem]
        theorem List.nthLe_mem {α : Type u} (l : List α) (n : ) (h : n < List.length l) :
        List.nthLe l n h l
        @[deprecated List.mem_iff_get]
        theorem List.mem_iff_nthLe {α : Type u} {a : α} {l : List α} :
        a l ∃ (n : ), ∃ (h : n < List.length l), List.nthLe l n h = a
        theorem List.get?_injective {α : Type u} {xs : List α} {i : } {j : } (h₀ : i < List.length xs) (h₁ : List.Nodup xs) (h₂ : List.get? xs i = List.get? xs j) :
        i = j
        @[deprecated List.get_map]
        theorem List.nthLe_map {α : Type u} {β : Type v} (f : αβ) {l : List α} {n : } (H1 : n < List.length (List.map f l)) (H2 : n < List.length l) :
        List.nthLe (List.map f l) n H1 = f (List.nthLe l n H2)
        theorem List.get_map_rev {α : Type u} {β : Type v} (f : αβ) {l : List α} {n : Fin (List.length l)} :
        f (List.get l n) = List.get (List.map f l) { val := n, isLt := (_ : n < List.length (List.map f l)) }

        A version of get_map that can be used for rewriting.

        @[deprecated List.get_map_rev]
        theorem List.nthLe_map_rev {α : Type u} {β : Type v} (f : αβ) {l : List α} {n : } (H : n < List.length l) :
        f (List.nthLe l n H) = List.nthLe (List.map f l) n (_ : n < List.length (List.map f l))

        A version of nthLe_map that can be used for rewriting.

        @[simp, deprecated List.get_map]
        theorem List.nthLe_map' {α : Type u} {β : Type v} (f : αβ) {l : List α} {n : } (H : n < List.length (List.map f l)) :
        List.nthLe (List.map f l) n H = f (List.nthLe l n (_ : n < List.length l))
        @[deprecated List.get_of_eq]
        theorem List.nthLe_of_eq {α : Type u} {L : List α} {L' : List α} (h : L = L') {i : } (hi : i < List.length L) :
        List.nthLe L i hi = List.nthLe L' i (_ : i < List.length L')

        If one has nthLe L i hi in a formula and h : L = L', one can not rw h in the formula as hi gives i < L.length and not i < L'.length. The lemma nth_le_of_eq can be used to make such a rewrite, with rw (nth_le_of_eq h).

        @[simp, deprecated List.get_singleton]
        theorem List.nthLe_singleton {α : Type u} (a : α) {n : } (hn : n < 1) :
        List.nthLe [a] n hn = a
        @[deprecated]
        theorem List.nthLe_zero {α : Type u} [Inhabited α] {L : List α} (h : 0 < List.length L) :
        @[deprecated List.get_append]
        theorem List.nthLe_append {α : Type u} {l₁ : List α} {l₂ : List α} {n : } (hn₁ : n < List.length (l₁ ++ l₂)) (hn₂ : n < List.length l₁) :
        List.nthLe (l₁ ++ l₂) n hn₁ = List.nthLe l₁ n hn₂
        @[deprecated List.get_append_right']
        theorem List.nthLe_append_right {α : Type u} {l₁ : List α} {l₂ : List α} {n : } (h₁ : List.length l₁ n) (h₂ : n < List.length (l₁ ++ l₂)) :
        List.nthLe (l₁ ++ l₂) n h₂ = List.nthLe l₂ (n - List.length l₁) (_ : n - List.length l₁ < List.length l₂)
        @[deprecated List.get_replicate]
        theorem List.nthLe_replicate {α : Type u} (a : α) {n : } {m : } (h : m < List.length (List.replicate n a)) :
        @[deprecated List.getLast_eq_get]
        theorem List.getLast_eq_nthLe {α : Type u} (l : List α) (h : l []) :
        theorem List.get_length_sub_one {α : Type u} {l : List α} (h : List.length l - 1 < List.length l) :
        List.get l { val := List.length l - 1, isLt := h } = List.getLast l (_ : l = []False)
        @[deprecated List.get_length_sub_one]
        theorem List.nthLe_length_sub_one {α : Type u} {l : List α} (h : List.length l - 1 < List.length l) :
        List.nthLe l (List.length l - 1) h = List.getLast l (_ : l = []False)
        @[deprecated List.get_cons_length]
        theorem List.nthLe_cons_length {α : Type u} (x : α) (xs : List α) (n : ) (h : n = List.length xs) :
        List.nthLe (x :: xs) n (_ : n < Nat.succ (List.length xs)) = List.getLast (x :: xs) (_ : x :: xs [])
        theorem List.take_one_drop_eq_of_lt_length {α : Type u} {l : List α} {n : } (h : n < List.length l) :
        List.take 1 (List.drop n l) = [List.get l { val := n, isLt := h }]
        @[deprecated List.take_one_drop_eq_of_lt_length]
        theorem List.take_one_drop_eq_of_lt_length' {α : Type u} {l : List α} {n : } (h : n < List.length l) :
        @[deprecated List.ext_get]
        theorem List.ext_nthLe {α : Type u} {l₁ : List α} {l₂ : List α} (hl : List.length l₁ = List.length l₂) (h : ∀ (n : ) (h₁ : n < List.length l₁) (h₂ : n < List.length l₂), List.nthLe l₁ n h₁ = List.nthLe l₂ n h₂) :
        l₁ = l₂
        @[simp]
        theorem List.indexOf_get {α : Type u} [DecidableEq α] {a : α} {l : List α} (h : List.indexOf a l < List.length l) :
        List.get l { val := List.indexOf a l, isLt := h } = a
        @[simp, deprecated List.indexOf_get]
        theorem List.indexOf_nthLe {α : Type u} [DecidableEq α] {a : α} {l : List α} (h : List.indexOf a l < List.length l) :
        @[simp]
        theorem List.indexOf_get? {α : Type u} [DecidableEq α] {a : α} {l : List α} (h : a l) :
        @[deprecated]
        theorem List.get_reverse_aux₁ {α : Type u} (l : List α) (r : List α) (i : ) (h1 : i + List.length l < List.length (List.reverseAux l r)) (h2 : i < List.length r) :
        List.get (List.reverseAux l r) { val := i + List.length l, isLt := h1 } = List.get r { val := i, isLt := h2 }
        theorem List.indexOf_inj {α : Type u} [DecidableEq α] {l : List α} {x : α} {y : α} (hx : x l) (hy : y l) :
        theorem List.get_reverse_aux₂ {α : Type u} (l : List α) (r : List α) (i : ) (h1 : List.length l - 1 - i < List.length (List.reverseAux l r)) (h2 : i < List.length l) :
        List.get (List.reverseAux l r) { val := List.length l - 1 - i, isLt := h1 } = List.get l { val := i, isLt := h2 }
        @[simp]
        theorem List.get_reverse {α : Type u} (l : List α) (i : ) (h1 : List.length l - 1 - i < List.length (List.reverse l)) (h2 : i < List.length l) :
        List.get (List.reverse l) { val := List.length l - 1 - i, isLt := h1 } = List.get l { val := i, isLt := h2 }
        @[simp, deprecated List.get_reverse]
        theorem List.nthLe_reverse {α : Type u} (l : List α) (i : ) (h1 : List.length l - 1 - i < List.length (List.reverse l)) (h2 : i < List.length l) :
        @[deprecated List.get_reverse']
        theorem List.nthLe_reverse' {α : Type u} (l : List α) (n : ) (hn : n < List.length (List.reverse l)) (hn' : List.length l - 1 - n < List.length l) :
        theorem List.get_reverse' {α : Type u} (l : List α) (n : Fin (List.length (List.reverse l))) (hn' : List.length l - 1 - n < List.length l) :
        List.get (List.reverse l) n = List.get l { val := List.length l - 1 - n, isLt := hn' }
        theorem List.eq_cons_of_length_one {α : Type u} {l : List α} (h : List.length l = 1) :
        l = [List.nthLe l 0 (_ : 0 < List.length l)]
        theorem List.get_eq_iff {α : Type u} {l : List α} {n : Fin (List.length l)} {x : α} :
        List.get l n = x List.get? l n = some x
        @[deprecated List.get_eq_iff]
        theorem List.nthLe_eq_iff {α : Type u} {l : List α} {n : } {x : α} {h : n < List.length l} :
        List.nthLe l n h = x List.get? l n = some x
        @[deprecated List.get?_eq_get]
        theorem List.some_nthLe_eq {α : Type u} {l : List α} {n : } {h : n < List.length l} :
        theorem List.modifyNthTail_modifyNthTail {α : Type u} {f : List αList α} {g : List αList α} (m : ) (n : ) (l : List α) :
        List.modifyNthTail g (m + n) (List.modifyNthTail f n l) = List.modifyNthTail (fun (l : List α) => List.modifyNthTail g m (f l)) n l
        theorem List.modifyNthTail_modifyNthTail_le {α : Type u} {f : List αList α} {g : List αList α} (m : ) (n : ) (l : List α) (h : n m) :
        List.modifyNthTail g m (List.modifyNthTail f n l) = List.modifyNthTail (fun (l : List α) => List.modifyNthTail g (m - n) (f l)) n l
        theorem List.modifyNthTail_modifyNthTail_same {α : Type u} {f : List αList α} {g : List αList α} (n : ) (l : List α) :
        theorem List.removeNth_eq_nthTail {α : Type u} (n : ) (l : List α) :
        theorem List.modifyNth_eq_set {α : Type u} (f : αα) (n : ) (l : List α) :
        List.modifyNth f n l = Option.getD ((fun (a : α) => List.set l n (f a)) <$> List.get? l n) l
        theorem List.length_modifyNthTail {α : Type u} (f : List αList α) (H : ∀ (l : List α), List.length (f l) = List.length l) (n : ) (l : List α) :
        theorem List.length_modifyNth {α : Type u} (f : αα) (n : ) (l : List α) :
        @[simp, deprecated List.get_set_eq]
        theorem List.nthLe_set_eq {α : Type u} (l : List α) (i : ) (a : α) (h : i < List.length (List.set l i a)) :
        List.nthLe (List.set l i a) i h = a
        @[simp]
        theorem List.get_set_of_ne {α : Type u} {l : List α} {i : } {j : } (h : i j) (a : α) (hj : j < List.length (List.set l i a)) :
        List.get (List.set l i a) { val := j, isLt := hj } = List.get l { val := j, isLt := (_ : j < List.length l) }
        @[simp, deprecated List.get_set_of_ne]
        theorem List.nthLe_set_of_ne {α : Type u} {l : List α} {i : } {j : } (h : i j) (a : α) (hj : j < List.length (List.set l i a)) :
        List.nthLe (List.set l i a) j hj = List.nthLe l j (_ : j < List.length l)
        @[simp]
        theorem List.insertNth_zero {α : Type u} (s : List α) (x : α) :
        List.insertNth 0 x s = x :: s
        @[simp]
        theorem List.insertNth_succ_nil {α : Type u} (n : ) (a : α) :
        List.insertNth (n + 1) a [] = []
        @[simp]
        theorem List.insertNth_succ_cons {α : Type u} (s : List α) (hd : α) (x : α) (n : ) :
        List.insertNth (n + 1) x (hd :: s) = hd :: List.insertNth n x s
        theorem List.length_insertNth {α : Type u} {a : α} (n : ) (as : List α) :
        theorem List.removeNth_insertNth {α : Type u} {a : α} (n : ) (l : List α) :
        theorem List.insertNth_removeNth_of_ge {α : Type u} {a : α} (n : ) (m : ) (as : List α) :
        n < List.length asn mList.insertNth m a (List.removeNth as n) = List.removeNth (List.insertNth (m + 1) a as) n
        theorem List.insertNth_removeNth_of_le {α : Type u} {a : α} (n : ) (m : ) (as : List α) :
        n < List.length asm nList.insertNth m a (List.removeNth as n) = List.removeNth (List.insertNth m a as) (n + 1)
        theorem List.insertNth_comm {α : Type u} (a : α) (b : α) (i : ) (j : ) (l : List α) :
        i jj List.length lList.insertNth (j + 1) b (List.insertNth i a l) = List.insertNth i a (List.insertNth j b l)
        theorem List.mem_insertNth {α : Type u} {a : α} {b : α} {n : } {l : List α} :
        n List.length l(a List.insertNth n b l a = b a l)
        theorem List.insertNth_of_length_lt {α : Type u} (l : List α) (x : α) (n : ) (h : List.length l < n) :
        @[simp]
        theorem List.insertNth_length_self {α : Type u} (l : List α) (x : α) :
        theorem List.length_le_length_insertNth {α : Type u} (l : List α) (x : α) (n : ) :
        theorem List.length_insertNth_le_succ {α : Type u} (l : List α) (x : α) (n : ) :
        theorem List.get_insertNth_of_lt {α : Type u} (l : List α) (x : α) (n : ) (k : ) (hn : k < n) (hk : k < List.length l) (hk' : optParam (k < List.length (List.insertNth n x l)) (_ : k < List.length (List.insertNth n x l))) :
        List.get (List.insertNth n x l) { val := k, isLt := hk' } = List.get l { val := k, isLt := hk }
        @[deprecated List.get_insertNth_of_lt]
        theorem List.nthLe_insertNth_of_lt {α : Type u} (l : List α) (x : α) (n : ) (k : ) :
        k < n∀ (hk : k < List.length l) (hk' : optParam (k < List.length (List.insertNth n x l)) (_ : k < List.length (List.insertNth n x l))), List.nthLe (List.insertNth n x l) k hk' = List.nthLe l k hk
        @[simp]
        theorem List.get_insertNth_self {α : Type u} (l : List α) (x : α) (n : ) (hn : n List.length l) (hn' : optParam (n < List.length (List.insertNth n x l)) (_ : n < List.length (List.insertNth n x l))) :
        List.get (List.insertNth n x l) { val := n, isLt := hn' } = x
        @[simp, deprecated List.get_insertNth_self]
        theorem List.nthLe_insertNth_self {α : Type u} (l : List α) (x : α) (n : ) (hn : n List.length l) (hn' : optParam (n < List.length (List.insertNth n x l)) (_ : n < List.length (List.insertNth n x l))) :
        List.nthLe (List.insertNth n x l) n hn' = x
        theorem List.get_insertNth_add_succ {α : Type u} (l : List α) (x : α) (n : ) (k : ) (hk' : n + k < List.length l) (hk : optParam (n + k + 1 < List.length (List.insertNth n x l)) (_ : n + k + 1 < List.length (List.insertNth n x l))) :
        List.get (List.insertNth n x l) { val := n + k + 1, isLt := hk } = List.get l { val := n + k, isLt := hk' }
        @[deprecated List.get_insertNth_add_succ]
        theorem List.nthLe_insertNth_add_succ {α : Type u} (l : List α) (x : α) (n : ) (k : ) (hk' : n + k < List.length l) (hk : optParam (n + k + 1 < List.length (List.insertNth n x l)) (_ : n + k + 1 < List.length (List.insertNth n x l))) :
        List.nthLe (List.insertNth n x l) (n + k + 1) hk = List.nthLe l (n + k) hk'

        map #

        theorem List.map_eq_foldr {α : Type u} {β : Type v} (f : αβ) (l : List α) :
        List.map f l = List.foldr (fun (a : α) (bs : List β) => f a :: bs) [] l
        theorem List.map_congr {α : Type u} {β : Type v} {f : αβ} {g : αβ} {l : List α} :
        (∀ (x : α), x lf x = g x)List.map f l = List.map g l
        theorem List.map_eq_map_iff {α : Type u} {β : Type v} {f : αβ} {g : αβ} {l : List α} :
        List.map f l = List.map g l ∀ (x : α), x lf x = g x
        theorem List.map_concat {α : Type u} {β : Type v} (f : αβ) (a : α) (l : List α) :
        theorem List.map_id'' {α : Type u} {f : αα} (h : ∀ (x : α), f x = x) (l : List α) :
        List.map f l = l
        theorem List.eq_nil_of_map_eq_nil {α : Type u} {β : Type v} {f : αβ} {l : List α} (h : List.map f l = []) :
        l = []
        @[simp]
        theorem List.map_join {α : Type u} {β : Type v} (f : αβ) (L : List (List α)) :
        theorem List.bind_ret_eq_map {α : Type u} {β : Type v} (f : αβ) (l : List α) :
        List.bind l (List.ret f) = List.map f l
        theorem List.bind_congr {α : Type u} {β : Type v} {l : List α} {f : αList β} {g : αList β} (h : ∀ (x : α), x lf x = g x) :
        @[simp]
        theorem List.map_eq_map {α : Type u_2} {β : Type u_2} (f : αβ) (l : List α) :
        f <$> l = List.map f l
        @[simp]
        theorem List.map_tail {α : Type u} {β : Type v} (f : αβ) (l : List α) :
        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.map_filter_eq_foldr {α : Type u} {β : Type v} (f : αβ) (p : αBool) (as : List α) :
        List.map f (List.filter p as) = List.foldr (fun (a : α) (bs : List β) => bif p a then f a :: bs else bs) [] as
        theorem List.getLast_map {α : Type u} {β : Type v} (f : αβ) {l : List α} (hl : l []) :
        List.getLast (List.map f l) (_ : ¬List.map f l = []) = f (List.getLast l hl)
        theorem List.map_eq_replicate_iff {α : Type u} {β : Type v} {l : List α} {f : αβ} {b : β} :
        List.map f l = List.replicate (List.length l) b ∀ (x : α), x lf x = b
        @[simp]
        theorem List.map_const {α : Type u} {β : Type v} (l : List α) (b : β) :
        @[simp]
        theorem List.map_const' {α : Type u} {β : Type v} (l : List α) (b : β) :
        List.map (fun (x : α) => b) l = List.replicate (List.length l) b
        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 #

        theorem List.take_cons {α : Type u} (n : ) (a : α) (l : List α) :
        List.take (Nat.succ n) (a :: l) = a :: List.take n l
        theorem List.take_all_of_le {α : Type u} {n : } {l : List α} :
        List.length l nList.take n l = l
        @[simp]
        theorem List.take_left {α : Type u} (l₁ : List α) (l₂ : List α) :
        List.take (List.length l₁) (l₁ ++ l₂) = l₁
        theorem List.take_left' {α : Type u} {l₁ : List α} {l₂ : List α} {n : } (h : List.length l₁ = n) :
        List.take n (l₁ ++ l₂) = l₁
        theorem List.take_take {α : Type u} (n : ) (m : ) (l : List α) :
        theorem List.take_replicate {α : Type u} (a : α) (n : ) (m : ) :
        theorem List.map_take {α : Type u_2} {β : Type u_3} (f : αβ) (L : List α) (i : ) :
        theorem List.take_append_eq_append_take {α : Type u} {l₁ : List α} {l₂ : List α} {n : } :
        List.take n (l₁ ++ l₂) = List.take n l₁ ++ List.take (n - List.length l₁) l₂

        Taking the first n elements in l₁ ++ l₂ is the same as appending the first n elements of l₁ to the first n - l₁.length elements of l₂.

        theorem List.take_append_of_le_length {α : Type u} {l₁ : List α} {l₂ : List α} {n : } (h : n List.length l₁) :
        List.take n (l₁ ++ l₂) = List.take n l₁
        theorem List.take_append {α : Type u} {l₁ : List α} {l₂ : List α} (i : ) :
        List.take (List.length l₁ + i) (l₁ ++ l₂) = l₁ ++ List.take i l₂

        Taking the first l₁.length + i elements in l₁ ++ l₂ is the same as appending the first i elements of l₂ to l₁.

        theorem List.get_take {α : Type u} (L : List α) {i : } {j : } (hi : i < List.length L) (hj : i < j) :
        List.get L { val := i, isLt := hi } = List.get (List.take j L) { val := i, isLt := (_ : i < List.length (List.take j L)) }

        The i-th element of a list coincides with the i-th element of any of its prefixes of length > i. Version designed to rewrite from the big list to the small list.

        @[deprecated List.get_take]
        theorem List.nthLe_take {α : Type u} (L : List α) {i : } {j : } (hi : i < List.length L) (hj : i < j) :
        List.nthLe L i hi = List.nthLe (List.take j L) i (_ : i < List.length (List.take j L))

        The i-th element of a list coincides with the i-th element of any of its prefixes of length > i. Version designed to rewrite from the big list to the small list.

        theorem List.get_take' {α : Type u} (L : List α) {j : } {i : Fin (List.length (List.take j L))} :
        List.get (List.take j L) i = List.get L { val := i, isLt := (_ : i < List.length L) }

        The i-th element of a list coincides with the i-th element of any of its prefixes of length > i. Version designed to rewrite from the small list to the big list.

        @[deprecated List.get_take']
        theorem List.nthLe_take' {α : Type u} (L : List α) {i : } {j : } (hi : i < List.length (List.take j L)) :
        List.nthLe (List.take j L) i hi = List.nthLe L i (_ : i < List.length L)

        The i-th element of a list coincides with the i-th element of any of its prefixes of length > i. Version designed to rewrite from the small list to the big list.

        theorem List.get?_take {α : Type u} {l : List α} {n : } {m : } (h : m < n) :
        @[simp]
        theorem List.nth_take_of_succ {α : Type u} {l : List α} {n : } :
        List.get? (List.take (n + 1) l) n = List.get? l n
        theorem List.take_succ {α : Type u} {l : List α} {n : } :
        @[simp]
        theorem List.take_eq_nil_iff {α : Type u} {l : List α} {k : } :
        List.take k l = [] l = [] k = 0
        theorem List.take_eq_take {α : Type u} {l : List α} {m : } {n : } :
        theorem List.take_add {α : Type u} (l : List α) (m : ) (n : ) :
        theorem List.dropLast_take {α : Type u} {n : } {l : List α} (h : n < List.length l) :
        theorem List.dropLast_cons_of_ne_nil {α : Type u_2} {x : α} {l : List α} (h : l []) :
        @[simp]
        theorem List.dropLast_append_of_ne_nil {α : Type u_2} {l : List α} (l' : List α) :
        l []List.dropLast (l' ++ l) = l' ++ List.dropLast l
        theorem List.drop_eq_nil_iff_le {α : Type u} {l : List α} {k : } :
        @[simp]
        theorem List.tail_drop {α : Type u} (l : List α) (n : ) :
        @[simp]
        theorem List.drop_tail {α : Type u} (l : List α) (n : ) :
        theorem List.cons_get_drop_succ {α : Type u} {l : List α} {n : Fin (List.length l)} :
        List.get l n :: List.drop (n + 1) l = List.drop (n) l
        @[deprecated List.cons_get_drop_succ]
        theorem List.cons_nthLe_drop_succ {α : Type u} {l : List α} {n : } (hn : n < List.length l) :
        List.nthLe l n hn :: List.drop (n + 1) l = List.drop n l
        theorem List.drop_length_cons {α : Type u} {l : List α} (h : l []) (a : α) :
        theorem List.drop_append {α : Type u} {l₁ : List α} {l₂ : List α} (i : ) :
        List.drop (List.length l₁ + i) (l₁ ++ l₂) = List.drop i l₂

        Dropping the elements up to l₁.length + i in l₁ + l₂ is the same as dropping the elements up to i in l₂.

        theorem List.drop_sizeOf_le {α : Type u} [SizeOf α] (l : List α) (n : ) :
        theorem List.get_drop {α : Type u} (L : List α) {i : } {j : } (h : i + j < List.length L) :
        List.get L { val := i + j, isLt := h } = List.get (List.drop i L) { val := j, isLt := (_ : j < List.length (List.drop i L)) }

        The i + j-th element of a list coincides with the j-th element of the list obtained by dropping the first i elements. Version designed to rewrite from the big list to the small list.

        @[deprecated List.get_drop]
        theorem List.nthLe_drop {α : Type u} (L : List α) {i : } {j : } (h : i + j < List.length L) :
        List.nthLe L (i + j) h = List.nthLe (List.drop i L) j (_ : j < List.length (List.drop i L))

        The i + j-th element of a list coincides with the j-th element of the list obtained by dropping the first i elements. Version designed to rewrite from the big list to the small list.

        theorem List.get_drop' {α : Type u} (L : List α) {i : } {j : Fin (List.length (List.drop i L))} :
        List.get (List.drop i L) j = List.get L { val := i + j, isLt := (_ : i + j < List.length L) }

        The i + j-th element of a list coincides with the j-th element of the list obtained by dropping the first i elements. Version designed to rewrite from the small list to the big list.

        @[deprecated List.get_drop']
        theorem List.nthLe_drop' {α : Type u} (L : List α) {i : } {j : } (h : j < List.length (List.drop i L)) :
        List.nthLe (List.drop i L) j h = List.nthLe L (i + j) (_ : i + j < List.length L)

        The i + j-th element of a list coincides with the j-th element of the list obtained by dropping the first i elements. Version designed to rewrite from the small list to the big list.

        theorem List.get?_drop {α : Type u} (L : List α) (i : ) (j : ) :
        List.get? (List.drop i L) j = List.get? L (i + j)
        @[simp]
        theorem List.drop_drop {α : Type u} (n : ) (m : ) (l : List α) :
        List.drop n (List.drop m l) = List.drop (n + m) l
        theorem List.drop_take {α : Type u} (m : ) (n : ) (l : List α) :
        theorem List.map_drop {α : Type u_2} {β : Type u_3} (f : αβ) (L : List α) (i : ) :
        theorem List.modifyNthTail_eq_take_drop {α : Type u} (f : List αList α) (H : f [] = []) (n : ) (l : List α) :
        @[simp]
        theorem List.modifyNth_nil {α : Type u} (f : αα) (n : ) :
        List.modifyNth f n [] = []
        @[simp]
        theorem List.modifyNth_zero_cons {α : Type u} (f : αα) (a : α) (l : List α) :
        List.modifyNth f 0 (a :: l) = f a :: l
        @[simp]
        theorem List.modifyNth_succ_cons {α : Type u} (f : αα) (n : ) (a : α) (l : List α) :
        List.modifyNth f (n + 1) (a :: l) = a :: List.modifyNth f n l
        theorem List.modifyNth_eq_take_drop {α : Type u} (f : αα) (n : ) (l : List α) :
        theorem List.modifyNth_eq_take_cons_drop {α : Type u} (f : αα) {n : } {l : List α} (h : n < List.length l) :
        List.modifyNth f n l = List.take n l ++ f (List.get l { val := n, isLt := h }) :: List.drop (n + 1) l
        theorem List.set_eq_take_cons_drop {α : Type u} (a : α) {n : } {l : List α} (h : n < List.length l) :
        List.set l n a = List.take n l ++ a :: List.drop (n + 1) l
        theorem List.reverse_take {α : Type u_2} {xs : List α} (n : ) (h : n List.length xs) :
        @[simp]
        theorem List.set_eq_nil {α : Type u} (l : List α) (n : ) (a : α) :
        List.set l n a = [] l = []
        @[simp]
        theorem List.takeI_length {α : Type u} [Inhabited α] (n : ) (l : List α) :
        @[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 α} :
        @[simp]
        theorem List.takeI_left {α : Type u} [Inhabited α] (l₁ : List α) (l₂ : List α) :
        List.takeI (List.length l₁) (l₁ ++ l₂) = l₁
        theorem List.takeI_left' {α : Type u} [Inhabited α] {l₁ : List α} {l₂ : List α} {n : } (h : List.length l₁ = n) :
        List.takeI n (l₁ ++ l₂) = l₁
        @[simp]
        theorem List.takeD_length {α : Type u} (n : ) (l : List α) (a : α) :
        theorem List.takeD_eq_take {α : Type u} {n : } {l : List α} (a : α) :
        @[simp]
        theorem List.takeD_left {α : Type u} (l₁ : List α) (l₂ : List α) (a : α) :
        List.takeD (List.length l₁) (l₁ ++ l₂) a = l₁
        theorem List.takeD_left' {α : Type u} {l₁ : List α} {l₂ : List α} {n : } {a : α} (h : List.length l₁ = 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
        @[simp]
        theorem List.foldl_join {α : Type u} {β : Type v} (f : αβα) (a : α) (L : List (List β)) :
        @[simp]
        theorem List.foldr_join {α : Type u} {β : Type v} (f : αββ) (b : β) (L : List (List α)) :
        List.foldr f b (List.join L) = List.foldr (fun (l : List α) (b : β) => List.foldr f b l) b L
        theorem List.foldr_eta {α : Type u} (l : List α) :
        List.foldr List.cons [] l = l
        @[simp]
        theorem List.reverse_foldl {α : Type u} {l : List α} :
        List.reverse (List.foldl (fun (t : List α) (h : α) => h :: t) [] l) = l
        theorem List.foldl_map' {α : Type u} {β : Type u} (g : αβ) (f : ααα) (f' : βββ) (a : α) (l : List α) (h : ∀ (x y : α), f' (g x) (g y) = g (f x y)) :
        List.foldl f' (g a) (List.map g l) = g (List.foldl f a l)
        theorem List.foldr_map' {α : Type u} {β : Type u} (g : αβ) (f : ααα) (f' : βββ) (a : α) (l : List α) (h : ∀ (x y : α), f' (g x) (g y) = g (f x y)) :
        List.foldr f' (g a) (List.map g l) = g (List.foldr f a 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_2} {l : List (αα)} {f : αα} (hl : ∀ (f : αα), f lFunction.Injective f) (hf : Function.Injective f) :
        Function.Injective (List.foldl Function.comp f l)
        def List.foldrRecOn {α : Type u} {β : Type v} {C : βSort u_2} (l : List α) (op : αββ) (b : β) (hb : C b) (hl : (b : β) → C b(a : α) → a lC (op a b)) :
        C (List.foldr op b l)

        Induction principle for values produced by a foldr: if a property holds for the seed element b : β and for all incremental op : α → β → β performed on the elements (a : α) ∈ l. 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
          def List.foldlRecOn {α : Type u} {β : Type v} {C : βSort u_2} (l : List α) (op : βαβ) (b : β) (hb : C b) (hl : (b : β) → C b(a : α) → a lC (op b a)) :
          C (List.foldl op b l)

          Induction principle for values produced by a foldl: if a property holds for the seed element b : β and for all incremental op : β → α → β performed on the elements (a : α) ∈ l. 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.foldrRecOn_nil {α : Type u} {β : Type v} {C : βSort u_2} (op : αββ) (b : β) (hb : C b) (hl : (b : β) → C b(a : α) → a []C (op a b)) :
            List.foldrRecOn [] op b hb hl = hb
            @[simp]
            theorem List.foldrRecOn_cons {α : Type u} {β : Type v} {C : βSort u_2} (x : α) (l : List α) (op : αββ) (b : β) (hb : C b) (hl : (b : β) → C b(a : α) → a x :: lC (op a b)) :
            List.foldrRecOn (x :: l) op b hb hl = hl (List.foldr op b l) (List.foldrRecOn l op b hb fun (b : β) (hb : C b) (a : α) (ha : a l) => hl b hb a (_ : a x :: l)) x (_ : x x :: l)
            @[simp]
            theorem List.foldlRecOn_nil {α : Type u} {β : Type v} {C : βSort u_2} (op : βαβ) (b : β) (hb : C b) (hl : (b : β) → C b(a : α) → a []C (op b a)) :
            List.foldlRecOn [] op b hb hl = hb
            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 α) :
            @[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.get?_zero_scanl {α : Type u} {β : Type v} {f : βαβ} {b : β} {l : List α} :
            @[simp]
            theorem List.get_zero_scanl {α : Type u} {β : Type v} {f : βαβ} {b : β} {l : List α} {h : 0 < List.length (List.scanl f b l)} :
            List.get (List.scanl f b l) { val := 0, isLt := h } = b
            @[simp, deprecated List.get_zero_scanl]
            theorem List.nthLe_zero_scanl {α : Type u} {β : Type v} {f : βαβ} {b : β} {l : List α} {h : 0 < List.length (List.scanl f b l)} :
            List.nthLe (List.scanl f b l) 0 h = b
            theorem List.get?_succ_scanl {α : Type u} {β : Type v} {f : βαβ} {b : β} {l : List α} {i : } :
            List.get? (List.scanl f b l) (i + 1) = Option.bind (List.get? (List.scanl f b l) i) fun (x : β) => Option.map (fun (y : α) => f x y) (List.get? l i)
            @[deprecated List.get_succ_scanl]
            theorem List.nthLe_succ_scanl {α : Type u} {β : Type v} {f : βαβ} {b : β} {l : List α} {i : } {h : i + 1 < List.length (List.scanl f b l)} :
            List.nthLe (List.scanl f b l) (i + 1) h = f (List.nthLe (List.scanl f b l) i (_ : i < List.length (List.scanl f b l))) (List.nthLe l i (_ : i < List.length l))
            theorem List.get_succ_scanl {α : Type u} {β : Type v} {f : βαβ} {b : β} {l : List α} {i : } {h : i + 1 < List.length (List.scanl f b l)} :
            List.get (List.scanl f b l) { val := i + 1, isLt := h } = f (List.get (List.scanl f b l) { val := i, isLt := (_ : i < List.length (List.scanl f b l)) }) (List.get l { val := i, isLt := (_ : i < List.length l) })
            @[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 : 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 : Commutative f) (hassoc : 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 : ααα} (hcomm : Commutative f) (hassoc : 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_assoc {α : Type u} {op : ααα} [ha : Std.Associative op] {l : List α} {a₁ : α} {a₂ : α} :
            List.foldl op (op a₁ a₂) l = op a₁ (List.foldl op 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 (x x_1 : α) => op x x_1) 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 b ← mb 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 #

            @[simp]
            theorem List.splitAt_eq_take_drop {α : Type u} (n : ) (l : List α) :
            theorem List.splitAt_eq_take_drop.go_eq_take_drop {α : Type u} (n : ) (l : List α) (xs : List α) (acc : Array α) :
            List.splitAt.go l xs n acc = if n < List.length xs then (Array.toList acc ++ List.take n xs, List.drop n xs) else (l, [])
            @[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 α) => List.reverse acc ++ 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.join (List.zipWith (fun (x x_1 : List α) => x ++ x_1) (List.splitOnP p as) (List.map (fun (x : α) => [x]) (List.filter p as) ++ [[]])) = as

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

            theorem List.splitOnP_spec.join_zipWith {α : Type u} {xs : List (List α)} {ys : List (List α)} {a : α} (hxs : xs []) (hys : ys []) :
            List.join (List.zipWith (fun (x x_1 : List α) => x ++ x_1) (List.modifyHead (List.cons a) xs) ys) = a :: List.join (List.zipWith (fun (x x_1 : List α) => x ++ x_1) xs ys)
            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 α] :

            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 []) :

            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 α) :
            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 #

            @[simp]
            theorem List.attach_nil {α : Type u} :
            theorem List.sizeOf_lt_sizeOf_of_mem {α : Type u} [SizeOf α] {x : α} {l : List α} (hx : x l) :
            @[simp]
            theorem List.pmap_eq_map {α : Type u} {β : Type v} (p : αProp) (f : αβ) (l : List α) (H : ∀ (a : α), a lp a) :
            List.pmap (fun (a : α) (x : p a) => f a) l H = List.map f l
            theorem List.pmap_congr {α : Type u} {β : Type v} {p : αProp} {q : αProp} {f : (a : α) → p aβ} {g : (a : α) → q aβ} (l : List α) {H₁ : ∀ (a : α), a lp a} {H₂ : ∀ (a : α), a lq a} (h : ∀ (a : α), a l∀ (h₁ : p a) (h₂ : q a), f a h₁ = g a h₂) :
            List.pmap f l H₁ = List.pmap g l H₂
            theorem List.map_pmap {α : Type u} {β : Type v} {γ : Type w} {p : αProp} (g : βγ) (f : (a : α) → p aβ) (l : List α) (H : ∀ (a : α), a lp a) :
            List.map g (List.pmap f l H) = List.pmap (fun (a : α) (h : p a) => g (f a h)) l H
            theorem List.pmap_map {α : Type u} {β : Type v} {γ : Type w} {p : βProp} (g : (b : β) → p bγ) (f : αβ) (l : List α) (H : ∀ (a : β), a List.map f lp a) :
            List.pmap g (List.map f l) H = List.pmap (fun (a : α) (h : p (f a)) => g (f a) h) l (_ : ∀ (a : α), a lp (f a))
            theorem List.pmap_eq_map_attach {α : Type u} {β : Type v} {p : αProp} (f : (a : α) → p aβ) (l : List α) (H : ∀ (a : α), a lp a) :
            List.pmap f l H = List.map (fun (x : { x : α // x l }) => f x (_ : p x)) (List.attach l)
            theorem List.attach_map_coe' {α : Type u} {β : Type v} (l : List α) (f : αβ) :
            List.map (fun (i : { i : α // i l }) => f i) (List.attach l) = List.map f l
            theorem List.attach_map_val' {α : Type u} {β : Type v} (l : List α) (f : αβ) :
            List.map (fun (i : { x : α // x l }) => f i) (List.attach l) = List.map f l
            @[simp]
            theorem List.attach_map_val {α : Type u} (l : List α) :
            List.map Subtype.val (List.attach l) = l
            @[simp]
            theorem List.mem_attach {α : Type u} (l : List α) (x : { x : α // x l }) :
            @[simp]
            theorem List.mem_pmap {α : Type u} {β : Type v} {p : αProp} {f : (a : α) → p aβ} {l : List α} {H : ∀ (a : α), a lp a} {b : β} :
            b List.pmap f l H ∃ (a : α), ∃ (h : a l), f a (_ : p a) = b
            @[simp]
            theorem List.length_pmap {α : Type u} {β : Type v} {p : αProp} {f : (a : α) → p aβ} {l : List α} {H : ∀ (a : α), a lp a} :
            @[simp]
            @[simp]
            theorem List.pmap_eq_nil {α : Type u} {β : Type v} {p : αProp} {f : (a : α) → p aβ} {l : List α} {H : ∀ (a : α), a lp a} :
            List.pmap f l H = [] l = []
            @[simp]
            theorem List.attach_eq_nil {α : Type u} (l : List α) :
            List.attach l = [] l = []
            theorem List.getLast_pmap {α : Type u_2} {β : Type u_3} (p : αProp) (f : (a : α) → p aβ) (l : List α) (hl₁ : ∀ (a : α), a lp a) (hl₂ : l []) :
            List.getLast (List.pmap f l hl₁) (_ : ¬List.pmap f l hl₁ = []) = f (List.getLast l hl₂) (_ : p (List.getLast l hl₂))
            theorem List.get?_pmap {α : Type u} {β : Type v} {p : αProp} (f : (a : α) → p aβ) {l : List α} (h : ∀ (a : α), a lp a) (n : ) :
            List.get? (List.pmap f l h) n = Option.pmap f (List.get? l n) (_ : ∀ (x : α), x List.get? l np x)
            theorem List.get_pmap {α : Type u} {β : Type v} {p : αProp} (f : (a : α) → p aβ) {l : List α} (h : ∀ (a : α), a lp a) {n : } (hn : n < List.length (List.pmap f l h)) :
            List.get (List.pmap f l h) { val := n, isLt := hn } = f (List.get l { val := n, isLt := (_ : n < List.length l) }) (_ : p (List.get l { val := n, isLt := (_ : n < List.length l) }))
            @[deprecated List.get_pmap]
            theorem List.nthLe_pmap {α : Type u} {β : Type v} {p : αProp} (f : (a : α) → p aβ) {l : List α} (h : ∀ (a : α), a lp a) {n : } (hn : n < List.length (List.pmap f l h)) :
            List.nthLe (List.pmap f l h) n hn = f (List.nthLe l n (_ : n < List.length l)) (_ : p (List.nthLe l n (_ : n < List.length l)))
            theorem List.pmap_append {ι : Type u_1} {α : Type u} {p : ιProp} (f : (a : ι) → p aα) (l₁ : List ι) (l₂ : List ι) (h : ∀ (a : ι), a l₁ ++ l₂p a) :
            List.pmap f (l₁ ++ l₂) h = List.pmap f l₁ (_ : ∀ (a : ι), a l₁p a) ++ List.pmap f l₂ (_ : ∀ (a : ι), a l₂p a)
            theorem List.pmap_append' {α : Type u_2} {β : Type u_3} {p : αProp} (f : (a : α) → p aβ) (l₁ : List α) (l₂ : List α) (h₁ : ∀ (a : α), a l₁p a) (h₂ : ∀ (a : α), a l₂p a) :
            List.pmap f (l₁ ++ l₂) (_ : ∀ (a : α), a l₁ ++ l₂p a) = List.pmap f l₁ h₁ ++ List.pmap f l₂ h₂

            find #

            @[simp]
            theorem List.find?_mem {α : Type u} {p : αBool} {l : List α} {a : α} (H : List.find? p l = some a) :
            a l

            lookmap #

            theorem List.lookmap.go_append {α : Type u} (f : αOption α) (l : List α) (acc : Array α) :
            @[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 α) :

            filter #

            filterMap #

            theorem List.Sublist.map {α : Type u} {β : Type v} (f : αβ) {l₁ : List α} {l₂ : List α} (s : List.Sublist l₁ l₂) :
            List.Sublist (List.map f l₁) (List.map f l₂)

            reduceOption #

            @[simp]
            @[simp]
            @[simp]
            theorem List.reduceOption_map {α : Type u} {β : Type v} {l : List (Option α)} {f : αβ} :
            theorem List.reduceOption_mem_iff {α : Type u} {l : List (Option α)} {x : α} :
            theorem List.reduceOption_get?_iff {α : Type u} {l : List (Option α)} {x : α} :
            (∃ (i : ), List.get? l i = some (some x)) ∃ (i : ), List.get? (List.reduceOption l) i = some 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 α} :
            a List.filter p lp 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 α} :
            a lp a = truea List.filter p l
            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) :
            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 (List.attach l) = List.map (Subtype.map id (_ : ∀ (x : α), x List.filter (fun (x : α) => decide (∃ (h : x l), p { val := x, property := h } = true)) lx l)) (List.attach (List.filter (fun (x : α) => decide (∃ (h : x l), p { val := x, property := h } = true)) l))
            theorem List.filter_attach {α : Type u} (l : List α) (p : αBool) :
            List.filter (fun (x : { x : α // x l }) => p x) (List.attach l) = List.map (Subtype.map id (_ : ∀ (x : α), x List.filter p lx l)) (List.attach (List.filter p l))
            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₂ = (List.reverse l₂ ++ List.takeWhile p l₁, List.dropWhile p l₁)
            @[simp]
            theorem List.span_eq_take_drop {α : Type u} (p : αBool) (l : List α) :
            theorem List.dropWhile_nthLe_zero_not {α : Type u} (p : αBool) (l : List α) (hl : 0 < List.length (List.dropWhile p l)) :
            @[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_nil {α : Type u} {p : αBool} :
            theorem List.takeWhile_cons {α : Type u} {p : αBool} {l : List α} {x : α} :
            List.takeWhile p (x :: l) = match p x with | true => x :: List.takeWhile p l | false => []
            theorem List.takeWhile_cons_of_pos {α : Type u} {p : αBool} {l : List α} {x : α} (h : p x = true) :
            theorem List.takeWhile_cons_of_neg {α : Type u} {p : αBool} {l : List α} {x : α} (h : ¬p x = true) :
            List.takeWhile p (x :: l) = []
            @[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 < List.length l), ¬p (List.nthLe l 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) :

            erase #

            @[simp]
            theorem List.length_erase_add_one {α : Type u} [DecidableEq α] {a : α} {l : List α} (h : a l) :
            theorem List.map_erase {α : Type u} {β : Type v} [DecidableEq α] [DecidableEq β] {f : αβ} (finj : Function.Injective f) {a : α} (l : List α) :
            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 : α) => List.erase l (f a)) (List.map f l₁) l₂

            diff #

            @[simp]
            theorem List.map_diff {α : Type u} {β : Type v} [DecidableEq α] [DecidableEq β] {f : αβ} (finj : Function.Injective f) {l₁ : List α} {l₂ : List α} :
            List.map f (List.diff l₁ l₂) = List.diff (List.map f l₁) (List.map f l₂)
            theorem List.erase_diff_erase_sublist_of_sublist {α : Type u} [DecidableEq α] {a : α} {l₁ : List α} {l₂ : List α} :
            List.Sublist l₁ l₂List.Sublist (List.diff (List.erase l₂ a) (List.erase l₁ a)) (List.diff l₂ l₁)

            enum #

            @[simp]
            theorem List.enumFrom_get? {α : Type u} (n : ) (l : List α) (m : ) :
            List.get? (List.enumFrom n l) m = (fun (a : α) => (n + m, a)) <$> List.get? l m
            @[simp]
            theorem List.enum_get? {α : Type u} (l : List α) (n : ) :
            List.get? (List.enum l) n = (fun (a : α) => (n, a)) <$> List.get? l n
            @[simp]
            theorem List.enumFrom_map_snd {α : Type u} (n : ) (l : List α) :
            List.map Prod.snd (List.enumFrom n l) = l
            @[simp]
            theorem List.enum_map_snd {α : Type u} (l : List α) :
            List.map Prod.snd (List.enum l) = l
            theorem List.mem_enumFrom {α : Type u} {x : α} {i : } {j : } (xs : List α) :
            (i, x) List.enumFrom j xsj i i < j + List.length xs x xs
            @[simp]
            theorem List.enum_nil {α : Type u} :
            List.enum [] = []
            @[simp]
            theorem List.enum_cons {α : Type u} (x : α) (xs : List α) :
            List.enum (x :: xs) = (0, x) :: List.enumFrom 1 xs
            @[simp]
            theorem List.enumFrom_singleton {α : Type u} (x : α) (n : ) :
            List.enumFrom n [x] = [(n, x)]
            @[simp]
            theorem List.enum_singleton {α : Type u} (x : α) :
            List.enum [x] = [(0, x)]
            theorem List.enumFrom_append {α : Type u} (xs : List α) (ys : List α) (n : ) :
            theorem List.enum_append {α : Type u} (xs : List α) (ys : List α) :
            theorem List.map_fst_add_enumFrom_eq_enumFrom {α : Type u} (l : List α) (n : ) (k : ) :
            List.map (Prod.map (fun (x : ) => x + n) id) (List.enumFrom k l) = List.enumFrom (n + k) l
            theorem List.map_fst_add_enum_eq_enumFrom {α : Type u} (l : List α) (n :