Basic properties of lists

ink

instance List.uniqueOfIsEmpty {α : Type u} [inst : IsEmpty α] : Unique (List α)

There is only one list of an empty type

Equations

• List.uniqueOfIsEmpty = let src := instInhabitedList; { toInhabited := { default := default }, uniq := (_ : ∀ (l : List α), l = default) }

ink

instance List.instIsLeftIdListAppendInstAppendListNil {α : Type u} : IsLeftId (List α) Append.append []

Equations

• @List.instIsLeftIdListAppendInstAppendListNil = @List.instIsLeftIdListAppendInstAppendListNil.proof_1

ink

instance List.instIsRightIdListAppendInstAppendListNil {α : Type u} : IsRightId (List α) Append.append []

Equations

• @List.instIsRightIdListAppendInstAppendListNil = @List.instIsRightIdListAppendInstAppendListNil.proof_1

ink

instance List.instIsAssociativeListAppendInstAppendList {α : Type u} : IsAssociative (List α) Append.append

Equations

• @List.instIsAssociativeListAppendInstAppendList = @List.instIsAssociativeListAppendInstAppendList.proof_1

ink

@[simp]

theorem List.cons_injective {α : Type u} {a : α} : Function.Injective (List.cons a)

ink

theorem List.cons_eq_cons {α : Type u} {a : α} {b : α} {l : List α} {l' : List α} : a :: l = b :: l' ↔ a = b ∧ l = l'

ink

theorem List.singleton_injective {α : Type u} : Function.Injective fun a => [a]

ink

theorem List.singleton_inj {α : Type u} {a : α} {b : α} : [a] = [b] ↔ a = b

ink

theorem List.set_of_mem_cons {α : Type u} (l : List α) (a : α) : { x | x ∈ a :: l } = insert a { x | x ∈ l }

mem

ink

theorem Decidable.List.eq_or_ne_mem_of_mem {α : Type u} [inst : DecidableEq α] {a : α} {b : α} {l : List α} (h : a ∈ b :: l) : a = b ∨ a ≠ b ∧ a ∈ l

ink

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.

ink

theorem List.not_mem_append {α : Type u} {a : α} {s : List α} {t : List α} (h₁ : ¬a ∈ s) (h₂ : ¬a ∈ t) : ¬a ∈ s ++ t

ink

theorem List.mem_split {α : Type u} {a : α} {l : List α} (h : a ∈ l) : ∃ s t, l = s ++ a :: t

ink

theorem List.mem_of_ne_of_mem {α : Type u} {a : α} {y : α} {l : List α} (h₁ : a ≠ y) (h₂ : a ∈ y :: l) : a ∈ l

ink

theorem List.ne_of_not_mem_cons {α : Type u} {a : α} {b : α} {l : List α} : ¬a ∈ b :: l → a ≠ b

ink

theorem List.not_mem_of_not_mem_cons {α : Type u} {a : α} {b : α} {l : List α} : ¬a ∈ b :: l → ¬a ∈ l

ink

theorem List.not_mem_cons_of_ne_of_not_mem {α : Type u} {a : α} {y : α} {l : List α} : a ≠ y → ¬a ∈ l → ¬a ∈ y :: l

ink

theorem List.ne_and_not_mem_of_not_mem_cons {α : Type u} {a : α} {y : α} {l : List α} : ¬a ∈ y :: l → a ≠ y ∧ ¬a ∈ l

ink

@[simp]

theorem List.mem_map' {α : Type u} {β : Type v} {f : α → β} {b : β} {l : List α} : b ∈ List.map f l ↔ ∃ a, a ∈ l ∧ f a = b

ink

theorem List.exists_of_mem_map' {α : Type u} {β : Type v} {f : α → β} {b : β} {l : List α} : b ∈ List.map f l → ∃ a, a ∈ l ∧ f a = b

Alias of the forward direction of List.mem_map'.

ink

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

ink

@[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

ink

theorem List.mem_map_of_involutive {α : Type u} {f : α → α} (hf : Function.Involutive f) {a : α} {l : List α} : a ∈ List.map f l ↔ f a ∈ l

ink

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

ink

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.

ink

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

Alias of the forward direction of List.length_pos.

ink

theorem List.length_pos_iff_ne_nil {α : Type u} {l : List α} : 0 < List.length l ↔ l ≠ []

ink

theorem List.exists_of_length_succ {α : Type u} {n : ℕ} (l : List α) : List.length l = n + 1 → ∃ h t, l = h :: t

ink

@[simp]

theorem List.length_injective_iff {α : Type u} : Function.Injective List.length ↔ Subsingleton α

ink

@[simp]

theorem List.length_injective {α : Type u} [inst : Subsingleton α] : Function.Injective List.length

ink

theorem List.length_eq_two {α : Type u} {l : List α} : List.length l = 2 ↔ ∃ a b, l = [a, b]

ink

theorem List.length_eq_three {α : Type u} {l : List α} : List.length l = 3 ↔ ∃ a b c, l = [a, b, c]

ink

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

Alias of List.Sublist.length_le.

set-theoretic notation of lists

ink

instance List.instSingletonList {α : Type u} : Singleton α (List α)

Equations

• List.instSingletonList = { singleton := fun x => [x] }

ink

instance List.instInsertList {α : Type u} [inst : DecidableEq α] : Insert α (List α)

Equations

• List.instInsertList = { insert := List.insert }

ink

instance List.instIsLawfulSingletonListInstEmptyCollectionListInstInsertListInstSingletonList {α : Type u} [inst : DecidableEq α] : IsLawfulSingleton α (List α)

Equations

• @List.instIsLawfulSingletonListInstEmptyCollectionListInstInsertListInstSingletonList = @List.instIsLawfulSingletonListInstEmptyCollectionListInstInsertListInstSingletonList.proof_1

ink

theorem List.singleton_eq {α : Type u} (x : α) : {x} = [x]

ink

theorem List.insert_neg {α : Type u} [inst : DecidableEq α] {x : α} {l : List α} (h : ¬x ∈ l) : insert x l = x :: l

ink

theorem List.insert_pos {α : Type u} [inst : DecidableEq α] {x : α} {l : List α} (h : x ∈ l) : insert x l = l

ink

theorem List.doubleton_eq {α : Type u} [inst : DecidableEq α] {x : α} {y : α} (h : x ≠ y) : {x, y} = [x, y]

bounded quantifiers over lists

ink

theorem List.forall_mem_of_forall_mem_cons {α : Type u} {p : α → Prop} {a : α} {l : List α} (h : (x : α) → x ∈ a :: l → p x) (x : α) : x ∈ l → p x

ink

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

ink

theorem List.exists_mem_cons_of {α : Type u} {p : α → Prop} {a : α} (l : List α) (h : p a) : ∃ x, x ∈ a :: l ∧ p x

ink

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

ink

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

ink

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

ink

instance List.instIsTransListSubsetInstHasSubsetList {α : Type u} : IsTrans (List α) Subset

Equations

• @List.instIsTransListSubsetInstHasSubsetList = @List.instIsTransListSubsetInstHasSubsetList.proof_1

ink

theorem List.subset_append_of_subset_right' {α : Type u} (l : List α) (l₁ : List α) (l₂ : List α) : l ⊆ l₂ → l ⊆ l₁ ++ l₂

ink

theorem List.cons_subset_of_subset_of_mem {α : Type u} {a : α} {l : List α} {m : List α} (ainm : a ∈ m) (lsubm : l ⊆ m) : a :: l ⊆ m

ink

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

ink

theorem List.eq_nil_of_subset_nil {α : Type u_1} {l : List α} : l ⊆ [] → l = []

Alias of the forward direction of List.subset_nil.

ink

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

ink

theorem List.append_eq_has_append {α : Type u} {L₁ : List α} {L₂ : List α} : List.append L₁ L₂ = L₁ ++ L₂

ink

theorem List.append_eq_cons_iff {α : Type u} {a : List α} {b : List α} {c : List α} {x : α} : a ++ b = x :: c ↔ a = [] ∧ b = x :: c ∨ ∃ a', a = x :: a' ∧ c = a' ++ b

ink

theorem List.cons_eq_append_iff {α : Type u} {a : List α} {b : List α} {c : List α} {x : α} : x :: c = a ++ b ↔ a = [] ∧ b = x :: c ∨ ∃ a', a = x :: a' ∧ c = a' ++ b

ink

theorem List.append_left_cancel {α : Type u} {s : List α} {t₁ : List α} {t₂ : List α} (h : s ++ t₁ = s ++ t₂) : t₁ = t₂

ink

theorem List.append_right_cancel {α : Type u} {s₁ : List α} {s₂ : List α} {t : List α} (h : s₁ ++ t = s₂ ++ t) : s₁ = s₂

ink

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

ink

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

replicate

ink

@[simp]

theorem List.replicate_zero {α : Type u} (a : α) : List.replicate 0 a = []

ink

theorem List.replicate_one {α : Type u} (a : α) : List.replicate 1 a = [a]

ink

theorem List.eq_replicate_length {α : Type u} {a : α} {l : List α} : l = List.replicate (List.length l) a ↔ ∀ (b : α), b ∈ l → b = a

ink

theorem List.eq_replicate_of_mem {α : Type u} {a : α} {l : List α} : (∀ (b : α), b ∈ l → b = a) → l = List.replicate (List.length l) a

Alias of the reverse direction of List.eq_replicate_length.

ink

theorem List.eq_replicate {α : Type u} {a : α} {n : ℕ} {l : List α} : l = List.replicate n a ↔ List.length l = n ∧ ∀ (b : α), b ∈ l → b = a

ink

theorem List.replicate_add {α : Type u} (m : ℕ) (n : ℕ) (a : α) : List.replicate (m + n) a = List.replicate m a ++ List.replicate n a

ink

theorem List.replicate_succ' {α : Type u} (n : ℕ) (a : α) : List.replicate (n + 1) a = List.replicate n a ++ [a]

ink

theorem List.replicate_subset_singleton {α : Type u} (n : ℕ) (a : α) : List.replicate n a ⊆ [a]

ink

theorem List.subset_singleton_iff {α : Type u} {a : α} {L : List α} : L ⊆ [a] ↔ ∃ n, L = List.replicate n a

ink

@[simp]

theorem List.map_replicate {α : Type u} {β : Type v} (f : α → β) (n : ℕ) (a : α) : List.map f (List.replicate n a) = List.replicate n (f a)

ink

@[simp]

theorem List.tail_replicate {α : Type u} (a : α) (n : ℕ) : List.tail (List.replicate n a) = List.replicate (n - 1) a

ink

@[simp]

theorem List.join_replicate_nil {α : Type u} (n : ℕ) : List.join (List.replicate n []) = []

ink

theorem List.replicate_right_injective {α : Type u} {n : ℕ} (hn : n ≠ 0) : Function.Injective (List.replicate n)

ink

theorem List.replicate_right_inj {α : Type u} {a : α} {b : α} {n : ℕ} (hn : n ≠ 0) : List.replicate n a = List.replicate n b ↔ a = b

ink

@[simp]

theorem List.replicate_right_inj' {α : Type u} {a : α} {b : α} {n : ℕ} : List.replicate n a = List.replicate n b ↔ n = 0 ∨ a = b

ink

theorem List.replicate_left_injective {α : Type u} (a : α) : Function.Injective fun x => List.replicate x a

ink

@[simp]

theorem List.replicate_left_inj {α : Type u} {a : α} {n : ℕ} {m : ℕ} : List.replicate n a = List.replicate m a ↔ n = m

pure

ink

instance List.instMonadList : Monad List

Equations

• List.instMonadList = Monad.mk

ink

theorem List.bind_singleton {α : Type u} {β : Type v} (f : α → List β) (x : α) : List.bind [x] f = f x

ink

@[simp]

theorem List.bind_singleton' {α : Type u} (l : List α) : (List.bind l fun x => [x]) = l

ink

theorem List.map_eq_bind {α : Type u_1} {β : Type u_2} (f : α → β) (l : List α) : List.map f l = List.bind l fun x => [f x]

ink

theorem List.bind_assoc {γ : Type w} {α : Type u_1} {β : Type u_2} (l : List α) (f : α → List β) (g : β → List γ) : List.bind (List.bind l f) g = List.bind l fun x => List.bind (f x) g

ink

instance List.instLawfulMonadListInstMonadList : LawfulMonad List

Equations

• List.instLawfulMonadListInstMonadList = List.instLawfulMonadListInstMonadList.proof_1

ink

@[simp]

theorem List.mem_pure {α : Type u_1} (x : α) (y : α) : x ∈ pure y ↔ x = y

bind

ink

@[simp]

theorem List.bind_eq_bind {α : Type u_1} {β : Type u_1} (f : α → List β) (l : List α) : l >>= f = List.bind l f

ink

theorem List.bind_append {α : Type u} {β : Type v} (f : α → List β) (l₁ : List α) (l₂ : List α) : List.bind (l₁ ++ l₂) f = List.bind l₁ f ++ List.bind l₂ f

concat

ink

theorem List.concat_nil {α : Type u} (a : α) : List.concat [] a = [a]

ink

theorem List.concat_cons {α : Type u} (a : α) (b : α) (l : List α) : List.concat (a :: l) b = a :: List.concat l b

ink

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

ink

theorem List.init_eq_of_concat_eq {α : Type u} {a : α} {l₁ : List α} {l₂ : List α} : List.concat l₁ a = List.concat l₂ a → l₁ = l₂

ink

theorem List.last_eq_of_concat_eq {α : Type u} {a : α} {b : α} {l : List α} : List.concat l a = List.concat l b → a = b

ink

theorem List.concat_ne_nil {α : Type u} (a : α) (l : List α) : List.concat l a ≠ []

ink

theorem List.concat_append {α : Type u} (a : α) (l₁ : List α) (l₂ : List α) : List.concat l₁ a ++ l₂ = l₁ ++ a :: l₂

ink

theorem List.length_concat' {α : Type u} (a : α) (l : List α) : List.length (List.concat l a) = Nat.succ (List.length l)

ink

theorem List.append_concat {α : Type u} (a : α) (l₁ : List α) (l₂ : List α) : l₁ ++ List.concat l₂ a = List.concat (l₁ ++ l₂) a

reverse

ink

theorem List.reverse_cons' {α : Type u} (a : α) (l : List α) : List.reverse (a :: l) = List.concat (List.reverse l) a

ink

theorem List.reverse_singleton {α : Type u} (a : α) : List.reverse [a] = [a]

ink

@[simp]

theorem List.reverse_involutive {α : Type u} : Function.Involutive List.reverse

ink

@[simp]

theorem List.reverse_injective {α : Type u} : Function.Injective List.reverse

ink

theorem List.reverse_surjective {α : Type u} : Function.Surjective List.reverse

ink

theorem List.reverse_bijective {α : Type u} : Function.Bijective List.reverse

ink

@[simp]

theorem List.reverse_inj {α : Type u} {l₁ : List α} {l₂ : List α} : List.reverse l₁ = List.reverse l₂ ↔ l₁ = l₂

ink

theorem List.reverse_eq_iff {α : Type u} {l : List α} {l' : List α} : List.reverse l = l' ↔ l = List.reverse l'

ink

@[simp]

theorem List.reverse_eq_nil {α : Type u} {l : List α} : List.reverse l = [] ↔ l = []

ink

theorem List.concat_eq_reverse_cons {α : Type u} (a : α) (l : List α) : List.concat l a = List.reverse (a :: List.reverse l)

ink

theorem List.map_reverse {α : Type u} {β : Type v} (f : α → β) (l : List α) : List.map f (List.reverse l) = List.reverse (List.map f l)

ink

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₂)

ink

theorem List.mem_reverse' {α : Type u} {a : α} {l : List α} : a ∈ List.reverse l ↔ a ∈ l

ink

@[simp]

theorem List.reverse_replicate {α : Type u} (n : ℕ) (a : α) : List.reverse (List.replicate n a) = List.replicate n a

empty

ink

theorem List.isEmpty_iff_eq_nil {α : Type u} {l : List α} : List.isEmpty l = true ↔ l = []

dropLast

ink

@[simp]

theorem List.length_dropLast {α : Type u} (l : List α) : List.length (List.dropLast l) = List.length l - 1

ink

theorem List.dropLast_cons_cons {α : Type u} (a : α) (b : α) (l : List α) : List.dropLast (a :: b :: l) = a :: List.dropLast (b :: l)

getLast

ink

@[simp]

theorem List.getLast_cons {α : Type u} {a : α} {l : List α} (h : l ≠ []) : List.getLast (a :: l) (_ : a :: l ≠ []) = List.getLast l h

ink

theorem List.getLast_append_singleton {α : Type u} {a : α} (l : List α) : List.getLast (l ++ [a]) (_ : l ++ [a] ≠ []) = a

ink

theorem List.getLast_append' {α : Type u} (l₁ : List α) (l₂ : List α) (h : l₂ ≠ []) : List.getLast (l₁ ++ l₂) (_ : l₁ ++ l₂ ≠ []) = List.getLast l₂ h

ink

theorem List.getLast_concat' {α : Type u} {a : α} (l : List α) : List.getLast (List.concat l a) (_ : List.concat l a ≠ []) = a

ink

@[simp]

theorem List.getLast_singleton' {α : Type u} (a : α) : List.getLast [a] (_ : [a] ≠ []) = a

ink

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

ink

theorem List.dropLast_append_getLast {α : Type u} {l : List α} (h : l ≠ []) : List.dropLast l ++ [List.getLast l h] = l

ink

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₂

ink

theorem List.getLast_mem {α : Type u} {l : List α} (h : l ≠ []) : List.getLast l h ∈ l

ink

theorem List.getLast_replicate_succ {α : Type u} (m : ℕ) (a : α) : List.getLast (List.replicate (m + 1) a) (_ : List.replicate (m + 1) a ≠ []) = a

getLast?

ink

@[simp]

theorem List.getLast?_singleton {α : Type u} (a : α) : List.getLast? [a] = some a

ink

@[simp]

theorem List.getLast?_cons_cons {α : Type u} (a : α) (b : α) (l : List α) : List.getLast? (a :: b :: l) = List.getLast? (b :: l)

ink

@[simp]

theorem List.getLast?_isNone {α : Type u} {l : List α} : Option.isNone (List.getLast? l) = true ↔ l = []

ink

@[simp]

theorem List.getLast?_isSome {α : Type u} {l : List α} : Option.isSome (List.getLast? l) = true ↔ l ≠ []

ink

theorem List.mem_getLast?_eq_getLast {α : Type u} {l : List α} {x : α} : x ∈ List.getLast? l → ∃ h, x = List.getLast l h

ink

theorem List.getLast?_eq_getLast_of_ne_nil {α : Type u} {l : List α} (h : l ≠ []) : List.getLast? l = some (List.getLast l h)

ink

theorem List.mem_getLast?_cons {α : Type u} {x : α} {y : α} {l : List α} : x ∈ List.getLast? l → x ∈ List.getLast? (y :: l)

ink

theorem List.mem_of_mem_getLast? {α : Type u} {l : List α} {a : α} (ha : a ∈ List.getLast? l) : a ∈ l

ink

theorem List.dropLast_append_getLast? {α : Type u} {l : List α} (a : α) : a ∈ List.getLast? l → List.dropLast l ++ [a] = l

ink

theorem List.getLastI_eq_getLast? {α : Type u} [inst : Inhabited α] (l : List α) : List.getLastI l = Option.iget (List.getLast? l)

ink

@[simp]

theorem List.getLast?_append_cons {α : Type u} (l₁ : List α) (a : α) (l₂ : List α) : List.getLast? (l₁ ++ a :: l₂) = List.getLast? (a :: l₂)

ink

theorem List.getLast?_append_of_ne_nil {α : Type u} (l₁ : List α) {l₂ : List α} : l₂ ≠ [] → List.getLast? (l₁ ++ l₂) = List.getLast? l₂

ink

theorem List.getLast?_append {α : Type u} {l₁ : List α} {l₂ : List α} {x : α} (h : x ∈ List.getLast? l₂) : x ∈ List.getLast? (l₁ ++ l₂)

head(!?) and tail

ink

theorem List.head!_eq_head? {α : Type u} [inst : Inhabited α] (l : List α) : List.head! l = Option.iget (List.head? l)

ink

theorem List.surjective_head {α : Type u} [inst : Inhabited α] : Function.Surjective List.head!

ink

theorem List.surjective_head' {α : Type u} : Function.Surjective List.head?

ink

theorem List.surjective_tail {α : Type u} : Function.Surjective List.tail

ink

theorem List.eq_cons_of_mem_head? {α : Type u} {x : α} {l : List α} : x ∈ List.head? l → l = x :: List.tail l

ink

theorem List.mem_of_mem_head? {α : Type u} {x : α} {l : List α} (h : x ∈ List.head? l) : x ∈ l

ink

@[simp]

theorem List.head!_cons {α : Type u} [inst : Inhabited α] (a : α) (l : List α) : List.head! (a :: l) = a

ink

@[simp]

theorem List.head!_append {α : Type u} [inst : Inhabited α] (t : List α) {s : List α} (h : s ≠ []) : List.head! (s ++ t) = List.head! s

ink

theorem List.head?_append {α : Type u} {s : List α} {t : List α} {x : α} (h : x ∈ List.head? s) : x ∈ List.head? (s ++ t)

ink

theorem List.head?_append_of_ne_nil {α : Type u} (l₁ : List α) {l₂ : List α} : l₁ ≠ [] → List.head? (l₁ ++ l₂) = List.head? l₁

ink

theorem List.tail_append_singleton_of_ne_nil {α : Type u} {a : α} {l : List α} (h : l ≠ []) : List.tail (l ++ [a]) = List.tail l ++ [a]

ink

theorem List.cons_head?_tail {α : Type u} {l : List α} {a : α} : a ∈ List.head? l → a :: List.tail l = l

ink

theorem List.head!_mem_head? {α : Type u} [inst : Inhabited α] {l : List α} : l ≠ [] → List.head! l ∈ List.head? l

ink

theorem List.cons_head!_tail {α : Type u} [inst : Inhabited α] {l : List α} (h : l ≠ []) : List.head! l :: List.tail l = l

ink

theorem List.head!_mem_self {α : Type u} [inst : Inhabited α] {l : List α} (h : l ≠ []) : List.head! l ∈ l

ink

@[simp]

theorem List.head?_map {α : Type u} {β : Type v} (f : α → β) (l : List α) : List.head? (List.map f l) = Option.map f (List.head? l)

ink

theorem List.tail_append_of_ne_nil {α : Type u} (l : List α) (l' : List α) (h : l ≠ []) : List.tail (l ++ l') = List.tail l ++ l'

ink

@[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'

ink

theorem List.nthLe_cons_aux {α : Type u} {l : List α} {a : α} {n : ℕ} (hn : n ≠ 0) (h : n < List.length (a :: l)) : n - 1 < List.length l

ink

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)

ink

@[simp]

theorem List.modifyHead_modifyHead {α : Type u} (l : List α) (f : α → α) (g : α → α) : List.modifyHead g (List.modifyHead f l) = List.modifyHead (g ∘ f) l

Induction from the right

ink

def List.reverseRecOn {α : Type u} {C : List α → Sort u_1} (l : List α) (H0 : C []) (H1 : (l : List α) → (a : α) → C l → C (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.

ink

def List.bidirectionalRec {α : Type u} {C : List α → Sort u_1} (H0 : C []) (H1 : (a : α) → C [a]) (Hn : (a : α) → (l : List α) → (b : α) → C l → C (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

• One or more equations did not get rendered due to their size.
• List.bidirectionalRec H0 H1 Hn [] = H0
• List.bidirectionalRec H0 H1 Hn [a] = H1 a

ink

def List.bidirectionalRecOn {α : Type u} {C : List α → Sort u_1} (l : List α) (H0 : C []) (H1 : (a : α) → C [a]) (Hn : (a : α) → (l : List α) → (b : α) → C l → C (a :: (l ++ [b]))) : C l

Like bidirectionalRec, but with the list parameter placed first.

Equations

• List.bidirectionalRecOn l H0 H1 Hn = List.bidirectionalRec H0 H1 Hn l

sublists

ink

theorem List.Sublist.cons_cons {α : Type u} {l₁ : List α} {l₂ : List α} (a : α) (s : List.Sublist l₁ l₂) : List.Sublist (a :: l₁) (a :: l₂)

ink

theorem List.sublist_cons_of_sublist {α : Type u} (a : α) {l₁ : List α} {l₂ : List α} : List.Sublist l₁ l₂ → List.Sublist l₁ (a :: l₂)

ink

theorem List.sublist_of_cons_sublist_cons {α : Type u} {l₁ : List α} {l₂ : List α} {a : α} : List.Sublist (a :: l₁) (a :: l₂) → List.Sublist l₁ l₂

ink

theorem List.cons_sublist_cons_iff {α : Type u} {l₁ : List α} {l₂ : List α} {a : α} : List.Sublist (a :: l₁) (a :: l₂) ↔ List.Sublist l₁ l₂

ink

@[simp]

theorem List.singleton_sublist {α : Type u} {a : α} {l : List α} : List.Sublist [a] l ↔ a ∈ l

ink

theorem List.eq_nil_of_sublist_nil {α : Type u} {l : List α} (s : List.Sublist l []) : l = []

ink

@[simp]

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

ink

@[simp]

theorem List.replicate_sublist_replicate {α : Type u} {m : ℕ} {n : ℕ} (a : α) : List.Sublist (List.replicate m a) (List.replicate n a) ↔ m ≤ n

ink

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

ink

theorem List.Sublist.eq_of_length {α : Type u} {l₁ : List α} {l₂ : List α} : List.Sublist l₁ l₂ → List.length l₁ = List.length l₂ → l₁ = l₂

ink

theorem List.Sublist.eq_of_length_le {α : Type u} {l₁ : List α} {l₂ : List α} (s : List.Sublist l₁ l₂) (h : List.length l₂ ≤ List.length l₁) : l₁ = l₂

ink

theorem List.Sublist.antisymm {α : Type u} {l₁ : List α} {l₂ : List α} (s₁ : List.Sublist l₁ l₂) (s₂ : List.Sublist l₂ l₁) : l₁ = l₂

ink

instance List.decidableSublist {α : Type u} [inst : DecidableEq α] (l₁ : List α) (l₂ : List α) : Decidable (List.Sublist l₁ l₂)

Equations

• One or more equations did not get rendered due to their size.
• List.decidableSublist [] x = isTrue (_ : List.Sublist [] x)
• List.decidableSublist (head :: tail) [] = isFalse (_ : List.Sublist (head :: tail) [] → List.noConfusionType False (head :: tail) [])

indexOf

ink

theorem List.indexOf_nil {α : Type u} [inst : DecidableEq α] (a : α) : List.indexOf a [] = 0

ink

@[simp]

theorem List.indexOf_cons_self {α : Type u} [inst : DecidableEq α] (a : α) (l : List α) : List.indexOf a (a :: l) = 0

ink

theorem List.indexOf_cons_eq {α : Type u} [inst : DecidableEq α] {a : α} {b : α} (l : List α) : a = b → List.indexOf a (b :: l) = 0

ink

@[simp]

theorem List.indexOf_cons_ne {α : Type u} [inst : DecidableEq α] {a : α} {b : α} (l : List α) : a ≠ b → List.indexOf a (b :: l) = Nat.succ (List.indexOf a l)

ink

theorem List.indexOf_cons_ne.findIdx_go_succ {α : Type u} (p : α → Bool) (l : List α) (n : ℕ) : List.findIdx.go p l (n + 1) = Nat.succ (List.findIdx.go p l n)

ink

theorem List.indexOf_cons {α : Type u} [inst : DecidableEq α] (a : α) (b : α) (l : List α) : List.indexOf a (b :: l) = if a = b then 0 else Nat.succ (List.indexOf a l)

ink

theorem List.indexOf_eq_length {α : Type u} [inst : DecidableEq α] {a : α} {l : List α} : List.indexOf a l = List.length l ↔ ¬a ∈ l

ink

@[simp]

theorem List.indexOf_of_not_mem {α : Type u} [inst : DecidableEq α] {l : List α} {a : α} : ¬a ∈ l → List.indexOf a l = List.length l

ink

theorem List.indexOf_le_length {α : Type u} [inst : DecidableEq α] {a : α} {l : List α} : List.indexOf a l ≤ List.length l

ink

theorem List.indexOf_lt_length {α : Type u} [inst : DecidableEq α] {a : α} {l : List α} : List.indexOf a l < List.length l ↔ a ∈ l

ink

theorem List.indexOf_append_of_mem {α : Type u} {l₁ : List α} {l₂ : List α} [inst : DecidableEq α] {a : α} (h : a ∈ l₁) : List.indexOf a (l₁ ++ l₂) = List.indexOf a l₁

ink

theorem List.indexOf_append_of_not_mem {α : Type u} {l₁ : List α} {l₂ : List α} [inst : DecidableEq α] {a : α} (h : ¬a ∈ l₁) : List.indexOf a (l₁ ++ l₂) = List.length l₁ + List.indexOf a l₂

nth element

ink

theorem List.nthLe_of_mem {α : Type u} {a : α} {l : List α} (h : a ∈ l) : ∃ n h, List.nthLe l n h = a

ink

theorem List.nthLe_get? {α : Type u} {l : List α} {n : ℕ} (h : n < List.length l) : List.get? l n = some (List.nthLe l n h)

ink

@[simp]

theorem List.get?_length {α : Type u} (l : List α) : List.get? l (List.length l) = none

ink

theorem List.get?_eq_some' {α : Type u} {l : List α} {n : ℕ} {a : α} : List.get? l n = some a ↔ ∃ h, List.nthLe l n h = a

ink

theorem List.nthLe_mem {α : Type u} (l : List α) (n : ℕ) (h : n < List.length l) : List.nthLe l n h ∈ l

ink

theorem List.mem_iff_nthLe {α : Type u} {a : α} {l : List α} : a ∈ l ↔ ∃ n h, List.nthLe l n h = a

ink

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

ink

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)

ink

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.

ink

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.

ink

@[simp]

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))

ink

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).

ink

@[simp]

theorem List.nthLe_singleton {α : Type u} (a : α) {n : ℕ} (hn : n < 1) : List.nthLe [a] n hn = a

ink

theorem List.nthLe_zero {α : Type u} [inst : Inhabited α] {L : List α} (h : 0 < List.length L) : List.nthLe L 0 h = List.head! L

ink

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₂

ink

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₂)

ink

theorem List.nthLe_replicate {α : Type u} (a : α) {n : ℕ} {m : ℕ} (h : m < List.length (List.replicate n a)) : List.nthLe (List.replicate n a) m h = a

ink

theorem List.getLast_eq_nthLe {α : Type u} (l : List α) (h : l ≠ []) : List.getLast l h = List.nthLe l (List.length l - 1) (_ : List.length l - 1 < List.length l)

ink

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)

ink

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)

ink

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

ink

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 }]

ink

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.nthLe l n h]

ink

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₂

ink

@[simp]

theorem List.indexOf_get {α : Type u} [inst : DecidableEq α] {a : α} {l : List α} (h : List.indexOf a l < List.length l) : List.get l { val := List.indexOf a l, isLt := h } = a

ink

@[simp]

theorem List.indexOf_nthLe {α : Type u} [inst : DecidableEq α] {a : α} {l : List α} (h : List.indexOf a l < List.length l) : List.nthLe l (List.indexOf a l) h = a

ink

@[simp]

theorem List.indexOf_get? {α : Type u} [inst : DecidableEq α] {a : α} {l : List α} (h : a ∈ l) : List.get? l (List.indexOf a l) = some a

ink

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 }

ink

theorem List.indexOf_inj {α : Type u} [inst : DecidableEq α] {l : List α} {x : α} {y : α} (hx : x ∈ l) (hy : y ∈ l) : List.indexOf x l = List.indexOf y l ↔ x = y

ink

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 }

ink

@[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 }

ink

@[simp]

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) : List.nthLe (List.reverse l) (List.length l - 1 - i) h1 = List.nthLe l i h2

ink

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) : List.nthLe (List.reverse l) n hn = List.nthLe l (List.length l - 1 - n) hn'

ink

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' }

ink

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

ink

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

ink

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

ink

theorem List.some_nthLe_eq {α : Type u} {l : List α} {n : ℕ} {h : n < List.length l} : some (List.nthLe l n h) = List.get? l n

ink

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.modifyNthTail g m (f l)) n l

ink

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.modifyNthTail g (m - n) (f l)) n l

ink

theorem List.modifyNthTail_modifyNthTail_same {α : Type u} {f : List α → List α} {g : List α → List α} (n : ℕ) (l : List α) : List.modifyNthTail g n (List.modifyNthTail f n l) = List.modifyNthTail (g ∘ f) n l

ink

theorem List.removeNth_eq_nthTail {α : Type u} (n : ℕ) (l : List α) : List.removeNth l n = List.modifyNthTail List.tail n l

ink

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

ink

theorem List.length_modifyNthTail {α : Type u} (f : List α → List α) (H : ∀ (l : List α), List.length (f l) = List.length l) (n : ℕ) (l : List α) : List.length (List.modifyNthTail f n l) = List.length l

ink

theorem List.length_modifyNth {α : Type u} (f : α → α) (n : ℕ) (l : List α) : List.length (List.modifyNth f n l) = List.length l

ink

@[simp]

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

ink

@[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) }

ink

@[simp]

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)

ink

@[simp]

theorem List.insertNth_zero {α : Type u} (s : List α) (x : α) : List.insertNth 0 x s = x :: s

ink

@[simp]

theorem List.insertNth_succ_nil {α : Type u} (n : ℕ) (a : α) : List.insertNth (n + 1) a [] = []

ink

@[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

ink

theorem List.length_insertNth {α : Type u} {a : α} (n : ℕ) (as : List α) : n ≤ List.length as → List.length (List.insertNth n a as) = List.length as + 1

ink

theorem List.removeNth_insertNth {α : Type u} {a : α} (n : ℕ) (l : List α) : List.removeNth (List.insertNth n a l) n = l

ink

theorem List.insertNth_removeNth_of_ge {α : Type u} {a : α} (n : ℕ) (m : ℕ) (as : List α) : n < List.length as → n ≤ m → List.insertNth m a (List.removeNth as n) = List.removeNth (List.insertNth (m + 1) a as) n

ink

theorem List.insertNth_removeNth_of_le {α : Type u} {a : α} (n : ℕ) (m : ℕ) (as : List α) : n < List.length as → m ≤ n → List.insertNth m a (List.removeNth as n) = List.removeNth (List.insertNth m a as) (n + 1)

ink

theorem List.insertNth_comm {α : Type u} (a : α) (b : α) (i : ℕ) (j : ℕ) (l : List α) : i ≤ j → j ≤ List.length l → List.insertNth (j + 1) b (List.insertNth i a l) = List.insertNth i a (List.insertNth j b l)

ink

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)

ink

theorem List.insertNth_of_length_lt {α : Type u} (l : List α) (x : α) (n : ℕ) (h : List.length l < n) : List.insertNth n x l = l

ink

@[simp]

theorem List.insertNth_length_self {α : Type u} (l : List α) (x : α) : List.insertNth (List.length l) x l = l ++ [x]

ink

theorem List.length_le_length_insertNth {α : Type u} (l : List α) (x : α) (n : ℕ) : List.length l ≤ List.length (List.insertNth n x l)

ink

theorem List.length_insertNth_le_succ {α : Type u} (l : List α) (x : α) (n : ℕ) : List.length (List.insertNth n x l) ≤ List.length l + 1

ink

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 }

ink

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

ink

@[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

ink

@[simp]

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

ink

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' }

ink

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'

ink

theorem List.insertNth_injective {α : Type u} (n : ℕ) (x : α) : Function.Injective (List.insertNth n x)

map

ink

theorem List.map_eq_foldr {α : Type u} {β : Type v} (f : α → β) (l : List α) : List.map f l = List.foldr (fun a bs => f a :: bs) [] l

ink

theorem List.map_congr {α : Type u} {β : Type v} {f : α → β} {g : α → β} {l : List α} : (∀ (x : α), x ∈ l → f x = g x) → List.map f l = List.map g l

ink

theorem List.map_eq_map_iff {α : Type u} {β : Type v} {f : α → β} {g : α → β} {l : List α} : List.map f l = List.map g l ↔ ∀ (x : α), x ∈ l → f x = g x

ink

theorem List.map_concat {α : Type u} {β : Type v} (f : α → β) (a : α) (l : List α) : List.map f (List.concat l a) = List.concat (List.map f l) (f a)

ink

@[simp]

theorem List.map_id'' {α : Type u} (l : List α) : List.map (fun x => x) l = l

ink

theorem List.map_id' {α : Type u} {f : α → α} (h : ∀ (x : α), f x = x) (l : List α) : List.map f l = l

ink

theorem List.eq_nil_of_map_eq_nil {α : Type u} {β : Type v} {f : α → β} {l : List α} (h : List.map f l = []) : l = []

ink

@[simp]

theorem List.map_join {α : Type u} {β : Type v} (f : α → β) (L : List (List α)) : List.map f (List.join L) = List.join (List.map (List.map f) L)

ink

theorem List.bind_ret_eq_map {α : Type u} {β : Type v} (f : α → β) (l : List α) : List.bind l (List.ret ∘ f) = List.map f l

ink

theorem List.bind_congr {α : Type u} {β : Type v} {l : List α} {f : α → List β} {g : α → List β} (h : ∀ (x : α), x ∈ l → f x = g x) : List.bind l f = List.bind l g

ink

@[simp]

theorem List.map_eq_map {α : Type u_1} {β : Type u_1} (f : α → β) (l : List α) : f <$> l = List.map f l

ink

@[simp]

theorem List.map_tail {α : Type u} {β : Type v} (f : α → β) (l : List α) : List.map f (List.tail l) = List.tail (List.map f l)

ink

@[simp]

theorem List.map_injective_iff {α : Type u} {β : Type v} {f : α → β} : Function.Injective (List.map f) ↔ Function.Injective f

ink

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.

ink

@[simp]

theorem List.map_comp_map {α : Type u} {β : Type v} {γ : Type w} (g : β → γ) (f : α → β) : List.map g ∘ List.map f = List.map (g ∘ f)

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

ink

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 => bif p a then f a :: bs else bs) [] as

ink

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)

ink

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 ∈ l → f x = b

ink

@[simp]

theorem List.map_const {α : Type u} {β : Type v} (l : List α) (b : β) : List.map (Function.const α b) l = List.replicate (List.length l) b

ink

@[simp]

theorem List.map_const' {α : Type u} {β : Type v} (l : List α) (b : β) : List.map (fun x => b) l = List.replicate (List.length l) b

ink

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

ink

theorem List.nil_zipWith {α : Type u} {β : Type v} {γ : Type w} (f : α → β → γ) (l : List β) : List.zipWith f [] l = []

ink

theorem List.zipWith_nil {α : Type u} {β : Type v} {γ : Type w} (f : α → β → γ) (l : List α) : List.zipWith f l [] = []

ink

@[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

ink

@[simp]

theorem List.take_zero {α : Type u} (l : List α) : List.take 0 l = []

ink

@[simp]

theorem List.take_nil {α : Type u} (n : ℕ) : List.take n [] = []

ink

theorem List.take_cons {α : Type u} (n : ℕ) (a : α) (l : List α) : List.take (Nat.succ n) (a :: l) = a :: List.take n l

ink

theorem List.take_all_of_le {α : Type u} {n : ℕ} {l : List α} : List.length l ≤ n → List.take n l = l

ink

@[simp]

theorem List.take_left {α : Type u} (l₁ : List α) (l₂ : List α) : List.take (List.length l₁) (l₁ ++ l₂) = l₁

ink

theorem List.take_left' {α : Type u} {l₁ : List α} {l₂ : List α} {n : ℕ} (h : List.length l₁ = n) : List.take n (l₁ ++ l₂) = l₁

ink

theorem List.take_take {α : Type u} (n : ℕ) (m : ℕ) (l : List α) : List.take n (List.take m l) = List.take (min n m) l

ink

theorem List.take_replicate {α : Type u} (a : α) (n : ℕ) (m : ℕ) : List.take n (List.replicate m a) = List.replicate (min n m) a

ink

theorem List.map_take {α : Type u_1} {β : Type u_2} (f : α → β) (L : List α) (i : ℕ) : List.map f (List.take i L) = List.take i (List.map f L)

ink

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₂.

ink

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₁

ink

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₁.

ink

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.

ink

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.

ink

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.

ink

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.

ink

theorem List.get?_take {α : Type u} {l : List α} {n : ℕ} {m : ℕ} (h : m < n) : List.get? (List.take n l) m = List.get? l m

ink

@[simp]

theorem List.nth_take_of_succ {α : Type u} {l : List α} {n : ℕ} : List.get? (List.take (n + 1) l) n = List.get? l n

ink

theorem List.take_succ {α : Type u} {l : List α} {n : ℕ} : List.take (n + 1) l = List.take n l ++ Option.toList (List.get? l n)

ink

@[simp]

theorem List.take_eq_nil_iff {α : Type u} {l : List α} {k : ℕ} : List.take k l = [] ↔ l = [] ∨ k = 0

ink

theorem List.take_eq_take {α : Type u} {l : List α} {m : ℕ} {n : ℕ} : List.take m l = List.take n l ↔ min m (List.length l) = min n (List.length l)

ink

theorem List.take_add {α : Type u} (l : List α) (m : ℕ) (n : ℕ) : List.take (m + n) l = List.take m l ++ List.take n (List.drop m l)

ink

theorem List.dropLast_eq_take {α : Type u} (l : List α) : List.dropLast l = List.take (Nat.pred (List.length l)) l

ink

theorem List.dropLast_take {α : Type u} {n : ℕ} {l : List α} (h : n < List.length l) : List.dropLast (List.take n l) = List.take (Nat.pred n) l

ink

theorem List.dropLast_cons_of_ne_nil {α : Type u_1} {x : α} {l : List α} (h : l ≠ []) : List.dropLast (x :: l) = x :: List.dropLast l

ink

@[simp]

theorem List.dropLast_append_of_ne_nil {α : Type u_1} {l : List α} (l' : List α) : l ≠ [] → List.dropLast (l' ++ l) = l' ++ List.dropLast l

ink

theorem List.drop_eq_nil_iff_le {α : Type u} {l : List α} {k : ℕ} : List.drop k l = [] ↔ List.length l ≤ k

ink

theorem List.tail_drop {α : Type u} (l : List α) (n : ℕ) : List.tail (List.drop n l) = List.drop (n + 1) l

ink

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

ink

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

ink

@[simp]

theorem List.drop_one {α : Type u} (l : List α) : List.drop 1 l = List.tail l

ink

theorem List.drop_add {α : Type u} (m : ℕ) (n : ℕ) (l : List α) : List.drop (m + n) l = List.drop m (List.drop n l)

ink

@[simp]

theorem List.drop_left {α : Type u} (l₁ : List α) (l₂ : List α) : List.drop (List.length l₁) (l₁ ++ l₂) = l₂

ink

theorem List.drop_left' {α : Type u} {l₁ : List α} {l₂ : List α} {n : ℕ} (h : List.length l₁ = n) : List.drop n (l₁ ++ l₂) = l₂

ink

theorem List.drop_eq_get_cons {α : Type u} {n : ℕ} {l : List α} (h : n < List.length l) : List.drop n l = List.get l { val := n, isLt := h } :: List.drop (n + 1) l

ink

theorem List.drop_length_cons {α : Type u} {l : List α} (h : l ≠ []) (a : α) : List.drop (List.length l) (a :: l) = [List.getLast l h]

ink

theorem List.drop_append_eq_append_drop {α : Type u} {l₁ : List α} {l₂ : List α} {n : ℕ} : List.drop n (l₁ ++ l₂) = List.drop n l₁ ++ List.drop (n - List.length l₁) l₂

Dropping the elements up to n in l₁ ++ l₂ is the same as dropping the elements up to n in l₁, dropping the elements up to n - l₁.length in l₂, and appending them.

ink

theorem List.drop_append_of_le_length {α : Type u} {l₁ : List α} {l₂ : List α} {n : ℕ} (h : n ≤ List.length l₁) : List.drop n (l₁ ++ l₂) = List.drop n l₁ ++ l₂

ink

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₂.

ink

theorem List.drop_sizeOf_le {α : Type u} [inst : SizeOf α] (l : List α) (n : ℕ) : sizeOf (List.drop n l) ≤ sizeOf l

ink

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.

ink

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.

ink

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.

ink

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.

ink

theorem List.get?_drop {α : Type u} (L : List α) (i : ℕ) (j : ℕ) : List.get? (List.drop i L) j = List.get? L (i + j)

ink

@[simp]

theorem List.drop_drop {α : Type u} (n : ℕ) (m : ℕ) (l : List α) : List.drop n (List.drop m l) = List.drop (n + m) l

ink

theorem List.drop_take {α : Type u} (m : ℕ) (n : ℕ) (l : List α) : List.drop m (List.take (m + n) l) = List.take n (List.drop m l)

ink

theorem List.map_drop {α : Type u_1} {β : Type u_2} (f : α → β) (L : List α) (i : ℕ) : List.map f (List.drop i L) = List.drop i (List.map f L)

ink

theorem List.modifyNthTail_eq_take_drop {α : Type u} (f : List α → List α) (H : f [] = []) (n : ℕ) (l : List α) : List.modifyNthTail f n l = List.take n l ++ f (List.drop n l)

ink

theorem List.modifyNth_eq_take_drop {α : Type u} (f : α → α) (n : ℕ) (l : List α) : List.modifyNth f n l = List.take n l ++ List.modifyHead f (List.drop n l)

ink

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

ink

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

ink

theorem List.reverse_take {α : Type u_1} {xs : List α} (n : ℕ) (h : n ≤ List.length xs) : List.take n (List.reverse xs) = List.reverse (List.drop (List.length xs - n) xs)

ink

@[simp]

theorem List.set_eq_nil {α : Type u} (l : List α) (n : ℕ) (a : α) : List.set l n a = [] ↔ l = []

ink

@[simp]

theorem List.takeI_length {α : Type u} [inst : Inhabited α] (n : ℕ) (l : List α) : List.length (List.takeI n l) = n

ink

@[simp]

theorem List.takeI_nil {α : Type u} [inst : Inhabited α] (n : ℕ) : List.takeI n [] = List.replicate n default

ink

theorem List.takeI_eq_take {α : Type u} [inst : Inhabited α] {n : ℕ} {l : List α} : n ≤ List.length l → List.takeI n l = List.take n l

ink

@[simp]

theorem List.takeI_left {α : Type u} [inst : Inhabited α] (l₁ : List α) (l₂ : List α) : List.takeI (List.length l₁) (l₁ ++ l₂) = l₁

ink

theorem List.takeI_left' {α : Type u} [inst : Inhabited α] {l₁ : List α} {l₂ : List α} {n : ℕ} (h : List.length l₁ = n) : List.takeI n (l₁ ++ l₂) = l₁

ink

@[simp]

theorem List.takeD_length {α : Type u} (n : ℕ) (l : List α) (a : α) : List.length (List.takeD n l a) = n

ink

theorem List.takeD_eq_take {α : Type u} {n : ℕ} {l : List α} (a : α) : n ≤ List.length l → List.takeD n l a = List.take n l

ink

@[simp]

theorem List.takeD_left {α : Type u} (l₁ : List α) (l₂ : List α) (a : α) : List.takeD (List.length l₁) (l₁ ++ l₂) a = l₁

ink

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

ink

theorem List.foldl_ext {α : Type u} {β : Type v} (f : α → β → α) (g : α → β → α) (a : α) {l : List β} (H : ∀ (a : α) (b : β), b ∈ l → f a b = g a b) : List.foldl f a l = List.foldl g a l

ink

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

ink

@[simp]

theorem List.foldl_nil {α : Type u} {β : Type v} (f : α → β → α) (a : α) : List.foldl f a [] = a

ink

@[simp]

theorem List.foldl_cons {α : Type u} {β : Type v} (f : α → β → α) (a : α) (b : β) (l : List β) : List.foldl f a (b :: l) = List.foldl f (f a b) l

ink

@[simp]

theorem List.foldr_nil {α : Type u} {β : Type v} (f : α → β → β) (b : β) : List.foldr f b [] = b

ink

@[simp]

theorem List.foldr_cons {α : Type u} {β : Type v} (f : α → β → β) (b : β) (a : α) (l : List α) : List.foldr f b (a :: l) = f a (List.foldr f b l)

ink

theorem List.foldl_fixed' {α : Type u} {β : Type v} {f : α → β → α} {a : α} (hf : ∀ (b : β), f a b = a) (l : List β) : List.foldl f a l = a

ink

theorem List.foldr_fixed' {α : Type u} {β : Type v} {f : α → β → β} {b : β} (hf : ∀ (a : α), f a b = b) (l : List α) : List.foldr f b l = b

ink

@[simp]

theorem List.foldl_fixed {α : Type u} {β : Type v} {a : α} (l : List β) : List.foldl (fun a x => a) a l = a

ink

@[simp]

theorem List.foldr_fixed {α : Type u} {β : Type v} {b : β} (l : List α) : List.foldr (fun x b => b) b l = b

ink

@[simp]

theorem List.foldl_join {α : Type u} {β : Type v} (f : α → β → α) (a : α) (L : List (List β)) : List.foldl f a (List.join L) = List.foldl (List.foldl f) a L

ink

@[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 b => List.foldr f b l) b L

ink

theorem List.foldr_eta {α : Type u} (l : List α) : List.foldr List.cons [] l = l

ink

@[simp]

theorem List.reverse_foldl {α : Type u} {l : List α} : List.reverse (List.foldl (fun t h => h :: t) [] l) = l

ink

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)

ink

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)

ink

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)

ink

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)

ink

theorem List.injective_foldl_comp {α : Type u_1} {l : List (α → α)} {f : α → α} (hl : ∀ (f : α → α), f ∈ l → Function.Injective f) (hf : Function.Injective f) : Function.Injective (List.foldl Function.comp f l)

ink

def List.foldrRecOn {α : Type u} {β : Type v} {C : β → Sort u_1} (l : List α) (op : α → β → β) (b : β) (hb : C b) (hl : (b : β) → C b → (a : α) → a ∈ l → C (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∈ 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.

ink

def List.foldlRecOn {α : Type u} {β : Type v} {C : β → Sort u_1} (l : List α) (op : β → α → β) (b : β) (hb : C b) (hl : (b : β) → C b → (a : α) → a ∈ l → C (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∈ 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.

ink

@[simp]

theorem List.foldrRecOn_nil {α : Type u} {β : Type v} {C : β → Sort u_1} (op : α → β → β) (b : β) (hb : C b) (hl : (b : β) → C b → (a : α) → a ∈ [] → C (op a b)) : List.foldrRecOn [] op b hb hl = hb

ink

@[simp]

theorem List.foldrRecOn_cons {α : Type u} {β : Type v} {C : β → Sort u_1} (x : α) (l : List α) (op : α → β → β) (b : β) (hb : C b) (hl : (b : β) → C b → (a : α) → a ∈ x :: l → C (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 a ha => hl b hb a (_ : a ∈ x :: l)) x (_ : x ∈ x :: l)

ink

@[simp]

theorem List.foldlRecOn_nil {α : Type u} {β : Type v} {C : β → Sort u_1} (op : β → α → β) (b : β) (hb : C b) (hl : (b : β) → C b → (a : α) → a ∈ [] → C (op b a)) : List.foldlRecOn [] op b hb hl = hb

ink

theorem List.length_scanl {α : Type u} {β : Type v} {f : β → α → β} (a : β) (l : List α) : List.length (List.scanl f a l) = List.length l + 1

ink

@[simp]

theorem List.scanl_nil {α : Type u} {β : Type v} {f : β → α → β} (b : β) : List.scanl f b [] = [b]

ink

@[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

ink

@[simp]

theorem List.get?_zero_scanl {α : Type u} {β : Type v} {f : β → α → β} {b : β} {l : List α} : List.get? (List.scanl f b l) 0 = some b

ink

@[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

ink

@[simp]

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

ink

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)

ink

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))

ink

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) })

ink

@[simp]

theorem List.scanr_nil {α : Type u} {β : Type v} (f : α → β → β) (b : β) : List.scanr f b [] = [b]

ink

@[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

ink

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)

ink

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)

ink

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

ink

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

ink

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

ink

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

ink

theorem List.foldl_assoc {α : Type u} {op : α → α → α} [ha : IsAssociative α op] {l : List α} {a₁ : α} {a₂ : α} : List.foldl op (op a₁ a₂) l = op a₁ (List.foldl op a₂ l)

ink

theorem List.foldl_op_eq_op_foldr_assoc {α : Type u} {op : α → α → α} [ha : IsAssociative α 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)

ink

theorem List.foldl_assoc_comm_cons {α : Type u} {op : α → α → α} [ha : IsAssociative α op] [hc : IsCommutative α op] {l : List α} {a₁ : α} {a₂ : α} : List.foldl op a₂ (a₁ :: l) = op a₁ (List.foldl op a₂ l)

foldlM, foldrM, mapM

ink

@[simp]

theorem List.foldlM_nil {α : Type u} {β : Type v} {m : Type v → Type w} [inst : Monad m] (f : β → α → m β) {b : β} : List.foldlM f b [] = pure b

ink

@[simp]

theorem List.foldlM_cons {α : Type u} {β : Type v} {m : Type v → Type w} [inst : Monad m] {f : β → α → m β} {b : β} {a : α} {l : List α} : List.foldlM f b (a :: l) = do let b' ← f b a List.foldlM f b' l

ink

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

ink

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

intersperse

ink

@[simp]

theorem List.intersperse_nil {α : Type u} (a : α) : List.intersperse a [] = []

ink

@[simp]

theorem List.intersperse_singleton {α : Type u} (a : α) (b : α) : List.intersperse a [b] = [b]

ink

@[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

ink

@[simp]

theorem List.splitAt_eq_take_drop {α : Type u} (n : ℕ) (l : List α) : List.splitAt n l = (List.take n l, List.drop n l)

ink

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

ink

@[simp]

theorem List.splitOn_nil {α : Type u} [inst : DecidableEq α] (a : α) : List.splitOn a [] = [[]]

ink

@[simp]

theorem List.splitOnP_nil {α : Type u} (p : α → Bool) : List.splitOnP p [] = [[]]

ink

theorem List.splitOnP.go_append {α : Type u} (p : α → Bool) (xs : List α) (acc : Array α) (r : Array (List α)) : List.splitOnP.go p xs acc r = Array.toListAppend r (List.splitOnP.go p xs acc #[])

ink

theorem List.splitOnP.go_acc {α : Type u} (p : α → Bool) (xs : List α) (acc : Array α) : List.splitOnP.go p xs acc #[] = List.modifyHead (Array.toListAppend acc) (List.splitOnP.go p xs #[] #[])

ink

theorem List.splitOnP_ne_nil {α : Type u} (p : α → Bool) (xs : List α) : List.splitOnP p xs ≠ []

ink

theorem List.splitOnP_ne_nil.modifyHead_ne_nil_of_ne_nil {α : Type u} {f : α → α} {l : List α} : l ≠ [] → List.modifyHead f l ≠ []

ink

@[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)

ink

theorem List.splitOnP_spec {α : Type u} (p : α → Bool) (as : List α) : List.join (List.zipWith (fun x x_1 => 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.

ink

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 => x ++ x_1) (List.modifyHead (List.cons a) xs) ys) = a :: List.join (List.zipWith (fun x x_1 => x ++ x_1) xs ys)

ink

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]

ink

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

ink

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

intercalate [x] is the left inverse of splitOn x

ink

theorem List.splitOn_intercalate {α : Type u} (ls : List (List α)) [inst : DecidableEq α] (x : α) (hx : ∀ (l : List α), l ∈ ls → ¬x ∈ l) (hls : ls ≠ []) : List.splitOn x (List.intercalate [x] 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

ink

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

ink

theorem List.modifyLast_append_one {α : Type u} (f : α → α) (a : α) (l : List α) : List.modifyLast f (l ++ [a]) = l ++ [f a]

ink

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

ink

def List.pmap {α : Type u} {β : Type v} {p : α → Prop} (f : (a : α) → p a → β) (l : List α) : ((a : α) → a ∈ l → p a) → List β

Partial map. If f : Π a, p a → β→ β is a partial function defined on a : α satisfying p, then pmap f l h is essentially the same as map f l but is defined only when all members of l satisfy p, using the proof to apply f.

Equations

• List.pmap f [] x_2 = []
• List.pmap f (a :: l) H = f a (_ : p a ∧ ((x : α) → x ∈ l → p x)).left :: List.pmap f l (_ : p a ∧ ((x : α) → x ∈ l → p x)).right

ink

def List.attach {α : Type u} (l : List α) : List { x // x ∈ l }

"Attach" the proof that the elements of l are in l to produce a new list with the same elements but in the type {x // x ∈ l}∈ l}.

Equations

• List.attach l = List.pmap Subtype.mk l (_ : ∀ (x : α), x ∈ l → x ∈ l)

ink

theorem List.sizeOf_lt_sizeOf_of_mem {α : Type u} [inst : SizeOf α] {x : α} {l : List α} (hx : x ∈ l) : sizeOf x < sizeOf l

ink

@[simp]

theorem List.pmap_eq_map {α : Type u} {β : Type v} (p : α → Prop) (f : α → β) (l : List α) (H : (a : α) → a ∈ l → p a) : List.pmap (fun a x => f a) l H = List.map f l

ink

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 ∈ l → p a} {H₂ : (a : α) → a ∈ l → q 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₂

ink

theorem List.map_pmap {α : Type u} {β : Type v} {γ : Type w} {p : α → Prop} (g : β → γ) (f : (a : α) → p a → β) (l : List α) (H : (a : α) → a ∈ l → p a) : List.map g (List.pmap f l H) = List.pmap (fun a h => g (f a h)) l H

ink

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 l → p a) : List.pmap g (List.map f l) H = List.pmap (fun a h => g (f a) h) l fun a h => H (f a) (_ : f a ∈ List.map f l)

ink

theorem List.pmap_eq_map_attach {α : Type u} {β : Type v} {p : α → Prop} (f : (a : α) → p a → β) (l : List α) (H : (a : α) → a ∈ l → p a) : List.pmap f l H = List.map (fun x => f (↑x) (H ↑x (_ : ↑x ∈ l))) (List.attach l)

ink

theorem List.attach_map_coe' {α : Type u} {β : Type v} (l : List α) (f : α → β) : List.map (fun i => f ↑i) (List.attach l) = List.map f l

ink

theorem List.attach_map_val' {α : Type u} {β : Type v} (l : List α) (f : α → β) : List.map (fun i => f ↑i) (List.attach l) = List.map f l

ink

@[simp]

theorem List.attach_map_val {α : Type u} (l : List α) : List.map Subtype.val (List.attach l) = l

ink

@[simp]

theorem List.mem_attach {α : Type u} (l : List α) (x : { x // x ∈ l }) : x ∈ List.attach l

ink

@[simp]

theorem List.mem_pmap {α : Type u} {β : Type v} {p : α → Prop} {f : (a : α) → p a → β} {l : List α} {H : (a : α) → a ∈ l → p a} {b : β} : b ∈ List.pmap f l H ↔ ∃ a h, f a (H a h) = b

ink

@[simp]

theorem List.length_pmap {α : Type u} {β : Type v} {p : α → Prop} {f : (a : α) → p a → β} {l : List α} {H : (a : α) → a ∈ l → p a} : List.length (List.pmap f l H) = List.length l

ink

@[simp]

theorem List.length_attach {α : Type u} (L : List α) : List.length (List.attach L) = List.length L

ink

@[simp]

theorem List.pmap_eq_nil {α : Type u} {β : Type v} {p : α → Prop} {f : (a : α) → p a → β} {l : List α} {H : (a : α) → a ∈ l → p a} : List.pmap f l H = [] ↔ l = []

ink

@[simp]

theorem List.attach_eq_nil {α : Type u} (l : List α) : List.attach l = [] ↔ l = []

ink

theorem List.getLast_pmap {α : Type u_1} {β : Type u_2} (p : α → Prop) (f : (a : α) → p a → β) (l : List α) (hl₁ : (a : α) → a ∈ l → p a) (hl₂ : l ≠ []) : List.getLast (List.pmap f l hl₁) (_ : ¬List.pmap f l hl₁ = []) = f (List.getLast l hl₂) (hl₁ (List.getLast l hl₂) (_ : List.getLast l hl₂ ∈ l))

ink

theorem List.get?_pmap {α : Type u} {β : Type v} {p : α → Prop} (f : (a : α) → p a → β) {l : List α} (h : (a : α) → a ∈ l → p a) (n : ℕ) : List.get? (List.pmap f l h) n = Option.pmap f (List.get? l n) fun x H => h x (_ : x ∈ l)

ink

theorem List.get_pmap {α : Type u} {β : Type v} {p : α → Prop} (f : (a : α) → p a → β) {l : List α} (h : (a : α) → a ∈ l → p 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) }) (h (List.get l { val := n, isLt := (_ : n < List.length l) }) (_ : List.get l { val := n, isLt := (_ : n < List.length l) } ∈ l))

ink

theorem List.nthLe_pmap {α : Type u} {β : Type v} {p : α → Prop} (f : (a : α) → p a → β) {l : List α} (h : (a : α) → a ∈ l → p 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)) (h (List.nthLe l n (_ : n < List.length l)) (_ : List.get l { val := n, isLt := (_ : n < List.length l) } ∈ l))

ink

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₁ fun a ha => h a (_ : a ∈ l₁ ++ l₂)) ++ List.pmap f l₂ fun a ha => h a (_ : a ∈ l₁ ++ l₂)

ink

theorem List.pmap_append' {α : Type u_1} {β : Type u_2} {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₂) fun a ha => Or.elim (_ : a ∈ l₁ ∨ a ∈ l₂) (h₁ a) (h₂ a)) = List.pmap f l₁ h₁ ++ List.pmap f l₂ h₂

find

ink

@[simp]

theorem List.find?_nil {α : Type u} (p : α → Bool) : List.find? p [] = none

ink

@[simp]

theorem List.find?_cons_of_pos {α : Type u} {p : α → Bool} {a : α} (l : List α) (h : p a = true) : List.find? p (a :: l) = some a

ink

@[simp]

theorem List.find?_cons_of_neg {α : Type u} {p : α → Bool} {a : α} (l : List α) (h : ¬p a = true) : List.find? p (a :: l) = List.find? p l

ink

@[simp]

theorem List.find?_eq_none {α : Type u} {p : α → Bool} {l : List α} : List.find? p l = none ↔ ∀ (x : α), x ∈ l → ¬p x = true

ink

theorem List.find?_some {α : Type u} {p : α → Bool} {l : List α} {a : α} (H : List.find? p l = some a) : p a = true

ink

@[simp]

theorem List.find?_mem {α : Type u} {p : α → Bool} {l : List α} {a : α} (H : List.find? p l = some a) : a ∈ l

lookmap

ink

theorem List.lookmap.go_append {α : Type u} (f : α → Option α) (l : List α) (acc : Array α) : List.lookmap.go f l acc = Array.toListAppend acc (List.lookmap f l)

ink

@[simp]

theorem List.lookmap_nil {α : Type u} (f : α → Option α) : List.lookmap f [] = []

ink

@[simp]

theorem List.lookmap_cons_none {α : Type u} (f : α → Option α) {a : α} (l : List α) (h : f a = none) : List.lookmap f (a :: l) = a :: List.lookmap f l

ink

@[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

ink

theorem List.lookmap_some {α : Type u} (l : List α) : List.lookmap some l = l

ink

theorem List.lookmap_none {α : Type u} (l : List α) : List.lookmap (fun x => none) l = l

ink

theorem List.lookmap_congr {α : Type u} {f : α → Option α} {g : α → Option α} {l : List α} : (∀ (a : α), a ∈ l → f a = g a) → List.lookmap f l = List.lookmap g l

ink

theorem List.lookmap_of_forall_not {α : Type u} (f : α → Option α) {l : List α} (H : ∀ (a : α), a