Documentation

Mathlib.Init.Data.List.Lemmas

Note about Mathlib/Init/ #

The files in Mathlib/Init are leftovers from the port from Mathlib3. (They contain content moved from lean3 itself that Mathlib needed but was not moved to lean4.)

We intend to move all the content of these files out into the main Mathlib directory structure. Contributions assisting with this are appreciated.

#align statements without corresponding declarations (i.e. because the declaration is in Batteries or Lean) can be left here. These will be deleted soon so will not significantly delay deleting otherwise empty Init files.

Lemmas for List not (yet) in Batteries #

append

length

map

bind

mem

source
theorem List.mem_cons_eq {α : Type u} (a : α) (y : α) (l : List α) :
(a ∈ y :: l) = (a = y ∨ a ∈ l)
source
theorem List.eq_or_mem_of_mem_cons :
∀ {α : Type u_1} {a b : α} {l : List α}, a ∈ b :: l → a = b ∨ a ∈ l

Alias of the forward direction of List.mem_cons.

source
theorem List.not_exists_mem_nil {α : Type u} (p : α → Prop) :
¬∃ (x : α), x ∈ [] ∧ p x
source
@[deprecated List.not_exists_mem_nil]
theorem List.not_bex_nil {α : Type u} (p : α → Prop) :
¬∃ (x : α), x ∈ [] ∧ p x

Alias of List.not_exists_mem_nil.

source
@[deprecated List.exists_mem_cons]
theorem List.bex_cons {α : Type u_1} {p : α → Prop} {a : α} {l : List α} :
(∃ (x : α), ∃ (x_1 : x ∈ a :: l), p x) ↔ p a ∨ ∃ (x : α), ∃ (x_1 : x ∈ l), p x

Alias of List.exists_mem_cons.

list subset

sublists

source
theorem List.length_le_of_sublist :
∀ {α : Type u_1} {l₁ l₂ : List α}, l₁.Sublist l₂ → l₁.length ≤ l₂.length

Alias of List.Sublist.length_le.

filter

map_accumr

source
def List.mapAccumr {α : Type u} {β : Type v} {σ : Type w₂} (f : α → σ → σ × β) :
List α → σ → σ × List β

Runs a function over a list returning the intermediate results and a final result.

Equations
Instances For
    source
    @[simp]
    theorem List.length_mapAccumr {α : Type u} {β : Type v} {σ : Type w₂} (f : α → σ → σ × β) (x : List α) (s : σ) :
    (List.mapAccumr f x s).snd.length = x.length

    Length of the list obtained by mapAccumr.

    source
    def List.mapAccumr₂ {α : Type u} {β : Type v} {φ : Type w₁} {σ : Type w₂} (f : α → β → σ → σ × φ) :
    List α → List β → σ → σ × List φ

    Runs a function over two lists returning the intermediate results and a final result.

    Equations
    Instances For
      source
      @[simp]
      theorem List.length_mapAccumr₂ {α : Type u} {β : Type v} {φ : Type w₁} {σ : Type w₂} (f : α → β → σ → σ × φ) (x : List α) (y : List β) (c : σ) :
      (List.mapAccumr₂ f x y c).snd.length = min x.length y.length

      Length of a list obtained using mapAccumr₂.