Tail recursive implementations for List definitions.

Many of the proofs require theorems about Array, so these are in a separate file to minimize imports.

@[inline]

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

Tail recursive version of erase.

Equations

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

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

Auxiliary for setTR: setTR.go l a xs n acc = acc.toList ++ set xs a, unless n ≥ l.length in which case it returns l

Equations

• List.setTR.go l a [] x✝ x = l
• List.setTR.go l a (head :: xs) 0 x = x.toListAppend (a :: xs)
• List.setTR.go l a (x_3 :: xs) n.succ x = List.setTR.go l a xs n (x.push x_3)

@[csimp]

theorem List.set_eq_setTR : @List.set = @List.setTR

theorem List.set_eq_setTR.go (α : Type u_1) (l : List α) (a : α) (acc : Array α) (xs : List α) (n : Nat) : l = acc.data ++ xs → List.setTR.go l a xs n acc = acc.data ++ xs.set n a

@[inline]

def List.eraseTR {α : Type u_1} [BEq α] (l : List α) (a : α) : List α

Tail recursive version of erase.

Equations

• l.eraseTR a = List.eraseTR.go l a l #[]

def List.eraseTR.go {α : Type u_1} [BEq α] (l : List α) (a : α) : List α → Array α → List α

Auxiliary for eraseTR: eraseTR.go l a xs acc = acc.toList ++ erase xs a, unless a is not present in which case it returns l

Equations

• List.eraseTR.go l a [] x = l
• List.eraseTR.go l a (x_2 :: xs) x = bif x_2 == a then x.toListAppend xs else List.eraseTR.go l a xs (x.push x_2)

@[csimp]

theorem List.erase_eq_eraseTR : @List.erase = @List.eraseTR

@[inline]

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

Tail recursive version of eraseIdx.

Equations

• l.eraseIdxTR n = List.eraseIdxTR.go l l n #[]

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

Auxiliary for eraseIdxTR: eraseIdxTR.go l n xs acc = acc.toList ++ eraseIdx xs a, unless a is not present in which case it returns l

Equations

• List.eraseIdxTR.go l [] x✝ x = l
• List.eraseIdxTR.go l (head :: xs) 0 x = x.toListAppend xs
• List.eraseIdxTR.go l (x_3 :: xs) n.succ x = List.eraseIdxTR.go l xs n (x.push x_3)

@[csimp]

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

@[inline]

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

Tail recursive version of bind.

Equations

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

@[specialize #[]]

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

Auxiliary for bind: bind.go f as = acc.toList ++ bind f as

Equations

• List.bindTR.go f [] x = x.toList
• List.bindTR.go f (x_2 :: xs) x = List.bindTR.go f xs (x ++ f x_2)

@[csimp]

theorem List.bind_eq_bindTR : @List.bind = @List.bindTR

theorem List.bind_eq_bindTR.go (α : Type u_2) (β : Type u_1) (f : α → List β) (as : List α) (acc : Array β) : List.bindTR.go f as acc = acc.data ++ as.bind f

@[inline]

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

Tail recursive version of join.

Equations

• l.joinTR = l.bindTR id

@[csimp]

theorem List.join_eq_joinTR : @List.join = @List.joinTR

@[inline]

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

Tail recursive version of filterMap.

Equations

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

@[specialize #[]]

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

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

Equations

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

@[csimp]

theorem List.filterMap_eq_filterMapTR : @List.filterMap = @List.filterMapTR

theorem List.filterMap_eq_filterMapTR.go (α : Type u_2) (β : Type u_1) (f : α → Option β) (as : List α) (acc : Array β) : List.filterMapTR.go f as acc = acc.data ++ List.filterMap f as

@[inline]

def List.replaceTR {α : Type u_1} [BEq α] (l : List α) (b : α) (c : α) : List α

Tail recursive version of replace.

Equations

• l.replaceTR b c = List.replaceTR.go l b c l #[]

@[specialize #[]]

def List.replaceTR.go {α : Type u_1} [BEq α] (l : List α) (b : α) (c : α) : List α → Array α → List α

Auxiliary for replace: replace.go l b c xs acc = acc.toList ++ replace xs b c, unless b is not found in xs in which case it returns l.

Equations

• List.replaceTR.go l b c [] x = l
• List.replaceTR.go l b c (x_2 :: xs) x = bif x_2 == b then x.toListAppend (c :: xs) else List.replaceTR.go l b c xs (x.push x_2)

@[csimp]

theorem List.replace_eq_replaceTR : @List.replace = @List.replaceTR

@[inline]

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

Tail recursive version of take.

Equations

• List.takeTR n l = List.takeTR.go l l n #[]

@[specialize #[]]

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

Auxiliary for take: take.go l xs n acc = acc.toList ++ take n xs, unless n ≥ xs.length in which case it returns l.

Equations

• List.takeTR.go l [] x✝ x = l
• List.takeTR.go l (head :: xs) 0 x = x.toList
• List.takeTR.go l (x_3 :: xs) n.succ x = List.takeTR.go l xs n (x.push x_3)

@[csimp]

theorem List.take_eq_takeTR : @List.take = @List.takeTR

@[inline]

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

Tail recursive version of takeWhile.

Equations

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

@[specialize #[]]

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

Auxiliary for takeWhile: takeWhile.go p l xs acc = acc.toList ++ takeWhile p xs, unless no element satisfying p is found in xs in which case it returns l.

Equations

• List.takeWhileTR.go p l [] x = l
• List.takeWhileTR.go p l (x_2 :: xs) x = bif p x_2 then List.takeWhileTR.go p l xs (x.push x_2) else x.toList

@[csimp]

theorem List.takeWhile_eq_takeWhileTR : @List.takeWhile = @List.takeWhileTR

@[specialize #[]]

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

Tail recursive version of foldr.

Equations

• List.foldrTR f init l = Array.foldr f init (List.toArray l) (List.toArray l).size

@[csimp]

theorem List.foldr_eq_foldrTR : @List.foldr = @List.foldrTR

@[inline]

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

Tail recursive version of zipWith.

Equations

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

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

Auxiliary for zipWith: zipWith.go f as bs acc = acc.toList ++ zipWith f as bs

Equations

• List.zipWithTR.go f (a :: as) (b :: bs) x = List.zipWithTR.go f as bs (x.push (f a b))
• List.zipWithTR.go f x✝¹ x✝ x = x.toList

@[csimp]

theorem List.zipWith_eq_zipWithTR : @List.zipWith = @List.zipWithTR

theorem List.zipWith_eq_zipWithTR.go (α : Type u_3) (β : Type u_2) (γ : Type u_1) (f : α → β → γ) (as : List α) (bs : List β) (acc : Array γ) : List.zipWithTR.go f as bs acc = acc.data ++ List.zipWith f as bs

def List.unzipTR {α : Type u_1} {β : Type u_2} (l : List (α × β)) : List α × List β

Tail recursive version of unzip.

Equations

• l.unzipTR = List.foldr (fun (x : α × β) (x_1 : List α × List β) => match x with | (a, b) => match x_1 with | (al, bl) => (a :: al, b :: bl)) ([], []) l

@[csimp]

theorem List.unzip_eq_unzipTR : @List.unzip = @List.unzipTR

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

Tail recursive version of enumFrom.

Equations

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

@[csimp]

theorem List.enumFrom_eq_enumFromTR : @List.enumFrom = @List.enumFromTR

theorem List.enumFrom_eq_enumFromTR.go (α : Type u_1) (l : List α) (n : Nat) : let f := fun (a : α) (x : Nat × List (Nat × α)) => match x with | (n, acc) => (n - 1, (n - 1, a) :: acc); List.foldr f (n + l.length, []) l = (n, List.enumFrom n l)

theorem List.replicateTR_loop_eq : ∀ {α : Type u_1} {a : α} {acc : List α} (n : Nat), List.replicateTR.loop a n acc = List.replicate n a ++ acc

@[inline]

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

Tail recursive version of dropLast.

Equations

• l.dropLastTR = (List.toArray l).pop.toList

@[csimp]

theorem List.dropLast_eq_dropLastTR : @List.dropLast = @List.dropLastTR

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

Tail recursive version of intersperse.

Equations

• List.intersperseTR sep x = match x with | [] => [] | [x] => [x] | x :: y :: xs => x :: sep :: y :: List.foldr (fun (a : α) (r : List α) => sep :: a :: r) [] xs

@[csimp]

theorem List.intersperse_eq_intersperseTR : @List.intersperse = @List.intersperseTR

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

Tail recursive version of intercalate.

Equations

• sep.intercalateTR x = match x with | [] => [] | [x] => x | x :: xs => List.intercalateTR.go (List.toArray sep) x xs #[]

def List.intercalateTR.go {α : Type u_1} (sep : Array α) : List α → List (List α) → Array α → List α

Auxiliary for intercalateTR: intercalateTR.go sep x xs acc = acc.toList ++ intercalate sep.toList (x::xs)

Equations

• List.intercalateTR.go sep x✝ [] x = x.toListAppend x✝
• List.intercalateTR.go sep x✝ (y :: xs) x = List.intercalateTR.go sep y xs (x ++ x✝ ++ sep)

@[csimp]

theorem List.intercalate_eq_intercalateTR : @List.intercalate = @List.intercalateTR

theorem List.intercalate_eq_intercalateTR.go (α : Type u_1) (sep : List α) {acc : Array α} {x : List α} (xs : List (List α)) : List.intercalateTR.go (List.toArray sep) x xs acc = acc.data ++ (List.intersperse sep (x :: xs)).join