Bootstrapping theorems for lists

These are theorems used in the definitions of Std.Data.List.Basic. New theorems should be added to Std.Data.List.Lemmas if they are not needed by the bootstrap.

@[simp]

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

@[simp]

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

@[simp]

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

@[simp]

theorem List.get_cons_zero : ∀ {α : Type u_1} {a : α} {l : List α}, List.get (a :: l) 0 = a

@[simp]

theorem List.head?_nil {α : Type u_1} : List.head? [] = none

@[simp]

theorem List.head?_cons {α : Type u_1} {a : α} {l : List α} : List.head? (a :: l) = some a

@[simp]

theorem List.headD_nil {α : Type u_1} {d : α} : List.headD [] d = d

@[simp]

theorem List.headD_cons {α : Type u_1} {a : α} {l : List α} {d : α} : List.headD (a :: l) d = a

@[simp]

theorem List.head_cons {α : Type u_1} {a : α} {l : List α} {h : a :: l ≠ []} : List.head (a :: l) h = a

@[simp]

theorem List.tail?_nil {α : Type u_1} : List.tail? [] = none

@[simp]

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

@[simp]

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

@[simp]

theorem List.tailD_nil {α : Type u_1} {l' : List α} : List.tailD [] l' = l'

@[simp]

theorem List.tailD_cons {α : Type u_1} {a : α} {l : List α} {l' : List α} : List.tailD (a :: l) l' = l

@[simp]

theorem List.any_nil : ∀ {α : Type u_1} {f : α → Bool}, List.any [] f = false

@[simp]

theorem List.any_cons : ∀ {α : Type u_1} {a : α} {l : List α} {f : α → Bool}, List.any (a :: l) f = (f a || List.any l f)

@[simp]

theorem List.all_nil : ∀ {α : Type u_1} {f : α → Bool}, List.all [] f = true

@[simp]

theorem List.all_cons : ∀ {α : Type u_1} {a : α} {l : List α} {f : α → Bool}, List.all (a :: l) f = (f a && List.all l f)

@[simp]

theorem List.or_nil : List.or [] = false

@[simp]

theorem List.or_cons {a : Bool} {l : List Bool} : List.or (a :: l) = (a || List.or l)

@[simp]

theorem List.and_nil : List.and [] = true

@[simp]

theorem List.and_cons {a : Bool} {l : List Bool} : List.and (a :: l) = (a && List.and l)

length

theorem List.eq_nil_of_length_eq_zero : ∀ {α : Type u_1} {l : List α}, List.length l = 0 → l = []

theorem List.ne_nil_of_length_eq_succ : ∀ {α : Type u_1} {l : List α} {n : Nat}, List.length l = Nat.succ n → l ≠ []

theorem List.length_eq_zero : ∀ {α : Type u_1} {l : List α}, List.length l = 0 ↔ l = []

append

@[simp]

theorem List.singleton_append : ∀ {α : Type u_1} {x : α} {l : List α}, [x] ++ l = x :: l

theorem List.append_inj {α : Type u_1} {s₁ : List α} {s₂ : List α} {t₁ : List α} {t₂ : List α} : s₁ ++ t₁ = s₂ ++ t₂ → List.length s₁ = List.length s₂ → s₁ = s₂ ∧ t₁ = t₂

theorem List.append_inj_right : ∀ {α : Type u_1} {s₁ t₁ s₂ t₂ : List α}, s₁ ++ t₁ = s₂ ++ t₂ → List.length s₁ = List.length s₂ → t₁ = t₂

theorem List.append_inj_left : ∀ {α : Type u_1} {s₁ t₁ s₂ t₂ : List α}, s₁ ++ t₁ = s₂ ++ t₂ → List.length s₁ = List.length s₂ → s₁ = s₂

theorem List.append_inj' : ∀ {α : Type u_1} {s₁ t₁ s₂ t₂ : List α}, s₁ ++ t₁ = s₂ ++ t₂ → List.length t₁ = List.length t₂ → s₁ = s₂ ∧ t₁ = t₂

theorem List.append_inj_right' : ∀ {α : Type u_1} {s₁ t₁ s₂ t₂ : List α}, s₁ ++ t₁ = s₂ ++ t₂ → List.length t₁ = List.length t₂ → t₁ = t₂

theorem List.append_inj_left' : ∀ {α : Type u_1} {s₁ t₁ s₂ t₂ : List α}, s₁ ++ t₁ = s₂ ++ t₂ → List.length t₁ = List.length t₂ → s₁ = s₂

theorem List.append_right_inj {α : Type u_1} {t₁ : List α} {t₂ : List α} (s : List α) : s ++ t₁ = s ++ t₂ ↔ t₁ = t₂

theorem List.append_left_inj {α : Type u_1} {s₁ : List α} {s₂ : List α} (t : List α) : s₁ ++ t = s₂ ++ t ↔ s₁ = s₂

map

@[simp]

theorem List.map_nil {α : Type u_1} {β : Type u_2} {f : α → β} : List.map f [] = []

@[simp]

theorem List.map_cons {α : Type u_1} {β : Type u_2} (f : α → β) (a : α) (l : List α) : List.map f (a :: l) = f a :: List.map f l

@[simp]

theorem List.map_append {α : Type u_1} {β : Type u_2} (f : α → β) (l₁ : List α) (l₂ : List α) : List.map f (l₁ ++ l₂) = List.map f l₁ ++ List.map f l₂

@[simp]

theorem List.map_id {α : Type u_1} (l : List α) : List.map id l = l

@[simp]

theorem List.map_map {β : Type u_1} {γ : Type u_2} {α : Type u_3} (g : β → γ) (f : α → β) (l : List α) : List.map g (List.map f l) = List.map (g ∘ f) l

bind

@[simp]

theorem List.nil_bind {α : Type u_1} {β : Type u_2} (f : α → List β) : List.bind [] f = []

@[simp]

theorem List.cons_bind {α : Type u_1} {β : Type u_2} (x : α) (xs : List α) (f : α → List β) : List.bind (x :: xs) f = f x ++ List.bind xs f

@[simp]

theorem List.append_bind {α : Type u_1} {β : Type u_2} (xs : List α) (ys : List α) (f : α → List β) : List.bind (xs ++ ys) f = List.bind xs f ++ List.bind ys f

@[simp]

theorem List.bind_id {α : Type u_1} (l : List (List α)) : List.bind l id = List.join l

join

@[simp]

theorem List.join_nil {α : Type u_1} : List.join [] = []

@[simp]

theorem List.join_cons : ∀ {α : Type u_1} {l : List α} {ls : List (List α)}, List.join (l :: ls) = l ++ List.join ls

bounded quantifiers over Lists

theorem List.forall_mem_cons {α : Type u_1} {p : α → Prop} {a : α} {l : List α} : ((x : α) → x ∈ a :: l → p x) ↔ p a ∧ ((x : α) → x ∈ l → p x)

reverse

@[simp]

theorem List.reverseAux_nil : ∀ {α : Type u_1} {r : List α}, List.reverseAux [] r = r

@[simp]

theorem List.reverseAux_cons : ∀ {α : Type u_1} {a : α} {l r : List α}, List.reverseAux (a :: l) r = List.reverseAux l (a :: r)

theorem List.reverseAux_eq {α : Type u_1} (as : List α) (bs : List α) : List.reverseAux as bs = List.reverse as ++ bs

theorem List.reverse_map {α : Type u_1} {β : Type u_2} (f : α → β) (l : List α) : List.reverse (List.map f l) = List.map f (List.reverse l)

take and drop

@[simp]

theorem List.take_append_drop {α : Type u_1} (n : Nat) (l : List α) : List.take n l ++ List.drop n l = l

@[simp]

theorem List.length_drop {α : Type u_1} (i : Nat) (l : List α) : List.length (List.drop i l) = List.length l - i

theorem List.drop_length_le {α : Type u_1} {i : Nat} {l : List α} (h : List.length l ≤ i) : List.drop i l = []

theorem List.take_length_le {α : Type u_1} {i : Nat} {l : List α} (h : List.length l ≤ i) : List.take i l = l

@[simp]

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

@[simp]

theorem List.take_nil {α : Type u_1} {i : Nat} : List.take i [] = []

@[simp]

theorem List.take_cons_succ : ∀ {α : Type u_1} {a : α} {as : List α} {i : Nat}, List.take (i + 1) (a :: as) = a :: List.take i as

@[simp]

theorem List.drop_zero {α : Type u_1} (l : List α) : List.drop 0 l = l

@[simp]

theorem List.drop_succ_cons : ∀ {α : Type u_1} {a : α} {l : List α} {n : Nat}, List.drop (n + 1) (a :: l) = List.drop n l

@[simp]

theorem List.drop_length {α : Type u_1} (l : List α) : List.drop (List.length l) l = []

@[simp]

theorem List.take_length {α : Type u_1} (l : List α) : List.take (List.length l) l = l

theorem List.take_concat_get {α : Type u_1} (l : List α) (i : Nat) (h : i < List.length l) : List.concat (List.take i l) l[i] = List.take (i + 1) l

theorem List.reverse_concat {α : Type u_1} (l : List α) (a : α) : List.reverse (List.concat l a) = a :: List.reverse l

foldlM and foldrM

@[simp]

theorem List.foldlM_reverse {m : Type u_1 → Type u_2} {α : Type u_3} {β : Type u_1} [Monad m] (l : List α) (f : β → α → m β) (b : β) : List.foldlM f b (List.reverse l) = List.foldrM (fun x y => f y x) b l

@[simp]

theorem List.foldlM_nil {m : Type u_1 → Type u_2} {β : Type u_1} {α : Type u_3} [Monad m] (f : β → α → m β) (b : β) : List.foldlM f b [] = pure b

@[simp]

theorem List.foldlM_cons {m : Type u_1 → Type u_2} {β : Type u_1} {α : Type u_3} [Monad m] (f : β → α → m β) (b : β) (a : α) (l : List α) : List.foldlM f b (a :: l) = do let init ← f b a List.foldlM f init l

@[simp]

theorem List.foldlM_append {m : Type u_1 → Type u_2} {β : Type u_1} {α : Type u_3} [Monad m] [LawfulMonad m] (f : β → α → m β) (b : β) (l : List α) (l' : List α) : List.foldlM f b (l ++ l') = do let init ← List.foldlM f b l List.foldlM f init l'

@[simp]

theorem List.foldrM_nil {m : Type u_1 → Type u_2} {α : Type u_3} {β : Type u_1} [Monad m] (f : α → β → m β) (b : β) : List.foldrM f b [] = pure b

@[simp]

theorem List.foldrM_cons {m : Type u_1 → Type u_2} {α : Type u_3} {β : Type u_1} [Monad m] [LawfulMonad m] (a : α) (l : List α) (f : α → β → m β) (b : β) : List.foldrM f b (a :: l) = List.foldrM f b l >>= f a

@[simp]

theorem List.foldrM_reverse {m : Type u_1 → Type u_2} {α : Type u_3} {β : Type u_1} [Monad m] (l : List α) (f : α → β → m β) (b : β) : List.foldrM f b (List.reverse l) = List.foldlM (fun x y => f y x) b l

theorem List.foldl_eq_foldlM {β : Type u_1} {α : Type u_2} (f : β → α → β) (b : β) (l : List α) : List.foldl f b l = List.foldlM f b l

theorem List.foldr_eq_foldrM {α : Type u_1} {β : Type u_2} (f : α → β → β) (b : β) (l : List α) : List.foldr f b l = List.foldrM f b l

foldl and foldr

@[simp]

theorem List.foldl_reverse {α : Type u_1} {β : Type u_2} (l : List α) (f : β → α → β) (b : β) : List.foldl f b (List.reverse l) = List.foldr (fun x y => f y x) b l

@[simp]

theorem List.foldr_reverse {α : Type u_1} {β : Type u_2} (l : List α) (f : α → β → β) (b : β) : List.foldr f b (List.reverse l) = List.foldl (fun x y => f y x) b l

@[simp]

theorem List.foldrM_append {m : Type u_1 → Type u_2} {α : Type u_3} {β : Type u_1} [Monad m] [LawfulMonad m] (f : α → β → m β) (b : β) (l : List α) (l' : List α) : List.foldrM f b (l ++ l') = do let init ← List.foldrM f b l' List.foldrM f init l

@[simp]

theorem List.foldl_append {α : Type u_1} {β : Type u_2} (f : β → α → β) (b : β) (l : List α) (l' : List α) : List.foldl f b (l ++ l') = List.foldl f (List.foldl f b l) l'

@[simp]

theorem List.foldr_append {α : Type u_1} {β : Type u_2} (f : α → β → β) (b : β) (l : List α) (l' : List α) : List.foldr f b (l ++ l') = List.foldr f (List.foldr f b l') l

@[simp]

theorem List.foldl_nil : ∀ {α : Type u_1} {β : Type u_2} {f : α → β → α} {b : α}, List.foldl f b [] = b

@[simp]

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

@[simp]

theorem List.foldr_nil : ∀ {α : Type u_1} {α_1 : Type u_2} {f : α → α_1 → α_1} {b : α_1}, List.foldr f b [] = b

@[simp]

theorem List.foldr_cons {α : Type u_1} {a : α} : ∀ {α : Type u_2} {f : α → α → α} {b : α} (l : List α), List.foldr f b (a :: l) = f a (List.foldr f b l)

@[simp]

theorem List.foldr_self_append {α : Type u_1} {l' : List α} (l : List α) : List.foldr List.cons l' l = l ++ l'

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

mapM

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

Alternate (non-tail-recursive) form of mapM for proofs.

Equations

• List.mapM' f [] = pure []
• List.mapM' f (a :: l) = do let __do_lift ← f a let __do_lift_1 ← List.mapM' f l pure (__do_lift :: __do_lift_1)

@[simp]

theorem List.mapM'_nil {m : Type u_1 → Type u_2} {α : Type u_3} {β : Type u_1} [Monad m] {f : α → m β} : List.mapM' f [] = pure []

@[simp]

theorem List.mapM'_cons {m : Type u_1 → Type u_2} {α : Type u_3} {β : Type u_1} {a : α} {l : List α} [Monad m] {f : α → m β} : List.mapM' f (a :: l) = do let __do_lift ← f a let __do_lift_1 ← List.mapM' f l pure (__do_lift :: __do_lift_1)

theorem List.mapM'_eq_mapM {m : Type u_1 → Type u_2} {α : Type u_3} {β : Type u_1} [Monad m] [LawfulMonad m] (f : α → m β) (l : List α) : List.mapM' f l = List.mapM f l

theorem List.mapM'_eq_mapM.go {m : Type u_1 → Type u_2} {α : Type u_3} {β : Type u_1} [Monad m] [LawfulMonad m] (f : α → m β) (l : List α) (acc : List β) : List.mapM.loop f l acc = do let __do_lift ← List.mapM' f l pure (List.reverse acc ++ __do_lift)

@[simp]

theorem List.mapM_nil {m : Type u_1 → Type u_2} {α : Type u_3} {β : Type u_1} [Monad m] (f : α → m β) : List.mapM f [] = pure []

@[simp]

theorem List.mapM_cons {m : Type u_1 → Type u_2} {α : Type u_3} {β : Type u_1} {a : α} {l : List α} [Monad m] [LawfulMonad m] (f : α → m β) : List.mapM f (a :: l) = do let __do_lift ← f a let __do_lift_1 ← List.mapM f l pure (__do_lift :: __do_lift_1)

@[simp]

theorem List.mapM_append {m : Type u_1 → Type u_2} {α : Type u_3} {β : Type u_1} [Monad m] [LawfulMonad m] (f : α → m β) {l₁ : List α} {l₂ : List α} : List.mapM f (l₁ ++ l₂) = do let __do_lift ← List.mapM f l₁ let __do_lift_1 ← List.mapM f l₂ pure (__do_lift ++ __do_lift_1)

forM

@[simp]

theorem List.forM_nil' {m : Type u_1 → Type u_2} {α : Type u_3} {f : α → m PUnit} [Monad m] : List.forM [] f = pure PUnit.unit

@[simp]

theorem List.forM_cons' {m : Type u_1 → Type u_2} : ∀ {α : Type u_3} {a : α} {as : List α} {f : α → m PUnit} [inst : Monad m], List.forM (a :: as) f = do f a List.forM as f

eraseIdx

@[simp]

theorem List.eraseIdx_nil {α : Type u_1} {i : Nat} : List.eraseIdx [] i = []

@[simp]

theorem List.eraseIdx_cons_zero : ∀ {α : Type u_1} {a : α} {as : List α}, List.eraseIdx (a :: as) 0 = as

@[simp]

theorem List.eraseIdx_cons_succ : ∀ {α : Type u_1} {a : α} {as : List α} {i : Nat}, List.eraseIdx (a :: as) (i + 1) = a :: List.eraseIdx as i

find?

@[simp]

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

theorem List.find?_cons : ∀ {α : Type u_1} {a : α} {as : List α} {p : α → Bool}, List.find? p (a :: as) = match p a with | true => some a | false => List.find? p as

findSome?

@[simp]

theorem List.findSome?_nil {α : Type u_1} : ∀ {α : Type u_2} {f : α → Option α}, List.findSome? f [] = none

theorem List.findSome?_cons {α : Type u_1} {β : Type u_2} {a : α} {as : List α} {f : α → Option β} : List.findSome? f (a :: as) = match f a with | some b => some b | none => List.findSome? f as

replace

@[simp]

theorem List.replace_nil {α : Type u_1} {a : α} {b : α} [BEq α] : List.replace [] a b = []

theorem List.replace_cons {α : Type u_1} {as : List α} {b : α} {c : α} [BEq α] {a : α} : List.replace (a :: as) b c = match a == b with | true => c :: as | false => a :: List.replace as b c

@[simp]

theorem List.replace_cons_self {α : Type u_1} {as : List α} {b : α} [BEq α] [LawfulBEq α] {a : α} : List.replace (a :: as) a b = b :: as

elem

@[simp]

theorem List.elem_nil {α : Type u_1} {a : α} [BEq α] : List.elem a [] = false

theorem List.elem_cons {α : Type u_1} {as : List α} {b : α} [BEq α] {a : α} : List.elem b (a :: as) = match b == a with | true => true | false => List.elem b as

@[simp]

theorem List.elem_cons_self {α : Type u_1} {as : List α} [BEq α] [LawfulBEq α] {a : α} : List.elem a (a :: as) = true

lookup

@[simp]

theorem List.lookup_nil {α : Type u_1} {β : Type u_2} {a : α} [BEq α] : List.lookup a [] = none

theorem List.lookup_cons {α : Type u_1} : ∀ {β : Type u_2} {b : β} {es : List (α × β)} {a : α} [inst : BEq α] {k : α}, List.lookup a ((k, b) :: es) = match a == k with | true => some b | false => List.lookup a es

@[simp]

theorem List.lookup_cons_self {α : Type u_1} : ∀ {β : Type u_2} {b : β} {es : List (α × β)} [inst : BEq α] [inst_1 : LawfulBEq α] {k : α}, List.lookup k ((k, b) :: es) = some b

zipWith

@[simp]

theorem List.zipWith_nil_left {α : Type u_1} {β : Type u_2} {γ : Type u_3} {l : List β} {f : α → β → γ} : List.zipWith f [] l = []

@[simp]

theorem List.zipWith_nil_right {α : Type u_1} {β : Type u_2} {γ : Type u_3} {l : List α} {f : α → β → γ} : List.zipWith f l [] = []

@[simp]

theorem List.zipWith_cons_cons {α : Type u_1} {β : Type u_2} {γ : Type u_3} {a : α} {as : List α} {b : β} {bs : List β} {f : α → β → γ} : List.zipWith f (a :: as) (b :: bs) = f a b :: List.zipWith f as bs

zip

@[simp]

theorem List.zip_nil_left {α : Type u_1} {β : Type u_2} {l : List β} : List.zip [] l = []

@[simp]

theorem List.zip_nil_right {α : Type u_1} {l : List α} {β : Type u_2} : List.zip l [] = []

@[simp]

theorem List.zip_cons_cons : ∀ {α : Type u_1} {a : α} {as : List α} {α_1 : Type u_2} {b : α_1} {bs : List α_1}, List.zip (a :: as) (b :: bs) = (a, b) :: List.zip as bs

unzip

@[simp]

theorem List.unzip_nil {α : Type u_1} {β : Type u_2} : List.unzip [] = ([], [])

@[simp]

theorem List.unzip_cons {α : Type u_1} {β : Type u_2} {t : List (α × β)} {h : α × β} : List.unzip (h :: t) = match List.unzip t with | (al, bl) => (h.fst :: al, h.snd :: bl)

enumFrom

@[simp]

theorem List.enumFrom_nil {α : Type u_1} {i : Nat} : List.enumFrom i [] = []

@[simp]

theorem List.enumFrom_cons : ∀ {α : Type u_1} {a : α} {as : List α} {i : Nat}, List.enumFrom i (a :: as) = (i, a) :: List.enumFrom (i + 1) as

iota

@[simp]

theorem List.iota_zero : List.iota 0 = []

@[simp]

theorem List.iota_succ {i : Nat} : List.iota (i + 1) = (i + 1) :: List.iota i

intersperse

@[simp]

theorem List.intersperse_nil {α : Type u_1} (sep : α) : List.intersperse sep [] = []

@[simp]

theorem List.intersperse_single {α : Type u_1} {x : α} (sep : α) : List.intersperse sep [x] = [x]

@[simp]

theorem List.intersperse_cons₂ {α : Type u_1} {x : α} {y : α} {zs : List α} (sep : α) : List.intersperse sep (x :: y :: zs) = x :: sep :: List.intersperse sep (y :: zs)

isPrefixOf

@[simp]

theorem List.isPrefixOf_nil_left {α : Type u_1} {l : List α} [BEq α] : List.isPrefixOf [] l = true

@[simp]

theorem List.isPrefixOf_cons_nil {α : Type u_1} {a : α} {as : List α} [BEq α] : List.isPrefixOf (a :: as) [] = false

theorem List.isPrefixOf_cons₂ {α : Type u_1} {as : List α} {b : α} {bs : List α} [BEq α] {a : α} : List.isPrefixOf (a :: as) (b :: bs) = (a == b && List.isPrefixOf as bs)

@[simp]

theorem List.isPrefixOf_cons₂_self {α : Type u_1} {as : List α} {bs : List α} [BEq α] [LawfulBEq α] {a : α} : List.isPrefixOf (a :: as) (a :: bs) = List.isPrefixOf as bs

isEqv

@[simp]

theorem List.isEqv_nil_nil {α : Type u_1} {eqv : α → α → Bool} : List.isEqv [] [] eqv = true

@[simp]

theorem List.isEqv_nil_cons {α : Type u_1} {a : α} {as : List α} {eqv : α → α → Bool} : List.isEqv [] (a :: as) eqv = false

@[simp]

theorem List.isEqv_cons_nil {α : Type u_1} {a : α} {as : List α} {eqv : α → α → Bool} : List.isEqv (a :: as) [] eqv = false

theorem List.isEqv_cons₂ : ∀ {α : Type u_1} {a : α} {as : List α} {b : α} {bs : List α} {eqv : α → α → Bool}, List.isEqv (a :: as) (b :: bs) eqv = (eqv a b && List.isEqv as bs eqv)

dropLast

@[simp]

theorem List.dropLast_nil {α : Type u_1} : List.dropLast [] = []

@[simp]

theorem List.dropLast_single : ∀ {α : Type u_1} {x : α}, List.dropLast [x] = []

@[simp]

theorem List.dropLast_cons₂ : ∀ {α : Type u_1} {x y : α} {zs : List α}, List.dropLast (x :: y :: zs) = x :: List.dropLast (y :: zs)