Auxiliary for `List.reverse`

. `List.reverseAux l r = l.reverse ++ r`

, but it is defined directly.

## Equations

- List.reverseAux [] x = x
- List.reverseAux (a :: l) x = List.reverseAux l (a :: x)

`O(|as|)`

. Reverse of a list:

`[1, 2, 3, 4].reverse = [4, 3, 2, 1]`

Note that because of the "functional but in place" optimization implemented by Lean's compiler, this function works without any allocations provided that the input list is unshared: it simply walks the linked list and reverses all the node pointers.

## Equations

- List.reverse as = List.reverseAux as []

`O(|xs|)`

: append two lists. `[1, 2, 3] ++ [4, 5] = [1, 2, 3, 4, 5]`

.
It takes time proportional to the first list.

## Equations

- List.append [] x = x
- List.append (a :: l) x = a :: List.append l x

Tail-recursive version of `List.append`

.

## Equations

- List.appendTR as bs = List.reverseAux (List.reverse as) bs

## Equations

- List.instEmptyCollectionList = { emptyCollection := [] }

`O(|l|)`

. `erase l a`

removes the first occurrence of `a`

from `l`

.

## Equations

- List.erase [] x = []
- List.erase (a :: as) x = match a == x with | true => as | false => a :: List.erase as x

`O(i)`

. `eraseIdx l i`

removes the `i`

'th element of the list `l`

.

`erase [a, b, c, d, e] 0 = [b, c, d, e]`

`erase [a, b, c, d, e] 1 = [a, c, d, e]`

`erase [a, b, c, d, e] 5 = [a, b, c, d, e]`

## Equations

- List.eraseIdx [] x = []
- List.eraseIdx (head :: as) 0 = as
- List.eraseIdx (a :: as) (Nat.succ n) = a :: List.eraseIdx as n

## Equations

- List.mapTR.loop f [] x = List.reverse x
- List.mapTR.loop f (a :: as) x = List.mapTR.loop f as (f a :: x)

`O(|l|)`

. `filterMap f l`

takes a function `f : α → Option β`

and applies it to each element of `l`

;
the resulting non-`none`

values are collected to form the output list.

```
filterMap
(fun x => if x > 2 then some (2 * x) else none)
[1, 2, 5, 2, 7, 7]
= [10, 14, 14]
```

## Equations

- List.filterMap f [] = []
- List.filterMap f (head :: tail) = match f head with | none => List.filterMap f tail | some b => b :: List.filterMap f tail

`O(|l|)`

. `filter f l`

returns the list of elements in `l`

for which `f`

returns true.

```
filter (· > 2) [1, 2, 5, 2, 7, 7] = [5, 7, 7]
```

## Equations

- List.filter p [] = []
- List.filter p (head :: tail) = match p head with | true => head :: List.filter p tail | false => List.filter p tail

Tail-recursive version of `List.filter`

.

## Equations

- List.filterTR p as = List.filterTR.loop p as []

## Equations

- List.filterTR.loop p [] x = List.reverse x
- List.filterTR.loop p (a :: l) x = match p a with | true => List.filterTR.loop p l (a :: x) | false => List.filterTR.loop p l x

`O(|l|)`

. `partition p l`

calls `p`

on each element of `l`

, partitioning the list into two lists
`(l_true, l_false)`

where `l_true`

has the elements where `p`

was true
and `l_false`

has the elements where `p`

is false.
`partition p l = (filter p l, filter (not ∘ p) l)`

, but it is slightly more efficient
since it only has to do one pass over the list.

```
partition (· > 2) [1, 2, 5, 2, 7, 7] = ([5, 7, 7], [1, 2, 2])
```

## Equations

- List.partition p as = List.partition.loop p as ([], [])

## Equations

- List.partition.loop p [] (bs, cs) = (List.reverse bs, List.reverse cs)
- List.partition.loop p (a :: as) (bs, cs) = match p a with | true => List.partition.loop p as (a :: bs, cs) | false => List.partition.loop p as (bs, a :: cs)

`O(|l|)`

. `dropWhile p l`

removes elements from the list until it finds the first element
for which `p`

returns false; this element and everything after it is returned.

```
dropWhile (· < 4) [1, 3, 2, 4, 2, 7, 4] = [4, 2, 7, 4]
```

## Equations

- List.dropWhile p [] = []
- List.dropWhile p (head :: tail) = match p head with | true => List.dropWhile p tail | false => head :: tail

`O(|l|)`

. `find? p l`

returns the first element for which `p`

returns true,
or `none`

if no such element is found.

## Equations

- List.find? p [] = none
- List.find? p (head :: tail) = match p head with | true => some head | false => List.find? p tail

`O(|l|)`

. `findSome? f l`

applies `f`

to each element of `l`

, and returns the first non-`none`

result.

`findSome? (fun x => if x < 5 then some (10 * x) else none) [7, 6, 5, 8, 1, 2, 6] = some 10`

## Equations

- List.findSome? f [] = none
- List.findSome? f (head :: tail) = match f head with | some b => some b | none => List.findSome? f tail

`O(|l|)`

. `replace l a b`

replaces the first element in the list equal to `a`

with `b`

.

`replace [1, 4, 2, 3, 3, 7] 3 6 = [1, 4, 2, 6, 3, 7]`

`replace [1, 4, 2, 3, 3, 7] 5 6 = [1, 4, 2, 3, 3, 7]`

## Equations

- List.replace [] x x = []
- List.replace (a :: as) x x = match a == x with | true => x :: as | false => a :: List.replace as x x

- head: ∀ {α : Type u} {a : α} (as : List α), List.Mem a (a :: as)
The head of a list is a member:

`a ∈ a :: as`

. - tail: ∀ {α : Type u} {a : α} (b : α) {as : List α}, List.Mem a as → List.Mem a (b :: as)
A member of the tail of a list is a member of the list:

`a ∈ l → a ∈ b :: l`

.

`a ∈ l`

is a predicate which asserts that `a`

is in the list `l`

.
Unlike `elem`

, this uses `=`

instead of `==`

and is suited for mathematical reasoning.

`a ∈ [x, y, z] ↔ a = x ∨ a = y ∨ a = z`

## Instances For

## Equations

- List.instMembershipList = { mem := List.Mem }

## Equations

- List.instDecidableMemListInstMembershipList a as = decidable_of_decidable_of_iff (_ : List.elem a as = true ↔ a ∈ as)

`O(|l|^2)`

. Erase duplicated elements in the list.
Keeps the first occurrence of duplicated elements.

`eraseDups [1, 3, 2, 2, 3, 5] = [1, 3, 2, 5]`

## Equations

- List.eraseDups as = List.eraseDups.loop as []

## Equations

- List.eraseDups.loop [] x = List.reverse x
- List.eraseDups.loop (a :: l) x = match List.elem a x with | true => List.eraseDups.loop l x | false => List.eraseDups.loop l (a :: x)

`O(|l|)`

. Erase repeated adjacent elements. Keeps the first occurrence of each run.

`eraseReps [1, 3, 2, 2, 2, 3, 5] = [1, 3, 2, 3, 5]`

## Equations

- List.eraseReps x = match x with | [] => [] | a :: as => List.eraseReps.loop a as []

## Equations

- List.eraseReps.loop x [] x = List.reverse (x :: x)
- List.eraseReps.loop x (a' :: as) x = match x == a' with | true => List.eraseReps.loop x as x | false => List.eraseReps.loop a' as (x :: x)

`O(|l|)`

. `span p l`

splits the list `l`

into two parts, where the first part
contains the longest initial segment for which `p`

returns true
and the second part is everything else.

`span (· > 5) [6, 8, 9, 5, 2, 9] = ([6, 8, 9], [5, 2, 9])`

`span (· > 10) [6, 8, 9, 5, 2, 9] = ([6, 8, 9, 5, 2, 9], [])`

## Equations

- List.span p as = List.span.loop p as []

## Equations

- List.span.loop p [] x = (List.reverse x, [])
- List.span.loop p (a :: l) x = match p a with | true => List.span.loop p l (a :: x) | false => (List.reverse x, a :: l)

`O(|l|)`

. `groupBy R l`

splits `l`

into chains of elements
such that adjacent elements are related by `R`

.

`groupBy (·==·) [1, 1, 2, 2, 2, 3, 2] = [[1, 1], [2, 2, 2], [3], [2]]`

`groupBy (·<·) [1, 2, 5, 4, 5, 1, 4] = [[1, 2, 5], [4, 5], [1, 4]]`

## Equations

- List.groupBy R x = match x with | [] => [] | a :: as => List.groupBy.loop R as a [] []

## Equations

- List.groupBy.loop R (a :: as) x x x = match R x a with | true => List.groupBy.loop R as a (x :: x) x | false => List.groupBy.loop R as a [] (List.reverse (x :: x) :: x)
- List.groupBy.loop R [] x x x = List.reverse (List.reverse (x :: x) :: x)

`O(|l|)`

. `lookup a l`

treats `l : List (α × β)`

like an association list,
and returns the first `β`

value corresponding to an `α`

value in the list equal to `a`

.

## Equations

- List.lookup x [] = none
- List.lookup x ((k, b) :: es) = match x == k with | true => some b | false => List.lookup x es

`O(|xs|)`

. Computes the "set difference" of lists,
by filtering out all elements of `xs`

which are also in `ys`

.

`removeAll [1, 1, 5, 1, 2, 4, 5] [1, 2, 2] = [5, 4, 5]`

## Equations

- List.removeAll xs ys = List.filter (fun x => List.notElem x ys) xs

`O(min n |xs|)`

. Removes the first `n`

elements of `xs`

.

`O(min n |xs|)`

. Returns the first `n`

elements of `xs`

, or the whole list if `n`

is too large.

`O(|xs|)`

. Returns the longest initial segment of `xs`

for which `p`

returns true.

## Equations

- List.takeWhile p [] = []
- List.takeWhile p (head :: tail) = match p head with | true => head :: List.takeWhile p tail | false => []

`O(|l|)`

. Applies function `f`

to all of the elements of the list, from right to left.

`foldr f init [a, b, c] = f a <| f b <| f c <| init`

## Equations

- List.foldr f init [] = init
- List.foldr f init (head :: tail) = f head (List.foldr f init tail)

`O(min |xs| |ys|)`

. Applies `f`

to the two lists in parallel, stopping at the shorter list.

`zipWith f [x₁, x₂, x₃] [y₁, y₂, y₃, y₄] = [f x₁ y₁, f x₂ y₂, f x₃ y₃]`

## Equations

- List.zipWith f (x_2 :: xs) (y :: ys) = f x_2 y :: List.zipWith f xs ys
- List.zipWith f x x = []

`O(min |xs| |ys|)`

. Combines the two lists into a list of pairs, with one element from each list.
The longer list is truncated to match the shorter list.

`zip [x₁, x₂, x₃] [y₁, y₂, y₃, y₄] = [(x₁, y₁), (x₂, y₂), (x₃, y₃)]`

## Equations

- List.zip = List.zipWith Prod.mk

`O(|l|)`

. Separates a list of pairs into two lists containing the first components and second components.

`unzip [(x₁, y₁), (x₂, y₂), (x₃, y₃)] = ([x₁, x₂, x₃], [y₁, y₂, y₃])`

## Equations

- List.unzip [] = ([], [])
- List.unzip ((a, b) :: t) = match List.unzip t with | (al, bl) => (a :: al, b :: bl)

`O(n)`

. `range n`

is the numbers from `0`

to `n`

exclusive, in increasing order.

`range 5 = [0, 1, 2, 3, 4]`

## Equations

- List.range n = List.range.loop n []

## Equations

- List.range.loop 0 x = x
- List.range.loop (Nat.succ n) x = List.range.loop n (n :: x)

Tail-recursive version of `iota`

.

## Equations

- List.iotaTR n = List.iotaTR.go n []

## Equations

- List.iotaTR.go 0 x = List.reverse x
- List.iotaTR.go (Nat.succ n) x = List.iotaTR.go n (Nat.succ n :: x)

`O(|l|)`

. `enumFrom n l`

is like `enum`

but it allows you to specify the initial index.

`enumFrom 5 [a, b, c] = [(5, a), (6, b), (7, c)]`

## Equations

- List.enumFrom x [] = []
- List.enumFrom x (x_2 :: xs) = (x, x_2) :: List.enumFrom (x + 1) xs

`O(|l|)`

. `intersperse sep l`

alternates `sep`

and the elements of `l`

:

`intersperse sep [] = []`

`intersperse sep [a] = [a]`

`intersperse sep [a, b] = [a, sep, b]`

`intersperse sep [a, b, c] = [a, sep, b, sep, c]`

## Equations

- List.intersperse sep [] = []
- List.intersperse sep [x_1] = [x_1]
- List.intersperse sep (x_1 :: xs) = x_1 :: sep :: List.intersperse sep xs

`O(|xs|)`

. `intercalate sep xs`

alternates `sep`

and the elements of `xs`

:

`intercalate sep [] = []`

`intercalate sep [a] = a`

`intercalate sep [a, b] = a ++ sep ++ b`

`intercalate sep [a, b, c] = a ++ sep ++ b ++ sep ++ c`

## Equations

- List.intercalate sep xs = List.join (List.intersperse sep xs)

`bind xs f`

is the bind operation of the list monad. It applies `f`

to each element of `xs`

to get a list of lists, and then concatenates them all together.

- nil: ∀ {α : Type u} [inst : LT α] (b : α) (bs : List α), List.lt [] (b :: bs)
`[]`

is the smallest element in the order. - head: ∀ {α : Type u} [inst : LT α] {a : α} (as : List α) {b : α} (bs : List α), a < b → List.lt (a :: as) (b :: bs)
If

`a < b`

then`a::as < b::bs`

. - tail: ∀ {α : Type u} [inst : LT α] {a : α} {as : List α} {b : α} {bs : List α}, ¬a < b → ¬b < a → List.lt as bs → List.lt (a :: as) (b :: bs)
If

`a`

and`b`

are equivalent and`as < bs`

, then`a::as < b::bs`

.

The lexicographic order on lists.
`[] < a::as`

, and `a::as < b::bs`

if `a < b`

or if `a`

and `b`

are equivalent and `as < bs`

.

## Instances For

## Equations

`isPrefixOf l₁ l₂`

returns `true`

Iff `l₁`

is a prefix of `l₂`

.
That is, there exists a `t`

such that `l₂ == l₁ ++ t`

.

## Equations

- List.isPrefixOf [] x = true
- List.isPrefixOf x [] = false
- List.isPrefixOf (a :: as) (b :: bs) = (a == b && List.isPrefixOf as bs)

`isPrefixOf? l₁ l₂`

returns `some t`

when `l₂ == l₁ ++ t`

.

## Equations

- List.isPrefixOf? [] x = some x
- List.isPrefixOf? x [] = none
- List.isPrefixOf? (a :: as) (b :: bs) = if (a == b) = true then List.isPrefixOf? as bs else none

`isSuffixOf l₁ l₂`

returns `true`

Iff `l₁`

is a suffix of `l₂`

.
That is, there exists a `t`

such that `l₂ == t ++ l₁`

.

## Equations

- List.isSuffixOf l₁ l₂ = List.isPrefixOf (List.reverse l₁) (List.reverse l₂)

`isSuffixOf? l₁ l₂`

returns `some t`

when `l₂ == t ++ l₁`

.

## Equations

- List.isSuffixOf? l₁ l₂ = Option.map List.reverse (List.isPrefixOf? (List.reverse l₁) (List.reverse l₂))

`O(min |as| |bs|)`

. Returns true if `as`

and `bs`

have the same length,
and they are pairwise related by `eqv`

.

## Equations

- List.isEqv [] [] x = true
- List.isEqv (a :: as) (b :: bs) x = (x a b && List.isEqv as bs x)
- List.isEqv x x x = false

`replicate n a`

is `n`

copies of `a`

:

`replicate 5 a = [a, a, a, a, a]`

## Equations

- List.replicate 0 x = []
- List.replicate (Nat.succ n) x = x :: List.replicate n x

Tail-recursive version of `List.replicate`

.

## Equations

- List.replicateTR n a = List.replicateTR.loop a n []

## Equations

- List.replicateTR.loop a 0 x = x
- List.replicateTR.loop a (Nat.succ n) x = List.replicateTR.loop a n (a :: x)

Removes the last element of the list.

## Equations

- List.dropLast [] = []
- List.dropLast [x_1] = []
- List.dropLast (x_1 :: xs) = x_1 :: List.dropLast xs

Returns the largest element of the list, if it is not empty.

## Equations

- List.maximum? x = match x with | [] => none | a :: as => some (List.foldl max a as)

Returns the smallest element of the list, if it is not empty.

## Equations

- List.minimum? x = match x with | [] => none | a :: as => some (List.foldl min a as)