New definitions

def List.bagInter {α : Type u_1} [BEq α] : List α → List α → List α

Computes the "bag intersection" of l₁ and l₂, that is, the collection of elements of l₁ which are also in l₂. As each element is identified, it is removed from l₂, so elements are counted with multiplicity.

Equations

• [].bagInter x = []
• x.bagInter [] = []
• (a :: l₁).bagInter x = if List.elem a x = true then a :: l₁.bagInter (x.erase a) else l₁.bagInter x

def List.diff {α : Type u_1} [BEq α] : List α → List α → List α

Computes the difference of l₁ and l₂, by removing each element in l₂ from l₁.

Equations

• x.diff [] = x
• x.diff (a :: l₂) = if List.elem a x = true then (x.erase a).diff l₂ else x.diff l₂

@[inline]

def List.next? {α : Type u_1} : List α → Option (α × List α)

Get the head and tail of a list, if it is nonempty.

Equations

• x.next? = match x with | [] => none | a :: l => some (a, l)

@[inline]

def List.mapIdx {α : Type u_1} {β : Type u_2} (f : Nat → α → β) (as : List α) : List β

Given a function f : Nat → α → β and as : list α, as = [a₀, a₁, ...], returns the list [f 0 a₀, f 1 a₁, ...].

Equations

• List.mapIdx f as = List.mapIdx.go f as #[]

@[specialize #[]]

def List.mapIdx.go {α : Type u_1} {β : Type u_2} (f : Nat → α → β) : List α → Array β → List β

Auxiliary for mapIdx: mapIdx.go [a₀, a₁, ...] acc = acc.toList ++ [f acc.size a₀, f (acc.size + 1) a₁, ...]

Equations

• List.mapIdx.go f [] x = x.toList
• List.mapIdx.go f (a :: as) x = List.mapIdx.go f as (x.push (f x.size a))

@[inline]

def List.mapIdxM {α : Type u_1} {β : Type v} {m : Type v → Type w} [Monad m] (as : List α) (f : Nat → α → m β) : m (List β)

Monadic variant of mapIdx.

Equations

• as.mapIdxM f = List.mapIdxM.go f as #[]

@[specialize #[]]

def List.mapIdxM.go {α : Type u_1} {β : Type v} {m : Type v → Type w} [Monad m] (f : Nat → α → m β) : List α → Array β → m (List β)

Auxiliary for mapIdxM: mapIdxM.go as f acc = acc.toList ++ [← f acc.size a₀, ← f (acc.size + 1) a₁, ...]

Equations

• List.mapIdxM.go f [] x = pure x.toList
• List.mapIdxM.go f (a :: as) x = do let __do_lift ← f x.size a List.mapIdxM.go f as (x.push __do_lift)

@[specialize #[]]

def List.after {α : Type u_1} (p : α → Bool) : List α → List α

after p xs is the suffix of xs after the first element that satisfies p, not including that element.

after      (· == 1) [0, 1, 2, 3] = [2, 3]
drop_while (· != 1) [0, 1, 2, 3] = [1, 2, 3]

Equations

• List.after p [] = []
• List.after p (a :: l) = bif p a then l else List.after p l

@[deprecated List.eraseIdx]

def List.removeNth {α : Type u} : List α → Nat → List α

Alias of List.eraseIdx.

---

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.removeNth = @List.eraseIdx

@[deprecated List.eraseIdxTR]

def List.removeNthTR {α : Type u_1} (l : List α) (n : Nat) : List α

Alias of List.eraseIdxTR.

---

Tail recursive version of List.eraseIdx.

Equations

• @List.removeNthTR = @List.eraseIdxTR

@[deprecated List.eraseIdx_eq_eraseIdxTR]

theorem List.removeNth_eq_removeNthTR : @List.eraseIdx = @List.eraseIdxTR

Alias of List.eraseIdx_eq_eraseIdxTR.

def List.replaceF {α : Type u_1} (f : α → Option α) : List α → List α

Replaces the first element of the list for which f returns some with the returned value.

Equations

• List.replaceF f [] = []
• List.replaceF f (a :: l) = match f a with | none => a :: List.replaceF f l | some a => a :: l

@[inline]

def List.replaceFTR {α : Type u_1} (f : α → Option α) (l : List α) : List α

Tail-recursive version of replaceF.

Equations

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

@[specialize #[]]

def List.replaceFTR.go {α : Type u_1} (f : α → Option α) : List α → Array α → List α

Auxiliary for replaceFTR: replaceFTR.go f xs acc = acc.toList ++ replaceF f xs.

Equations

• List.replaceFTR.go f [] x = x.toList
• List.replaceFTR.go f (x_2 :: xs) x = match f x_2 with | none => List.replaceFTR.go f xs (x.push x_2) | some a' => x.toListAppend (a' :: xs)

@[csimp]

theorem List.replaceF_eq_replaceFTR : @List.replaceF = @List.replaceFTR

theorem List.replaceF_eq_replaceFTR.go (α : Type u_1) (p : α → Option α) (acc : Array α) (xs : List α) : List.replaceFTR.go p xs acc = acc.data ++ List.replaceF p xs

@[inline]

def List.union {α : Type u_1} [BEq α] (l₁ : List α) (l₂ : List α) : List α

Constructs the union of two lists, by inserting the elements of l₁ in reverse order to l₂. As a result, l₂ will always be a suffix, but only the last occurrence of each element in l₁ will be retained (but order will otherwise be preserved).

Equations

• l₁.union l₂ = List.foldr List.insert l₂ l₁

instance List.instUnionOfBEq_batteries {α : Type u_1} [BEq α] : Union (List α)

Equations

• List.instUnionOfBEq_batteries = { union := List.union }

@[inline]

def List.inter {α : Type u_1} [BEq α] (l₁ : List α) (l₂ : List α) : List α

Constructs the intersection of two lists, by filtering the elements of l₁ that are in l₂. Unlike bagInter this does not preserve multiplicity: [1, 1].inter [1] is [1, 1].

Equations

• l₁.inter l₂ = List.filter (fun (x : α) => List.elem x l₂) l₁

instance List.instInterOfBEq_batteries {α : Type u_1} [BEq α] : Inter (List α)

Equations

• List.instInterOfBEq_batteries = { inter := List.inter }

def List.splitAt {α : Type u_1} (n : Nat) (l : List α) : List α × List α

Split a list at an index.

splitAt 2 [a, b, c] = ([a, b], [c])

Equations

• List.splitAt n l = List.splitAt.go l l n []

def List.splitAt.go {α : Type u_1} (l : List α) : List α → Nat → List α → List α × List α

Auxiliary for splitAt: splitAt.go l xs n acc = (acc.reverse ++ take n xs, drop n xs) if n < xs.length, and (l, []) otherwise.

Equations

• List.splitAt.go l [] x✝ x = (l, [])
• List.splitAt.go l (x_3 :: xs) n.succ x = List.splitAt.go l xs n (x_3 :: x)
• List.splitAt.go l x✝¹ x✝ x = (x.reverse, x✝¹)

def List.splitAtD {α : Type u_1} (n : Nat) (l : List α) (dflt : α) : List α × List α

Split a list at an index. Ensures the left list always has the specified length by right padding with the provided default element.

splitAtD 2 [a, b, c] x = ([a, b], [c])
splitAtD 4 [a, b, c] x = ([a, b, c, x], [])

Equations

• List.splitAtD n l dflt = List.splitAtD.go dflt n l []

def List.splitAtD.go {α : Type u_1} (dflt : α) : Nat → List α → List α → List α × List α

Auxiliary for splitAtD: splitAtD.go dflt n l acc = (acc.reverse ++ left, right) if splitAtD n l dflt = (left, right).

Equations

• List.splitAtD.go dflt n.succ (x_3 :: xs) x = List.splitAtD.go dflt n xs (x_3 :: x)
• List.splitAtD.go dflt 0 x✝ x = (x.reverse, x✝)
• List.splitAtD.go dflt x✝ [] x = (x.reverseAux (List.replicate x✝ dflt), [])

def List.splitOnP {α : Type u_1} (P : α → Bool) (l : List α) : List (List α)

Split a list at every element satisfying a predicate. The separators are not in the result.

[1, 1, 2, 3, 2, 4, 4].splitOnP (· == 2) = [[1, 1], [3], [4, 4]]

Equations

• List.splitOnP P l = List.splitOnP.go P l []

def List.splitOnP.go {α : Type u_1} (P : α → Bool) : List α → List α → List (List α)

Auxiliary for splitOnP: splitOnP.go xs acc = res' where res' is obtained from splitOnP P xs by prepending acc.reverse to the first element.

Equations

• List.splitOnP.go P [] x = [x.reverse]
• List.splitOnP.go P (a :: t) x = if P a = true then x.reverse :: List.splitOnP.go P t [] else List.splitOnP.go P t (a :: x)

@[inline]

def List.splitOnPTR {α : Type u_1} (P : α → Bool) (l : List α) : List (List α)

Tail recursive version of splitOnP.

Equations

• List.splitOnPTR P l = List.splitOnPTR.go P l #[] #[]

@[specialize #[]]

def List.splitOnPTR.go {α : Type u_1} (P : α → Bool) : List α → Array α → Array (List α) → List (List α)

Auxiliary for splitOnP: splitOnP.go xs acc r = r.toList ++ res' where res' is obtained from splitOnP P xs by prepending acc.toList to the first element.

Equations

• List.splitOnPTR.go P [] x✝ x = x.toListAppend [x✝.toList]
• List.splitOnPTR.go P (a :: t) x✝ x = bif P a then List.splitOnPTR.go P t #[] (x.push x✝.toList) else List.splitOnPTR.go P t (x✝.push a) x

@[csimp]

theorem List.splitOnP_eq_splitOnPTR : @List.splitOnP = @List.splitOnPTR

@[inline]

def List.splitOn {α : Type u_1} [BEq α] (a : α) (as : List α) : List (List α)

Split a list at every occurrence of a separator element. The separators are not in the result.

[1, 1, 2, 3, 2, 4, 4].splitOn 2 = [[1, 1], [3], [4, 4]]

Equations

• List.splitOn a as = List.splitOnP (fun (x : α) => x == a) as

def List.modifyNthTail {α : Type u_1} (f : List α → List α) : Nat → List α → List α

Apply a function to the nth tail of l. Returns the input without using f if the index is larger than the length of the List.

modifyNthTail f 2 [a, b, c] = [a, b] ++ f [c]

Equations

• List.modifyNthTail f 0 x = f x
• List.modifyNthTail f n.succ [] = []
• List.modifyNthTail f n.succ (a :: l) = a :: List.modifyNthTail f n l

@[inline]

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

Apply f to the head of the list, if it exists.

Equations

• List.modifyHead f x = match x with | [] => [] | a :: l => f a :: l

@[simp]

theorem List.modifyHead_nil {α : Type u_1} (f : α → α) : List.modifyHead f [] = []

@[simp]

theorem List.modifyHead_cons {α : Type u_1} (a : α) (l : List α) (f : α → α) : List.modifyHead f (a :: l) = f a :: l

def List.modifyNth {α : Type u_1} (f : α → α) : Nat → List α → List α

Apply f to the nth element of the list, if it exists.

Equations

• List.modifyNth f = List.modifyNthTail (List.modifyHead f)

def List.modifyNthTR {α : Type u_1} (f : α → α) (n : Nat) (l : List α) : List α

Tail-recursive version of modifyNth.

Equations

• List.modifyNthTR f n l = List.modifyNthTR.go f l n #[]

def List.modifyNthTR.go {α : Type u_1} (f : α → α) : List α → Nat → Array α → List α

Auxiliary for modifyNthTR: modifyNthTR.go f l n acc = acc.toList ++ modifyNth f n l.

Equations

• List.modifyNthTR.go f [] x✝ x = x.toList
• List.modifyNthTR.go f (a :: l) 0 x = x.toListAppend (f a :: l)
• List.modifyNthTR.go f (a :: l) n.succ x = List.modifyNthTR.go f l n (x.push a)

theorem List.modifyNthTR_go_eq : ∀ {α : Type u_1} {f : α → α} {acc : Array α} (l : List α) (n : Nat), List.modifyNthTR.go f l n acc = acc.data ++ List.modifyNth f n l

@[csimp]

theorem List.modifyNth_eq_modifyNthTR : @List.modifyNth = @List.modifyNthTR

@[inline]

def List.modifyLast {α : Type u_1} (f : α → α) (l : List α) : List α

Apply f to the last element of l, if it exists.

Equations

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

@[specialize #[]]

def List.modifyLast.go {α : Type u_1} (f : α → α) : List α → Array α → List α

Auxiliary for modifyLast: modifyLast.go f l acc = acc.toList ++ modifyLast f l.

Equations

• List.modifyLast.go f [] x = []
• List.modifyLast.go f [x_2] x = x.toListAppend [f x_2]
• List.modifyLast.go f (x_2 :: xs) x = List.modifyLast.go f xs (x.push x_2)

def List.insertNth {α : Type u_1} (n : Nat) (a : α) : List α → List α

insertNth n a l inserts a into the list l after the first n elements of l

insertNth 2 1 [1, 2, 3, 4] = [1, 2, 1, 3, 4]

Equations

• List.insertNth n a = List.modifyNthTail (List.cons a) n

@[inline]

def List.insertNthTR {α : Type u_1} (n : Nat) (a : α) (l : List α) : List α

Tail-recursive version of insertNth.

Equations

• List.insertNthTR n a l = List.insertNthTR.go a n l #[]

def List.insertNthTR.go {α : Type u_1} (a : α) : Nat → List α → Array α → List α

Auxiliary for insertNthTR: insertNthTR.go a n l acc = acc.toList ++ insertNth n a l.

Equations

• List.insertNthTR.go a 0 x✝ x = x.toListAppend (a :: x✝)
• List.insertNthTR.go a x✝ [] x = x.toList
• List.insertNthTR.go a n.succ (a_1 :: l) x = List.insertNthTR.go a n l (x.push a_1)

theorem List.insertNthTR_go_eq : ∀ {α : Type u_1} {a : α} {acc : Array α} (n : Nat) (l : List α), List.insertNthTR.go a n l acc = acc.data ++ List.insertNth n a l

@[csimp]

theorem List.insertNth_eq_insertNthTR : @List.insertNth = @List.insertNthTR

theorem List.headD_eq_head? {α : Type u_1} (l : List α) (a : α) : l.headD a = l.head?.getD a

def List.takeD {α : Type u_1} : Nat → List α → α → List α

Take n elements from a list l. If l has less than n elements, append n - length l elements x.

Equations

• List.takeD 0 x✝ x = []
• List.takeD n.succ x✝ x = x✝.headD x :: List.takeD n x✝.tail x

@[simp]

theorem List.takeD_zero {α : Type u_1} (l : List α) (a : α) : List.takeD 0 l a = []

@[simp]

theorem List.takeD_succ {α : Type u_1} {n : Nat} (l : List α) (a : α) : List.takeD (n + 1) l a = l.head?.getD a :: List.takeD n l.tail a

@[simp]

theorem List.takeD_nil {α : Type u_1} (n : Nat) (a : α) : List.takeD n [] a = List.replicate n a

def List.takeDTR {α : Type u_1} (n : Nat) (l : List α) (dflt : α) : List α

Tail-recursive version of takeD.

Equations

• List.takeDTR n l dflt = List.takeDTR.go dflt n l #[]

def List.takeDTR.go {α : Type u_1} (dflt : α) : Nat → List α → Array α → List α

Auxiliary for takeDTR: takeDTR.go dflt n l acc = acc.toList ++ takeD n l dflt.

Equations

• List.takeDTR.go dflt n.succ (x_3 :: xs) x = List.takeDTR.go dflt n xs (x.push x_3)
• List.takeDTR.go dflt 0 x✝ x = x.toList
• List.takeDTR.go dflt x✝ [] x = x.toListAppend (List.replicate x✝ dflt)

theorem List.takeDTR_go_eq : ∀ {α : Type u_1} {dflt : α} {acc : Array α} (n : Nat) (l : List α), List.takeDTR.go dflt n l acc = acc.data ++ List.takeD n l dflt

@[csimp]

theorem List.takeD_eq_takeDTR : @List.takeD = @List.takeDTR

def List.scanl {α : Type u_1} {β : Type u_2} (f : α → β → α) (a : α) : List β → List α

Fold a function f over the list from the left, returning the list of partial results.

scanl (+) 0 [1, 2, 3] = [0, 1, 3, 6]

Equations

• List.scanl f a [] = [a]
• List.scanl f a (a_1 :: l) = a :: List.scanl f (f a a_1) l

@[inline]

def List.scanlTR {α : Type u_1} {β : Type u_2} (f : α → β → α) (a : α) (l : List β) : List α

Tail-recursive version of scanl.

Equations

• List.scanlTR f a l = List.scanlTR.go f l a #[]

@[specialize #[]]

def List.scanlTR.go {α : Type u_1} {β : Type u_2} (f : α → β → α) : List β → α → Array α → List α

Auxiliary for scanlTR: scanlTR.go f l a acc = acc.toList ++ scanl f a l.

Equations

• List.scanlTR.go f [] x✝ x = x.toListAppend [x✝]
• List.scanlTR.go f (b :: l) x✝ x = List.scanlTR.go f l (f x✝ b) (x.push x✝)

theorem List.scanlTR_go_eq : ∀ {α : Type u_1} {α_1 : Type u_2} {f : α → α_1 → α} {a : α} {acc : Array α} (l : List α_1), List.scanlTR.go f l a acc = acc.data ++ List.scanl f a l

@[csimp]

theorem List.scanl_eq_scanlTR : @List.scanl = @List.scanlTR

def List.scanr {α : Type u_1} {β : Type u_2} (f : α → β → β) (b : β) (l : List α) : List β

Fold a function f over the list from the right, returning the list of partial results.

scanr (+) 0 [1, 2, 3] = [6, 5, 3, 0]

Equations

• List.scanr f b l = match List.foldr (fun (a : α) (x : β × List β) => match x with | (b', l') => (f a b', b' :: l')) (b, []) l with | (b', l') => b' :: l'

@[specialize #[]]

def List.foldlIdx {α : Sort u_1} {β : Type u_2} (f : Nat → α → β → α) (init : α) : List β → optParam Nat 0 → α

Fold a list from left to right as with foldl, but the combining function also receives each element's index.

Equations

• List.foldlIdx f init [] x = init
• List.foldlIdx f init (b :: l) x = List.foldlIdx f (f x init b) l (x + 1)

@[specialize #[]]

def List.foldrIdx {α : Type u_1} {β : Sort u_2} (f : Nat → α → β → β) (init : β) (l : List α) (start : optParam Nat 0) : β

Fold a list from right to left as with foldr, but the combining function also receives each element's index.

Equations

• List.foldrIdx f init [] x = init
• List.foldrIdx f init (b :: l) x = f x b (List.foldrIdx f init l (x + 1))

@[inline]

def List.findIdxs {α : Type u_1} (p : α → Bool) (l : List α) : List Nat

findIdxs p l is the list of indexes of elements of l that satisfy p.

Equations

• List.findIdxs p l = List.foldrIdx (fun (i : Nat) (a : α) (is : List Nat) => if p a = true then i :: is else is) [] l

@[inline]

def List.indexesValues {α : Type u_1} (p : α → Bool) (l : List α) : List (Nat × α)

Returns the elements of l that satisfy p together with their indexes in l. The returned list is ordered by index.

Equations

• List.indexesValues p l = List.foldrIdx (fun (i : Nat) (a : α) (l : List (Nat × α)) => if p a = true then (i, a) :: l else l) [] l

@[inline]

def List.indexesOf {α : Type u_1} [BEq α] (a : α) : List α → List Nat

indexesOf a l is the list of all indexes of a in l. For example:

indexesOf a [a, b, a, a] = [0, 2, 3]

Equations

• List.indexesOf a = List.findIdxs fun (x : α) => x == a

@[inline]

def List.lookmap {α : Type u_1} (f : α → Option α) (l : List α) : List α

lookmap is a combination of lookup and filterMap. lookmap f l will apply f : α → Option α to each element of the list, replacing a → b at the first value a in the list such that f a = some b.

Equations

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

@[specialize #[]]

def List.lookmap.go {α : Type u_1} (f : α → Option α) : List α → Array α → List α

Auxiliary for lookmap: lookmap.go f l acc = acc.toList ++ lookmap f l.

Equations

• List.lookmap.go f [] x = x.toList
• List.lookmap.go f (x_2 :: xs) x = match f x_2 with | some b => x.toListAppend (b :: xs) | none => List.lookmap.go f xs (x.push x_2)

def List.inits {α : Type u_1} : List α → List (List α)

inits l is the list of initial segments of l.

inits [1, 2, 3] = [[], [1], [1, 2], [1, 2, 3]]

Equations

• [].inits = [[]]
• (a :: l).inits = [] :: List.map (fun (t : List α) => a :: t) l.inits

def List.initsTR {α : Type u_1} (l : List α) : List (List α)

Tail-recursive version of inits.

Equations

• l.initsTR = (List.foldr (fun (a : α) (arrs : Array (List α)) => (Array.map (fun (t : List α) => a :: t) arrs).push []) #[[]] l).toListRev

@[csimp]

theorem List.inits_eq_initsTR : @List.inits = @List.initsTR

def List.tails {α : Type u_1} : List α → List (List α)

tails l is the list of terminal segments of l.

tails [1, 2, 3] = [[1, 2, 3], [2, 3], [3], []]

Equations

• [].tails = [[]]
• (a :: l).tails = (a :: l) :: l.tails

def List.tailsTR {α : Type u_1} (l : List α) : List (List α)

Tail-recursive version of tails.

Equations

• l.tailsTR = List.tailsTR.go l #[]

def List.tailsTR.go {α : Type u_1} (l : List α) (acc : Array (List α)) : List (List α)

Auxiliary for tailsTR: tailsTR.go l acc = acc.toList ++ tails l.

Equations

• List.tailsTR.go [] acc = acc.toListAppend [[]]
• List.tailsTR.go (a :: l_1) acc = List.tailsTR.go l_1 (acc.push (a :: l_1))

@[csimp]

theorem List.tails_eq_tailsTR : @List.tails = @List.tailsTR

def List.sublists' {α : Type u_1} (l : List α) : List (List α)

sublists' l is the list of all (non-contiguous) sublists of l. It differs from sublists only in the order of appearance of the sublists; sublists' uses the first element of the list as the MSB, sublists uses the first element of the list as the LSB.

sublists' [1, 2, 3] = [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

Equations

• l.sublists' = let f := fun (a : α) (arr : Array (List α)) => Array.foldl (fun (r : Array (List α)) (l : List α) => r.push (a :: l)) arr arr; (List.foldr f #[[]] l).toList

@[implemented_by List.sublistsFast]

def List.sublists {α : Type u_1} (l : List α) : List (List α)

sublists l is the list of all (non-contiguous) sublists of l; cf. sublists' for a different ordering.

sublists [1, 2, 3] = [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Equations

• l.sublists = List.foldr (fun (a : α) (acc : List (List α)) => acc.bind fun (x : List α) => [x, a :: x]) [[]] l

def List.sublistsFast {α : Type u_1} (l : List α) : List (List α)

A version of List.sublists that has faster runtime performance but worse kernel performance

Equations

• One or more equations did not get rendered due to their size.

inductive List.Forall₂ {α : Type u_1} {β : Type u_2} (R : α → β → Prop) : List α → List β → Prop

Forall₂ R l₁ l₂ means that l₁ and l₂ have the same length, and whenever a is the nth element of l₁, and b is the nth element of l₂, then R a b is satisfied.

• nil: ∀ {α : Type u_1} {β : Type u_2} {R : α → β → Prop}, List.Forall₂ R [] []

  Two nil lists are Forall₂-related

• cons: ∀ {α : Type u_1} {β : Type u_2} {R : α → β → Prop} {a : α} {b : β} {l₁ : List α} {l₂ : List β}, R a b → List.Forall₂ R l₁ l₂ → List.Forall₂ R (a :: l₁) (b :: l₂)

  Two cons lists are related by Forall₂ R if the heads are related by R and the tails are related by Forall₂ R

@[simp]

theorem List.forall₂_cons {α : Type u_1} {β : Type u_2} {R : α → β → Prop} {a : α} {b : β} {l₁ : List α} {l₂ : List β} : List.Forall₂ R (a :: l₁) (b :: l₂) ↔ R a b ∧ List.Forall₂ R l₁ l₂

def List.all₂ {α : Type u_1} {β : Type u_2} (r : α → β → Bool) : List α → List β → Bool

Check for all elements a, b, where a and b are the nth element of the first and second List respectively, that r a b = true.

Equations

• List.all₂ r [] [] = true
• List.all₂ r (a :: as) (b :: bs) = if r a b = true then List.all₂ r as bs else false
• List.all₂ r x✝ x = false

@[simp]

theorem List.all₂_eq_true {α : Type u_1} {β : Type u_2} {r : α → β → Bool} (l₁ : List α) (l₂ : List β) : List.all₂ r l₁ l₂ = true ↔ List.Forall₂ (fun (x : α) (x_1 : β) => r x x_1 = true) l₁ l₂

instance List.instDecidableForall₂ {α : Type u_1} {β : Type u_2} {R : α → β → Prop} [(a : α) → (b : β) → Decidable (R a b)] (l₁ : List α) (l₂ : List β) : Decidable (List.Forall₂ R l₁ l₂)

Equations

• l₁.instDecidableForall₂ l₂ = decidable_of_iff (List.all₂ (fun (x : α) (x_1 : β) => decide (R x x_1)) l₁ l₂ = true) ⋯

def List.transpose {α : Type u_1} (l : List (List α)) : List (List α)

Transpose of a list of lists, treated as a matrix.

transpose [[1, 2], [3, 4], [5, 6]] = [[1, 3, 5], [2, 4, 6]]

Equations

• l.transpose = (List.foldr List.transpose.go #[] l).toList

def List.transpose.pop {α : Type u_1} (old : List α) : List α → Id (List α × List α)

pop : List α → StateM (List α) (List α) transforms the input list old by taking the head of the current state and pushing it on the head of old. If the state list is empty, then old is left unchanged.

Equations

• List.transpose.pop old x = match x with | [] => (old, []) | a :: l => (a :: old, l)

def List.transpose.go {α : Type u_1} (l : List α) (acc : Array (List α)) : Array (List α)

go : List α → Array (List α) → Array (List α) handles the insertion of a new list into all the lists in the array: go [a, b, c] #[l₁, l₂, l₃] = #[a::l₁, b::l₂, c::l₃]. If the new list is too short, the later lists are unchanged, and if it is too long the array is extended:

go [a] #[l₁, l₂, l₃] = #[a::l₁, l₂, l₃]
go [a, b, c, d] #[l₁, l₂, l₃] = #[a::l₁, b::l₂, c::l₃, [d]]

Equations

• List.transpose.go l acc = match Array.mapM List.transpose.pop acc l with | (acc, l) => List.foldl (fun (arr : Array (List α)) (a : α) => arr.push [a]) acc l

def List.sections {α : Type u_1} : List (List α) → List (List α)

List of all sections through a list of lists. A section of [L₁, L₂, ..., Lₙ] is a list whose first element comes from L₁, whose second element comes from L₂, and so on.

Equations

• [].sections = [[]]
• (l :: L).sections = L.sections.bind fun (s : List α) => List.map (fun (a : α) => a :: s) l

def List.sectionsTR {α : Type u_1} (L : List (List α)) : List (List α)

Optimized version of sections.

Equations

• L.sectionsTR = bif L.any List.isEmpty then [] else (List.foldr List.sectionsTR.go #[[]] L).toList

def List.sectionsTR.go {α : Type u_1} (l : List α) (acc : Array (List α)) : Array (List α)

go : List α → Array (List α) → Array (List α) inserts one list into the accumulated list of sections acc: go [a, b] #[l₁, l₂] = [a::l₁, b::l₁, a::l₂, b::l₂].

Equations

• List.sectionsTR.go l acc = Array.foldl (fun (acc' : Array (List α)) (l' : List α) => List.foldl (fun (acc' : Array (List α)) (a : α) => acc'.push (a :: l')) acc' l) #[] acc

theorem List.sections_eq_nil_of_isEmpty {α : Type u_1} {L : List (List α)} : L.any List.isEmpty = true → L.sections = []

@[csimp]

theorem List.sections_eq_sectionsTR : @List.sections = @List.sectionsTR

def List.extractP {α : Type u_1} (p : α → Bool) (l : List α) : Option α × List α

extractP p l returns a pair of an element a of l satisfying the predicate p, and l, with a removed. If there is no such element a it returns (none, l).

Equations

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

def List.extractP.go {α : Type u_1} (p : α → Bool) (l : List α) : List α → Array α → Option α × List α

Auxiliary for extractP: extractP.go p l xs acc = (some a, acc.toList ++ out) if extractP p xs = (some a, out), and extractP.go p l xs acc = (none, l) if extractP p xs = (none, _).

Equations

• List.extractP.go p l [] x = (none, l)
• List.extractP.go p l (x_2 :: xs) x = bif p x_2 then (some x_2, x.toListAppend xs) else List.extractP.go p l xs (x.push x_2)

def List.revzip {α : Type u_1} (l : List α) : List (α × α)

revzip l returns a list of pairs of the elements of l paired with the elements of l in reverse order.

revzip [1, 2, 3, 4, 5] = [(1, 5), (2, 4), (3, 3), (4, 2), (5, 1)]

Equations

• l.revzip = l.zip l.reverse

def List.product {α : Type u_1} {β : Type u_2} (l₁ : List α) (l₂ : List β) : List (α × β)

product l₁ l₂ is the list of pairs (a, b) where a ∈ l₁ and b ∈ l₂.

product [1, 2] [5, 6] = [(1, 5), (1, 6), (2, 5), (2, 6)]

Equations

• l₁.product l₂ = l₁.bind fun (a : α) => List.map (Prod.mk a) l₂

def List.productTR {α : Type u_1} {β : Type u_2} (l₁ : List α) (l₂ : List β) : List (α × β)

Optimized version of product.

Equations

• l₁.productTR l₂ = (List.foldl (fun (acc : Array (α × β)) (a : α) => List.foldl (fun (acc : Array (α × β)) (b : β) => acc.push (a, b)) acc l₂) #[] l₁).toList

@[csimp]

theorem List.product_eq_productTR : @List.product = @List.productTR

def List.sigma {α : Type u_1} {σ : α → Type u_2} (l₁ : List α) (l₂ : (a : α) → List (σ a)) : List ((a : α) × σ a)

sigma l₁ l₂ is the list of dependent pairs (a, b) where a ∈ l₁ and b ∈ l₂ a.

sigma [1, 2] (λ_, [(5 : Nat), 6]) = [(1, 5), (1, 6), (2, 5), (2, 6)]

Equations

• l₁.sigma l₂ = l₁.bind fun (a : α) => List.map (Sigma.mk a) (l₂ a)

def List.sigmaTR {α : Type u_1} {σ : α → Type u_2} (l₁ : List α) (l₂ : (a : α) → List (σ a)) : List ((a : α) × σ a)

Optimized version of sigma.

Equations

• l₁.sigmaTR l₂ = (List.foldl (fun (acc : Array ((a : α) × σ a)) (a : α) => List.foldl (fun (acc : Array ((a : α) × σ a)) (b : σ a) => acc.push ⟨a, b⟩) acc (l₂ a)) #[] l₁).toList

@[csimp]

theorem List.sigma_eq_sigmaTR : @List.sigma = @List.sigmaTR

def List.ofFn {α : Type u_1} {n : Nat} (f : Fin n → α) : List α

ofFn f with f : fin n → α returns the list whose ith element is f i

ofFn f = [f 0, f 1, ... , f (n - 1)]

Equations

• List.ofFn f = List.ofFn.go f n 0 ⋯

def List.ofFn.go {α : Type u_1} {n : Nat} (f : Fin n → α) (i : Nat) (j : Nat) (h : i + j = n) : List α

Auxiliary for List.ofFn. ofFn.go f i j _ = [f j, ..., f (n - 1)].

Equations

• List.ofFn.go f 0 x x_1 = []
• List.ofFn.go f i.succ x x_1 = f ⟨x, ⋯⟩ :: List.ofFn.go f i (x + 1) ⋯

@[inline]

def List.ofFnTR {α : Type u_1} {n : Nat} (f : Fin n → α) : List α

Tail-recursive version of ofFn.

Equations

• List.ofFnTR f = List.ofFnTR.go f n ⋯ []

def List.ofFnTR.go {α : Type u_1} {n : Nat} (f : Fin n → α) (i : Nat) (h : i ≤ n) : List α → List α

Auxiliary for List.ofFnTR. ofFnTR.go f i _ acc = f 0 :: ... :: f (i - 1) :: acc.

Equations

• List.ofFnTR.go f 0 x_3 x = x
• List.ofFnTR.go f i.succ h x = List.ofFnTR.go f i ⋯ (f ⟨i, h⟩ :: x)

@[csimp]

theorem List.ofFn_eq_ofFnTR : @List.ofFn = @List.ofFnTR

@[irreducible]

theorem List.ofFn_eq_ofFnTR.go (α : Type u_1) (n : Nat) (f : Fin n → α) (i : Nat) (j : Nat) (h : i + j = n) (h' : j ≤ n) : List.ofFnTR.go f j h' (List.ofFn.go f i j h) = List.ofFn f

def List.ofFnNthVal {α : Type u_1} {n : Nat} (f : Fin n → α) (i : Nat) : Option α

ofFnNthVal f i returns some (f i) if i < n and none otherwise.

Equations

• List.ofFnNthVal f i = if h : i < n then some (f ⟨i, h⟩) else none

def List.Disjoint {α : Type u_1} (l₁ : List α) (l₂ : List α) : Prop

disjoint l₁ l₂ means that l₁ and l₂ have no elements in common.

Equations

• l₁.Disjoint l₂ = ∀ ⦃a : α⦄, a ∈ l₁ → a ∈ l₂ → False

def List.takeWhile₂ {α : Type u_1} {β : Type u_2} (R : α → β → Bool) : List α → List β → List α × List β

Returns the longest initial prefix of two lists such that they are pairwise related by R.

takeWhile₂ (· < ·) [1, 2, 4, 5] [5, 4, 3, 6] = ([1, 2], [5, 4])

Equations

• List.takeWhile₂ R (a :: as) (b :: bs) = if R a b = true then match List.takeWhile₂ R as bs with | (as', bs') => (a :: as', b :: bs') else ([], [])
• List.takeWhile₂ R x✝ x = ([], [])

@[inline]

def List.takeWhile₂TR {α : Type u_1} {β : Type u_2} (R : α → β → Bool) (as : List α) (bs : List β) : List α × List β

Tail-recursive version of takeWhile₂.

Equations

• List.takeWhile₂TR R as bs = List.takeWhile₂TR.go R as bs [] []

@[specialize #[]]

def List.takeWhile₂TR.go {α : Type u_1} {β : Type u_2} (R : α → β → Bool) : List α → List β → List α → List β → List α × List β

Auxiliary for takeWhile₂TR: takeWhile₂TR.go R as bs acca accb = (acca.reverse ++ as', acca.reverse ++ bs') if takeWhile₂ R as bs = (as', bs').

Equations

• List.takeWhile₂TR.go R (a :: as) (b :: bs) x✝ x = bif R a b then List.takeWhile₂TR.go R as bs (a :: x✝) (b :: x) else (x✝.reverse, x.reverse)
• List.takeWhile₂TR.go R x✝² x✝¹ x✝ x = (x✝.reverse, x.reverse)

@[csimp]

theorem List.takeWhile₂_eq_takeWhile₂TR : @List.takeWhile₂ = @List.takeWhile₂TR

@[irreducible]

theorem List.takeWhile₂_eq_takeWhile₂TR.go (α : Type u_2) (β : Type u_1) (R : α → β → Bool) (as : List α) (bs : List β) (acca : List α) (accb : List β) : List.takeWhile₂TR.go R as bs acca accb = (acca.reverse ++ (List.takeWhile₂ R as bs).fst, accb.reverse ++ (List.takeWhile₂ R as bs).snd)

def List.pwFilter {α : Type u_1} (R : α → α → Prop) [DecidableRel R] (l : List α) : List α

pwFilter R l is a maximal sublist of l which is Pairwise R. pwFilter (·≠·) is the erase duplicates function (cf. eraseDup), and pwFilter (·<·) finds a maximal increasing subsequence in l. For example,

pwFilter (·<·) [0, 1, 5, 2, 6, 3, 4] = [0, 1, 2, 3, 4]

Equations

• List.pwFilter R l = List.foldr (fun (x : α) (IH : List α) => if ∀ (y : α), y ∈ IH → R x y then x :: IH else IH) [] l

inductive List.Chain {α : Type u_1} (R : α → α → Prop) : α → List α → Prop

Chain R a l means that R holds between adjacent elements of a::l.

Chain R a [b, c, d] ↔ R a b ∧ R b c ∧ R c d

• nil: ∀ {α : Type u_1} {R : α → α → Prop} {a : α}, List.Chain R a []

  A chain of length 1 is trivially a chain.

• cons: ∀ {α : Type u_1} {R : α → α → Prop} {a b : α} {l : List α}, R a b → List.Chain R b l → List.Chain R a (b :: l)

  If a relates to b and b::l is a chain, then a :: b :: l is also a chain.

def List.Chain' {α : Type u_1} (R : α → α → Prop) : List α → Prop

Chain' R l means that R holds between adjacent elements of l.

Chain' R [a, b, c, d] ↔ R a b ∧ R b c ∧ R c d

Equations

• List.Chain' R x = match x with | [] => True | a :: l => List.Chain R a l

@[inline]

def List.eraseDup {α : Type u_1} [BEq α] : List α → List α

eraseDup l removes duplicates from l (taking only the first occurrence). Defined as pwFilter (≠).

eraseDup [1, 0, 2, 2, 1] = [0, 2, 1] 

Equations

• List.eraseDup = List.pwFilter fun (x x_1 : α) => (x != x_1) = true

@[deprecated List.getLastD]

def List.ilast' {α : Type u_1} : α → List α → α

ilast' x xs returns the last element of xs if xs is non-empty; it returns x otherwise. Use List.getLastD instead.

Equations

• List.ilast' x [] = x
• List.ilast' x (b :: l) = List.ilast' b l

@[deprecated List.getLast?]

def List.last' {α : Type u_1} : List α → Option α

last' xs returns the last element of xs if xs is non-empty; it returns none otherwise. Use List.getLast? instead

Equations

• [].last' = none
• [a].last' = some a
• (head :: l).last' = l.last'

@[inline]

def List.rotate {α : Type u_1} (l : List α) (n : Nat) : List α

rotate l n rotates the elements of l to the left by n

rotate [0, 1, 2, 3, 4, 5] 2 = [2, 3, 4, 5, 0, 1]

Equations

• l.rotate n = match List.splitAt (n % l.length) l with | (l₁, l₂) => l₂ ++ l₁

def List.rotate' {α : Type u_1} : List α → Nat → List α

rotate' is the same as rotate, but slower. Used for proofs about rotate

Equations

• [].rotate' x = []
• x.rotate' 0 = x
• (a :: l).rotate' n.succ = (l ++ [a]).rotate' n

def List.mapDiagM {m : Type u_1 → Type u_2} {α : Type u_3} {β : Type u_1} [Monad m] (f : α → α → m β) (l : List α) : m (List β)

mapDiagM f l calls f on all elements in the upper triangular part of l × l. That is, for each e ∈ l, it will run f e e and then f e e' for each e' that appears after e in l.

mapDiagM f [1, 2, 3] =
  return [← f 1 1, ← f 1 2, ← f 1 3, ← f 2 2, ← f 2 3, ← f 3 3]

Equations

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

def List.mapDiagM.go {m : Type u_1 → Type u_2} {α : Type u_3} {β : Type u_1} [Monad m] (f : α → α → m β) : List α → Array β → m (List β)

Auxiliary for mapDiagM: mapDiagM.go as f acc = (acc.toList ++ ·) <$> mapDiagM f as

Equations

• List.mapDiagM.go f [] x = pure x.toList
• List.mapDiagM.go f (a :: as) x = do let b ← f a a let acc ← List.foldlM (fun (x : Array β) (x_1 : α) => x.push <$> f a x_1) (x.push b) as List.mapDiagM.go f as acc

def List.forDiagM {m : Type u_1 → Type u_2} {α : Type u_3} [Monad m] (f : α → α → m PUnit) : List α → m PUnit

forDiagM f l calls f on all elements in the upper triangular part of l × l. That is, for each e ∈ l, it will run f e e and then f e e' for each e' that appears after e in l.

forDiagM f [1, 2, 3] = do f 1 1; f 1 2; f 1 3; f 2 2; f 2 3; f 3 3

Equations

• List.forDiagM f [] = pure PUnit.unit
• List.forDiagM f (a :: l) = do f a a l.forM (f a) List.forDiagM f l

def List.getRest {α : Type u_1} [DecidableEq α] : List α → List α → Option (List α)

getRest l l₁ returns some l₂ if l = l₁ ++ l₂. If l₁ is not a prefix of l, returns none

Equations

• x.getRest [] = some x
• [].getRest x = none
• (x_2 :: l).getRest (y :: l₁) = if x_2 = y then l.getRest l₁ else none

def List.dropSlice {α : Type u_1} : Nat → Nat → List α → List α

List.dropSlice n m xs removes a slice of length m at index n in list xs.

Equations

• List.dropSlice x✝ x [] = []
• List.dropSlice 0 x✝ x = List.drop x✝ x
• List.dropSlice n.succ x (x_3 :: xs) = x_3 :: List.dropSlice n x xs

@[inline]

def List.dropSliceTR {α : Type u_1} (n : Nat) (m : Nat) (l : List α) : List α

Optimized version of dropSlice.

Equations

• List.dropSliceTR n m l = match m with | 0 => l | m.succ => List.dropSliceTR.go l m l n #[]

def List.dropSliceTR.go {α : Type u_1} (l : List α) (m : Nat) : List α → Nat → Array α → List α

Auxiliary for dropSliceTR: dropSliceTR.go l m xs n acc = acc.toList ++ dropSlice n m xs unless n ≥ length xs, in which case it is l.

Equations

• List.dropSliceTR.go l m [] x✝ x = l
• List.dropSliceTR.go l m (a :: l_1) 0 x = x.toListAppend (List.drop m l_1)
• List.dropSliceTR.go l m (a :: l_1) n.succ x = List.dropSliceTR.go l m l_1 n (x.push a)

theorem List.dropSlice_zero₂ {α : Type u_1} (n : Nat) (l : List α) : List.dropSlice n 0 l = l

@[csimp]

theorem List.dropSlice_eq_dropSliceTR : @List.dropSlice = @List.dropSliceTR

theorem List.dropSlice_eq_dropSliceTR.go (α : Type u_1) (l : List α) (m : Nat) (acc : Array α) (xs : List α) (n : Nat) : l = acc.data ++ xs → List.dropSliceTR.go l m xs n acc = acc.data ++ List.dropSlice n (m + 1) xs

def List.zipWithLeft' {α : Type u_1} {β : Type u_2} {γ : Type u_3} (f : α → Option β → γ) : List α → List β → List γ × List β

Left-biased version of List.zipWith. zipWithLeft' f as bs applies f to each pair of elements aᵢ ∈ as and bᵢ ∈ bs. If bs is shorter than as, f is applied to none for the remaining aᵢ. Returns the results of the f applications and the remaining bs.

zipWithLeft' prod.mk [1, 2] ['a'] = ([(1, some 'a'), (2, none)], [])
zipWithLeft' prod.mk [1] ['a', 'b'] = ([(1, some 'a')], ['b'])

Equations

• List.zipWithLeft' f [] x = ([], x)
• List.zipWithLeft' f (a :: as) [] = (List.map (fun (a : α) => f a none) (a :: as), [])
• List.zipWithLeft' f (a :: as) (b :: bs) = let r := List.zipWithLeft' f as bs; (f a (some b) :: r.fst, r.snd)

@[inline]

def List.zipWithLeft'TR {α : Type u_1} {β : Type u_2} {γ : Type u_3} (f : α → Option β → γ) (as : List α) (bs : List β) : List γ × List β

Tail-recursive version of zipWithLeft'.

Equations

• List.zipWithLeft'TR f as bs = List.zipWithLeft'TR.go f as bs #[]

def List.zipWithLeft'TR.go {α : Type u_1} {β : Type u_2} {γ : Type u_3} (f : α → Option β → γ) : List α → List β → Array γ → List γ × List β

Auxiliary for zipWithLeft'TR: zipWithLeft'TR.go l acc = acc.toList ++ zipWithLeft' l.

Equations

• List.zipWithLeft'TR.go f [] x✝ x = (x.toList, x✝)
• List.zipWithLeft'TR.go f x✝ [] x = ((List.foldl (fun (acc : Array γ) (a : α) => acc.push (f a none)) x x✝).toList, [])
• List.zipWithLeft'TR.go f (a :: as) (b :: bs) x = List.zipWithLeft'TR.go f as bs (x.push (f a (some b)))

@[csimp]

theorem List.zipWithLeft'_eq_zipWithLeft'TR : @List.zipWithLeft' = @List.zipWithLeft'TR

theorem List.zipWithLeft'_eq_zipWithLeft'TR.go (α : Type u_3) (β : Type u_2) (γ : Type u_1) (f : α → Option β → γ) (acc : Array γ) (as : List α) (bs : List β) : List.zipWithLeft'TR.go f as bs acc = match List.zipWithLeft' f as bs with | (l, r) => (acc.toList ++ l, r)

@[inline]

def List.zipWithRight' {α : Type u_1} {β : Type u_2} {γ : Type u_3} (f : Option α → β → γ) (as : List α) (bs : List β) : List γ × List α

Right-biased version of List.zipWith. zipWithRight' f as bs applies f to each pair of elements aᵢ ∈ as and bᵢ ∈ bs. If as is shorter than bs, f is applied to none for the remaining bᵢ. Returns the results of the f applications and the remaining as.

zipWithRight' prod.mk [1] ['a', 'b'] = ([(some 1, 'a'), (none, 'b')], [])
zipWithRight' prod.mk [1, 2] ['a'] = ([(some 1, 'a')], [2])

Equations

• List.zipWithRight' f as bs = List.zipWithLeft' (flip f) bs as

@[inline]

def List.zipLeft' {α : Type u_1} {β : Type u_2} : List α → List β → List (α × Option β) × List β

Left-biased version of List.zip. zipLeft' as bs returns the list of pairs (aᵢ, bᵢ) for aᵢ ∈ as and bᵢ ∈ bs. If bs is shorter than as, the remaining aᵢ are paired with none. Also returns the remaining bs.

zipLeft' [1, 2] ['a'] = ([(1, some 'a'), (2, none)], [])
zipLeft' [1] ['a', 'b'] = ([(1, some 'a')], ['b'])
zipLeft' = zipWithLeft' prod.mk

Equations

• List.zipLeft' = List.zipWithLeft' Prod.mk

@[inline]

def List.zipRight' {α : Type u_1} {β : Type u_2} : List α → List β → List (Option α × β) × List α

Right-biased version of List.zip. zipRight' as bs returns the list of pairs (aᵢ, bᵢ) for aᵢ ∈ as and bᵢ ∈ bs. If as is shorter than bs, the remaining bᵢ are paired with none. Also returns the remaining as.

zipRight' [1] ['a', 'b'] = ([(some 1, 'a'), (none, 'b')], [])
zipRight' [1, 2] ['a'] = ([(some 1, 'a')], [2])
zipRight' = zipWithRight' prod.mk

Equations

• List.zipRight' = List.zipWithRight' Prod.mk

def List.zipWithLeft {α : Type u_1} {β : Type u_2} {γ : Type u_3} (f : α → Option β → γ) : List α → List β → List γ

Left-biased version of List.zipWith. zipWithLeft f as bs applies f to each pair aᵢ ∈ as and bᵢ ‌∈ bs‌∈ bs. If bs is shorter than as, f is applied to none for the remaining aᵢ.

zipWithLeft prod.mk [1, 2] ['a'] = [(1, some 'a'), (2, none)]
zipWithLeft prod.mk [1] ['a', 'b'] = [(1, some 'a')]
zipWithLeft f as bs = (zipWithLeft' f as bs).fst

Equations

• List.zipWithLeft f [] x = []
• List.zipWithLeft f (a :: as) [] = List.map (fun (a : α) => f a none) (a :: as)
• List.zipWithLeft f (a :: as) (b :: bs) = f a (some b) :: List.zipWithLeft f as bs

@[inline]

def List.zipWithLeftTR {α : Type u_1} {β : Type u_2} {γ : Type u_3} (f : α → Option β → γ) (as : List α) (bs : List β) : List γ

Tail-recursive version of zipWithLeft.

Equations

• List.zipWithLeftTR f as bs = List.zipWithLeftTR.go f as bs #[]

def List.zipWithLeftTR.go {α : Type u_1} {β : Type u_2} {γ : Type u_3} (f : α → Option β → γ) : List α → List β → Array γ → List γ

Auxiliary for zipWithLeftTR: zipWithLeftTR.go l acc = acc.toList ++ zipWithLeft l.

Equations

• List.zipWithLeftTR.go f [] x✝ x = x.toList
• List.zipWithLeftTR.go f x✝ [] x = (List.foldl (fun (acc : Array γ) (a : α) => acc.push (f a none)) x x✝).toList
• List.zipWithLeftTR.go f (a :: as) (b :: bs) x = List.zipWithLeftTR.go f as bs (x.push (f a (some b)))

@[csimp]

theorem List.zipWithLeft_eq_zipWithLeftTR : @List.zipWithLeft = @List.zipWithLeftTR

theorem List.zipWithLeft_eq_zipWithLeftTR.go (α : Type u_3) (β : Type u_2) (γ : Type u_1) (f : α → Option β → γ) (acc : Array γ) (as : List α) (bs : List β) : List.zipWithLeftTR.go f as bs acc = acc.toList ++ List.zipWithLeft f as bs

@[inline]

def List.zipWithRight {α : Type u_1} {β : Type u_2} {γ : Type u_3} (f : Option α → β → γ) (as : List α) (bs : List β) : List γ

Right-biased version of List.zipWith. zipWithRight f as bs applies f to each pair aᵢ ∈ as and bᵢ ‌∈ bs‌∈ bs. If as is shorter than bs, f is applied to none for the remaining bᵢ.

zipWithRight prod.mk [1, 2] ['a'] = [(some 1, 'a')]
zipWithRight prod.mk [1] ['a', 'b'] = [(some 1, 'a'), (none, 'b')]
zipWithRight f as bs = (zipWithRight' f as bs).fst

Equations

• List.zipWithRight f as bs = List.zipWithLeft (flip f) bs as

@[inline]

def List.zipLeft {α : Type u_1} {β : Type u_2} : List α → List β → List (α × Option β)

Left-biased version of List.zip. zipLeft as bs returns the list of pairs (aᵢ, bᵢ) for aᵢ ∈ as and bᵢ ∈ bs. If bs is shorter than as, the remaining aᵢ are paired with none.

zipLeft [1, 2] ['a'] = [(1, some 'a'), (2, none)]
zipLeft [1] ['a', 'b'] = [(1, some 'a')]
zipLeft = zipWithLeft prod.mk

Equations

• List.zipLeft = List.zipWithLeft Prod.mk

@[inline]

def List.zipRight {α : Type u_1} {β : Type u_2} : List α → List β → List (Option α × β)

Right-biased version of List.zip. zipRight as bs returns the list of pairs (aᵢ, bᵢ) for aᵢ ∈ as and bᵢ ∈ bs. If as is shorter than bs, the remaining bᵢ are paired with none.

zipRight [1, 2] ['a'] = [(some 1, 'a')]
zipRight [1] ['a', 'b'] = [(some 1, 'a'), (none, 'b')]
zipRight = zipWithRight prod.mk

Equations

• List.zipRight = List.zipWithRight Prod.mk

@[inline]

def List.allSome {α : Type u_1} (l : List (Option α)) : Option (List α)

If all elements of xs are some xᵢ, allSome xs returns the xᵢ. Otherwise it returns none.

allSome [some 1, some 2] = some [1, 2]
allSome [some 1, none  ] = none

Equations

• l.allSome = List.mapM id l

def List.fillNones {α : Type u_1} : List (Option α) → List α → List α

fillNones xs ys replaces the nones in xs with elements of ys. If there are not enough ys to replace all the nones, the remaining nones are dropped from xs.

fillNones [none, some 1, none, none] [2, 3] = [2, 1, 3]

Equations

• [].fillNones x = []
• (some a :: as).fillNones x = a :: as.fillNones x
• (none :: as).fillNones [] = as.reduceOption
• (none :: as).fillNones (a :: as') = a :: as.fillNones as'

@[inline]

def List.fillNonesTR {α : Type u_1} (as : List (Option α)) (as' : List α) : List α

Tail-recursive version of fillNones.

Equations

• as.fillNonesTR as' = List.fillNonesTR.go as as' #[]

def List.fillNonesTR.go {α : Type u_1} : List (Option α) → List α → Array α → List α

Auxiliary for fillNonesTR: fillNonesTR.go as as' acc = acc.toList ++ fillNones as as'.

Equations

• List.fillNonesTR.go [] x✝ x = x.toList
• List.fillNonesTR.go (some a :: as) x✝ x = List.fillNonesTR.go as x✝ (x.push a)
• List.fillNonesTR.go (none :: as) [] x = List.filterMapTR.go id as x
• List.fillNonesTR.go (none :: as) (a :: as') x = List.fillNonesTR.go as as' (x.push a)

@[csimp]

theorem List.fillNones_eq_fillNonesTR : @List.fillNones = @List.fillNonesTR

theorem List.fillNones_eq_fillNonesTR.go (α : Type u_1) (acc : Array α) (as : List (Option α)) (as' : List α) : List.fillNonesTR.go as as' acc = acc.data ++ as.fillNones as'

def List.takeList {α : Type u_1} : List α → List Nat → List (List α) × List α

takeList as ns extracts successive sublists from as. For ns = n₁ ... nₘ, it first takes the n₁ initial elements from as, then the next n₂ ones, etc. It returns the sublists of as -- one for each nᵢ -- and the remaining elements of as. If as does not have at least as many elements as the sum of the nᵢ, the corresponding sublists will have less than nᵢ elements.

takeList ['a', 'b', 'c', 'd', 'e'] [2, 1, 1] = ([['a', 'b'], ['c'], ['d']], ['e'])
takeList ['a', 'b'] [3, 1] = ([['a', 'b'], []], [])

Equations

• x.takeList [] = ([], x)
• x.takeList (n :: ns) = match List.splitAt n x with | (xs₁, xs₂) => match xs₂.takeList ns with | (xss, rest) => (xs₁ :: xss, rest)

@[inline]

def List.takeListTR {α : Type u_1} (xs : List α) (ns : List Nat) : List (List α) × List α

Tail-recursive version of takeList.

Equations

• xs.takeListTR ns = List.takeListTR.go ns xs #[]

def List.takeListTR.go {α : Type u_1} : List Nat → List α → Array (List α) → List (List α) × List α

Auxiliary for takeListTR: takeListTR.go as as' acc = acc.toList ++ takeList as as'.

Equations

• List.takeListTR.go [] x✝ x = (x.toList, x✝)
• List.takeListTR.go (n :: ns) x✝ x = match List.splitAt n x✝ with | (xs₁, xs₂) => List.takeListTR.go ns xs₂ (x.push xs₁)

@[csimp]

theorem List.takeList_eq_takeListTR : @List.takeList = @List.takeListTR

theorem List.takeList_eq_takeListTR.go (α : Type u_1) (acc : Array (List α)) (ns : List Nat) (xs : List α) : List.takeListTR.go ns xs acc = match xs.takeList ns with | (l, r) => (acc.toList ++ l, r)

def List.toChunksAux {α : Type u_1} (n : Nat) : List α → Nat → List α × List (List α)

Auxliary definition used to define toChunks. toChunksAux n xs i returns (xs.take i, (xs.drop i).toChunks (n+1)), that is, the first i elements of xs, and the remaining elements chunked into sublists of length n+1.

Equations

• List.toChunksAux n [] x = ([], [])
• List.toChunksAux n (x_2 :: xs) 0 = match List.toChunksAux n xs n with | (l, L) => ([], (x_2 :: l) :: L)
• List.toChunksAux n (x_2 :: xs) i.succ = match List.toChunksAux n xs i with | (l, L) => (x_2 :: l, L)

def List.toChunks {α : Type u_1} : Nat → List α → List (List α)

xs.toChunks n splits the list into sublists of size at most n, such that (xs.toChunks n).join = xs.

[1, 2, 3, 4, 5, 6, 7, 8].toChunks 10 = [[1, 2, 3, 4, 5, 6, 7, 8]]
[1, 2, 3, 4, 5, 6, 7, 8].toChunks 3 = [[1, 2, 3], [4, 5, 6], [7, 8]]
[1, 2, 3, 4, 5, 6, 7, 8].toChunks 2 = [[1, 2], [3, 4], [5, 6], [7, 8]]
[1, 2, 3, 4, 5, 6, 7, 8].toChunks 0 = [[1, 2, 3, 4, 5, 6, 7, 8]]

Equations

• List.toChunks x✝ x = match x✝, x with | x, [] => [] | 0, xs => [xs] | n, x :: xs => List.toChunks.go n xs #[x] #[]

def List.toChunks.go {α : Type u_1} (n : Nat) : List α → Array α → Array (List α) → List (List α)

Auxliary definition used to define toChunks. toChunks.go xs acc₁ acc₂ pushes elements into acc₁ until it reaches size n, then it pushes the resulting list to acc₂ and continues until xs is exhausted.

Equations

• List.toChunks.go n [] x✝ x = (x.push x✝.toList).toList
• List.toChunks.go n (a :: t) x✝ x = if (x✝.size == n) = true then List.toChunks.go n t ((Array.mkEmpty n).push a) (x.push x✝.toList) else List.toChunks.go n t (x✝.push a) x

We add some n-ary versions of List.zipWith for functions with more than two arguments. These can also be written in terms of List.zip or List.zipWith. For example, zipWith₃ f xs ys zs could also be written as zipWith id (zipWith f xs ys) zs or as (zip xs <| zip ys zs).map fun ⟨x, y, z⟩ => f x y z.

def List.zipWith₃ {α : Type u_1} {β : Type u_2} {γ : Type u_3} {δ : Type u_4} (f : α → β → γ → δ) : List α → List β → List γ → List δ

Ternary version of List.zipWith.

Equations

• List.zipWith₃ f (x_3 :: xs) (y :: ys) (z :: zs) = f x_3 y z :: List.zipWith₃ f xs ys zs
• List.zipWith₃ f x✝¹ x✝ x = []

def List.zipWith₄ {α : Type u_1} {β : Type u_2} {γ : Type u_3} {δ : Type u_4} {ε : Type u_5} (f : α → β → γ → δ → ε) : List α → List β → List γ → List δ → List ε

Quaternary version of List.zipWith.

Equations

• List.zipWith₄ f (x_4 :: xs) (y :: ys) (z :: zs) (u :: us) = f x_4 y z u :: List.zipWith₄ f xs ys zs us
• List.zipWith₄ f x✝² x✝¹ x✝ x = []

def List.zipWith₅ {α : Type u_1} {β : Type u_2} {γ : Type u_3} {δ : Type u_4} {ε : Type u_5} {ζ : Type u_6} (f : α → β → γ → δ → ε → ζ) : List α → List β → List γ → List δ → List ε → List ζ

Quinary version of List.zipWith.

Equations

• List.zipWith₅ f (x_5 :: xs) (y :: ys) (z :: zs) (u :: us) (v :: vs) = f x_5 y z u v :: List.zipWith₅ f xs ys zs us vs
• List.zipWith₅ f x✝³ x✝² x✝¹ x✝ x = []

def List.mapWithPrefixSuffixAux {α : Type u_1} {β : Type u_2} (f : List α → α → List α → β) : List α → List α → List β

An auxiliary function for List.mapWithPrefixSuffix.

Equations

• List.mapWithPrefixSuffixAux f x [] = []
• List.mapWithPrefixSuffixAux f x (a :: l₂) = f x a l₂ :: List.mapWithPrefixSuffixAux f (x.concat a) l₂

def List.mapWithPrefixSuffix {α : Type u_1} {β : Type u_2} (f : List α → α → List α → β) (l : List α) : List β

List.mapWithPrefixSuffix f l maps f across a list l. For each a ∈ l with l = pref ++ [a] ++ suff, a is mapped to f pref a suff. Example: if f : list Nat → Nat → list Nat → β, List.mapWithPrefixSuffix f [1, 2, 3] will produce the list [f [] 1 [2, 3], f [1] 2 [3], f [1, 2] 3 []].

Equations

• List.mapWithPrefixSuffix f l = List.mapWithPrefixSuffixAux f [] l

def List.mapWithComplement {α : Type u_1} {β : Type u_2} (f : α → List α → β) : List α → List β

List.mapWithComplement f l is a variant of List.mapWithPrefixSuffix that maps f across a list l. For each a ∈ l with l = pref ++ [a] ++ suff, a is mapped to f a (pref ++ suff), i.e., the list input to f is l with a removed. Example: if f : Nat → list Nat → β, List.mapWithComplement f [1, 2, 3] will produce the list [f 1 [2, 3], f 2 [1, 3], f 3 [1, 2]].

Equations

• List.mapWithComplement f = List.mapWithPrefixSuffix fun (pref : List α) (a : α) (suff : List α) => f a (pref ++ suff)

def List.traverse {F : Type u_1 → Type u_2} {α : Type u_3} {β : Type u_1} [Applicative F] (f : α → F β) : List α → F (List β)

Map each element of a List to an action, evaluate these actions in order, and collect the results.

Equations

• List.traverse f [] = pure []
• List.traverse f (a :: l) = Seq.seq (List.cons <$> f a) fun (x : Unit) => List.traverse f l

inductive List.Perm {α : Type u_1} : List α → List α → Prop

Perm l₁ l₂ or l₁ ~ l₂ asserts that l₁ and l₂ are permutations of each other. This is defined by induction using pairwise swaps.

• nil: ∀ {α : Type u_1}, [].Perm []

  [] ~ []

• cons: ∀ {α : Type u_1} (x : α) {l₁ l₂ : List α}, l₁.Perm l₂ → (x :: l₁).Perm (x :: l₂)

  l₁ ~ l₂ → x::l₁ ~ x::l₂

• swap: ∀ {α : Type u_1} (x y : α) (l : List α), (y :: x :: l).Perm (x :: y :: l)

  x::y::l ~ y::x::l

• trans: ∀ {α : Type u_1} {l₁ l₂ l₃ : List α}, l₁.Perm l₂ → l₂.Perm l₃ → l₁.Perm l₃

  Perm is transitive.

def List.«term_~_» : Lean.TrailingParserDescr

Perm l₁ l₂ or l₁ ~ l₂ asserts that l₁ and l₂ are permutations of each other. This is defined by induction using pairwise swaps.

Equations

• List.«term_~_» = Lean.ParserDescr.trailingNode `List.term_~_ 50 50 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol " ~ ") (Lean.ParserDescr.cat `term 51))

def List.isPerm {α : Type u_1} [BEq α] : List α → List α → Bool

O(|l₁| * |l₂|). Computes whether l₁ is a permutation of l₂. See isPerm_iff for a characterization in terms of List.Perm.

Equations

• [].isPerm x = x.isEmpty
• (a :: t).isPerm x = (x.contains a && t.isPerm (x.erase a))

def List.Subperm {α : Type u_1} (l₁ : List α) (l₂ : List α) : Prop

Subperm l₁ l₂, denoted l₁ <+~ l₂, means that l₁ is a sublist of a permutation of l₂. This is an analogue of l₁ ⊆ l₂ which respects multiplicities of elements, and is used for the ≤ relation on multisets.

Equations

• l₁.Subperm l₂ = ∃ (l : List α), l.Perm l₁ ∧ l.Sublist l₂

def List.«term_<+~_» : Lean.TrailingParserDescr

Subperm l₁ l₂, denoted l₁ <+~ l₂, means that l₁ is a sublist of a permutation of l₂. This is an analogue of l₁ ⊆ l₂ which respects multiplicities of elements, and is used for the ≤ relation on multisets.

Equations

• List.«term_<+~_» = Lean.ParserDescr.trailingNode `List.term_<+~_ 50 50 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol " <+~ ") (Lean.ParserDescr.cat `term 51))

def List.isSubperm {α : Type u_1} [BEq α] (l₁ : List α) (l₂ : List α) : Bool

O(|l₁| * (|l₁| + |l₂|)). Computes whether l₁ is a sublist of a permutation of l₂. See isSubperm_iff for a characterization in terms of List.Subperm.

Equations

• l₁.isSubperm l₂ = decide (∀ (x : α), x ∈ l₁ → List.count x l₁ ≤ List.count x l₂)

def List.insertP {α : Type u_1} (p : α → Bool) (a : α) (l : List α) : List α

O(|l|). Inserts a in l right before the first element such that p is true, or at the end of the list if p always false on l.

Equations

• List.insertP p a l = List.insertP.loop p a l []

def List.insertP.loop {α : Type u_1} (p : α → Bool) (a : α) : List α → List α → List α

Inner loop for insertP. Tail recursive.

Equations

• List.insertP.loop p a [] x = (a :: x).reverseAux []
• List.insertP.loop p a (a_1 :: t) x = bif p a_1 then (a :: x).reverseAux (a_1 :: t) else List.insertP.loop p a t (a_1 :: x)

def List.merge {α : Type u_1} (s : α → α → Bool) (l : List α) (r : List α) : List α

O(|l| + |r|). Merge two lists using s as a switch.

Equations

• List.merge s l r = List.merge.loop s l r []

@[irreducible]

def List.merge.loop {α : Type u_1} (s : α → α → Bool) : List α → List α → List α → List α

Inner loop for List.merge. Tail recursive.

Equations

• List.merge.loop s [] x✝ x = x.reverseAux x✝
• List.merge.loop s x✝ [] x = x.reverseAux x✝
• List.merge.loop s (a :: l) (b :: r) x = bif s a b then List.merge.loop s l (b :: r) (a :: x) else List.merge.loop s (a :: l) r (b :: x)