The following functions can't be defined at Init.Data.List.Basic, because they depend on Init.Util, and Init.Util depends on Init.Data.List.Basic.

Alternative getters

get?

@[deprecated "Use `a[i]?` instead." (since := "2025-02-12")]

def List.get? {α : Type u_1} (as : List α) (i : Nat) : Option α

Returns the i-th element in the list (zero-based).

If the index is out of bounds (i ≥ as.length), this function returns none. Also see get, getD and get!.

Equations

• (a :: tail).get? 0 = some a
• (head :: as).get? n.succ = as.get? n
• x✝¹.get? x✝ = none

@[simp, deprecated "Use `a[i]?` instead." (since := "2025-02-12")]

theorem List.get?_nil {α : Type u_1} {n : Nat} : [].get? n = none

@[simp, deprecated "Use `a[i]?` instead." (since := "2025-02-12")]

theorem List.get?_cons_zero {α : Type u_1} {a : α} {l : List α} : (a :: l).get? 0 = some a

@[simp, deprecated "Use `a[i]?` instead." (since := "2025-02-12")]

theorem List.get?_cons_succ {α : Type u_1} {a : α} {l : List α} {n : Nat} : (a :: l).get? (n + 1) = l.get? n

@[deprecated "Use `List.ext_getElem?`." (since := "2025-02-12")]

theorem List.ext_get? {α : Type u_1} {l₁ l₂ : List α} : (∀ (n : Nat), l₁.get? n = l₂.get? n) → l₁ = l₂

get!

@[deprecated "Use `a[i]!` instead." (since := "2025-02-12")]

def List.get! {α : Type u_1} [Inhabited α] (as : List α) (i : Nat) : α

Returns the i-th element in the list (zero-based).

If the index is out of bounds (i ≥ as.length), this function panics when executed, and returns default. See get? and getD for safer alternatives.

Equations

• (a :: tail).get! 0 = a
• (head :: as).get! n.succ = as.get! n
• x✝¹.get! x✝ = panicWithPosWithDecl "Init.Data.List.BasicAux" "List.get!" 66 18 "invalid index"

@[deprecated "Use `a[i]!` instead." (since := "2025-02-12")]

theorem List.get!_nil {α : Type u_1} [Inhabited α] (n : Nat) : [].get! n = default

@[deprecated "Use `a[i]!` instead." (since := "2025-02-12")]

theorem List.get!_cons_succ {α : Type u_1} [Inhabited α] (l : List α) (a : α) (n : Nat) : (a :: l).get! (n + 1) = l.get! n

@[deprecated "Use `a[i]!` instead." (since := "2025-02-12")]

theorem List.get!_cons_zero {α : Type u_1} [Inhabited α] (l : List α) (a : α) : (a :: l).get! 0 = a

getD

def List.getD {α : Type u_1} (as : List α) (i : Nat) (fallback : α) : α

Returns the i-th element in the list (zero-based).

If the index is out of bounds (i ≥ as.length), this function returns fallback. See also get? and get!.

Equations

• as.getD i fallback = as[i]?.getD fallback

@[simp]

theorem List.getD_nil {n : Nat} {α✝ : Type u_1} {d : α✝} : [].getD n d = d

getLast!

def List.getLast! {α : Type u_1} [Inhabited α] : List α → α

Returns the last element in the list.

If the list is empty, this function panics when executed, and returns default. See getLast and getLastD for safer alternatives.

Equations

• [].getLast! = panicWithPosWithDecl "Init.Data.List.BasicAux" "List.getLast!" 101 13 "empty list"
• (a :: as).getLast! = (a :: as).getLast ⋯

Head and tail

head!

def List.head! {α : Type u_1} [Inhabited α] : List α → α

Returns the first element in the list.

If the list is empty, this function panics when executed, and returns default. See head and headD for safer alternatives.

Equations

• [].head! = panicWithPosWithDecl "Init.Data.List.BasicAux" "List.head!" 115 12 "empty list"
• (a :: as).head! = a

tail!

def List.tail! {α : Type u_1} : List α → List α

Drops the first element of the list.

If the list is empty, this function panics when executed, and returns the empty list. See tail and tailD for safer alternatives.

Equations

• [].tail! = panicWithPosWithDecl "Init.Data.List.BasicAux" "List.tail!" 127 13 "empty list"
• (a :: as).tail! = as

@[simp]

theorem List.tail!_cons {α : Type u_1} {a : α} {l : List α} : (a :: l).tail! = l

partitionM

@[inline]

def List.partitionM {m : Type → Type u_1} {α : Type} [Monad m] (p : α → m Bool) (l : List α) : m (List α × List α)

Monadic generalization of List.partition.

This uses Array.toList and which isn't imported by Init.Data.List.Basic or Init.Data.List.Control.

def posOrNeg (x : Int) : Except String Bool :=
  if x > 0 then pure true
  else if x < 0 then pure false
  else throw "Zero is not positive or negative"

partitionM posOrNeg [-1, 2, 3] = Except.ok ([2, 3], [-1])
partitionM posOrNeg [0, 2, 3] = Except.error "Zero is not positive or negative"

Equations

• List.partitionM p l = List.partitionM.go p l #[] #[]

@[specialize #[]]

def List.partitionM.go {m : Type → Type u_1} {α : Type} [Monad m] (p : α → m Bool) : List α → Array α → Array α → m (List α × List α)

Auxiliary for partitionM: partitionM.go p l acc₁ acc₂ returns (acc₁.toList ++ left, acc₂.toList ++ right) if partitionM p l returns (left, right).

Equations

• List.partitionM.go p [] x✝¹ x✝ = pure (x✝¹.toList, x✝.toList)
• List.partitionM.go p (x_3 :: xs) x✝¹ x✝ = do let __do_lift ← p x_3 if __do_lift = true then List.partitionM.go p xs (x✝¹.push x_3) x✝ else List.partitionM.go p xs x✝¹ (x✝.push x_3)

partitionMap

@[inline]

def List.partitionMap {α : Type u_1} {β : Type u_2} {γ : Type u_3} (f : α → β ⊕ γ) (l : List α) : List β × List γ

Given a function f : α → β ⊕ γ, partitionMap f l maps the list by f whilst partitioning the result into a pair of lists, List β × List γ, partitioning the .inl _ into the left list, and the .inr _ into the right List.

partitionMap (id : Nat ⊕ Nat → Nat ⊕ Nat) [inl 0, inr 1, inl 2] = ([0, 2], [1])

Equations

• List.partitionMap f l = List.partitionMap.go f l #[] #[]

@[specialize #[]]

def List.partitionMap.go {α : Type u_1} {β : Type u_2} {γ : Type u_3} (f : α → β ⊕ γ) : List α → Array β → Array γ → List β × List γ

Auxiliary for partitionMap: partitionMap.go f l acc₁ acc₂ = (acc₁.toList ++ left, acc₂.toList ++ right) if partitionMap f l = (left, right).

Equations

• List.partitionMap.go f [] x✝¹ x✝ = (x✝¹.toList, x✝.toList)
• List.partitionMap.go f (x_3 :: xs) x✝¹ x✝ = match f x_3 with | Sum.inl a => List.partitionMap.go f xs (x✝¹.push a) x✝ | Sum.inr b => List.partitionMap.go f xs x✝¹ (x✝.push b)

mapMono

This is a performance optimization for List.mapM that avoids allocating a new list when the result of each f a is a pointer equal value a.

For verification purposes, List.mapMono = List.map.

@[implemented_by _private.Init.Data.List.BasicAux.0.List.mapMonoMImp]

def List.mapMonoM {m : Type u_1 → Type u_2} {α : Type u_1} [Monad m] (as : List α) (f : α → m α) : m (List α)

Monomorphic List.mapM. The internal implementation uses pointer equality, and does not allocate a new list if the result of each f a is a pointer equal value a.

Equations

• [].mapMonoM f = pure []
• (a :: as_1).mapMonoM f = do let __do_lift ← f a let __do_lift_1 ← as_1.mapMonoM f pure (__do_lift :: __do_lift_1)

def List.mapMono {α : Type u_1} (as : List α) (f : α → α) : List α

Equations

• as.mapMono f = (as.mapMonoM f).run

Additional lemmas required for bootstrapping Array.

@[simp]

theorem List.getElem_append_left {α : Type u_1} {i : Nat} {as bs : List α} (h : i < as.length) {h' : i < (as ++ bs).length} : (as ++ bs)[i] = as[i]

@[simp]

theorem List.getElem_append_right {α : Type u_1} {as bs : List α} {i : Nat} (h₁ : as.length ≤ i) {h₂ : i < (as ++ bs).length} : (as ++ bs)[i] = bs[i - as.length]

@[deprecated "Deprecated without replacement." (since := "2025-02-13")]

theorem List.get_last {α : Type u_1} {a : α} {as : List α} {i : Fin (as ++ [a]).length} (h : ¬↑i < as.length) : (as ++ [a]).get i = a

theorem List.sizeOf_lt_of_mem {α : Type u_1} {a : α} [SizeOf α] {as : List α} (h : a ∈ as) : sizeOf a < sizeOf as

def List.tacticSizeOf_list_dec : Lean.ParserDescr

This tactic, added to the decreasing_trivial toolbox, proves that sizeOf a < sizeOf as when a ∈ as, which is useful for well founded recursions over a nested inductive like inductive T | mk : List T → T.

Equations

• List.tacticSizeOf_list_dec = Lean.ParserDescr.node `List.tacticSizeOf_list_dec 1024 (Lean.ParserDescr.nonReservedSymbol "sizeOf_list_dec" false)

theorem List.append_cancel_left {α : Type u_1} {as bs cs : List α} (h : as ++ bs = as ++ cs) : bs = cs

theorem List.append_cancel_right {α : Type u_1} {as bs cs : List α} (h : as ++ bs = cs ++ bs) : as = cs

@[simp]

theorem List.append_cancel_left_eq {α : Type u_1} (as bs cs : List α) : (as ++ bs = as ++ cs) = (bs = cs)

@[simp]

theorem List.append_cancel_right_eq {α : Type u_1} (as bs cs : List α) : (as ++ bs = cs ++ bs) = (as = cs)

theorem List.sizeOf_get {α : Type u_1} [SizeOf α] (as : List α) (i : Fin as.length) : sizeOf (as.get i) < sizeOf as

theorem List.not_lex_antisymm {α : Type u_1} [DecidableEq α] {r : α → α → Prop} [DecidableRel r] (antisymm : ∀ (x y : α), ¬r x y → ¬r y x → x = y) {as bs : List α} (h₁ : ¬Lex r bs as) (h₂ : ¬Lex r as bs) : as = bs

theorem List.le_antisymm {α : Type u_1} [DecidableEq α] [LT α] [DecidableLT α] [i : Std.Antisymm fun (x1 x2 : α) => ¬x1 < x2] {as bs : List α} (h₁ : as ≤ bs) (h₂ : bs ≤ as) : as = bs

instance List.instAntisymmLeOfDecidableEqOfDecidableLTOfNotLt {α : Type u_1} [DecidableEq α] [LT α] [DecidableLT α] [s : Std.Antisymm fun (x1 x2 : α) => ¬x1 < x2] : Std.Antisymm fun (x1 x2 : List α) => x1 ≤ x2