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.

ink

@[simp]

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

ink

@[simp]

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

ink

@[simp]

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

ink

@[simp]

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

ink

@[simp]

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

ink

@[simp]

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

ink

@[simp]

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

ink

@[simp]

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

ink

@[simp]

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

ink

@[simp]

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

ink

@[simp]

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

ink

@[simp]

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

ink

@[simp]

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

ink

@[simp]

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

ink

@[simp]

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

ink

@[simp]

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

length

ink

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

ink

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

ink

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

append

ink

@[simp]

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

ink

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₂

ink

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₂

ink

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₂

ink

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₂

ink

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₂

ink

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₂

ink

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

ink

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

map

ink

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

ink

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

ink

@[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₂

ink

@[simp]

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

ink

@[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

ink

@[simp]

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

ink

@[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

ink

@[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

bind

ink

@[simp]

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

reverse

ink

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

ink

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

ink

@[simp]

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

ink

@[simp]

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

ink

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

ink

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

ink

@[simp]

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

ink

@[simp]

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

ink

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

ink

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

ink

@[simp]

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

ink

@[simp]

theorem List.foldlM_append {m : Type u_1 → Type u_2} {β : Type u_1} {α : Type u_3} [inst : Monad m] [inst : 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'

ink

@[simp]

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

ink

@[simp]

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

ink

@[simp]

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

ink

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

ink

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

ink

@[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

ink

@[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

ink

@[simp]

theorem List.foldrM_append {m : Type u_1 → Type u_2} {α : Type u_3} {β : Type u_1} [inst : Monad m] [inst : 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

ink

@[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'

ink

@[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

ink

@[simp]

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

ink

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

ink

def List.mapM' {m : Type u_1 → Type u_2} {α : Type u_3} {β : Type u_1} [inst : 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)

ink

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

ink

theorem List.mapM'_eq_mapM.go {m : Type u_1 → Type u_2} {α : Type u_3} {β : Type u_1} [inst : Monad m] [inst : 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)

ink

@[simp]

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

ink

@[simp]

theorem List.mapM_cons {m : Type u_1 → Type u_2} {α : Type u_3} {β : Type u_1} {a : α} {l : List α} [inst : Monad m] [inst : 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)

ink

@[simp]

theorem List.mapM_append {m : Type u_1 → Type u_2} {α : Type u_3} {β : Type u_1} [inst : Monad m] [inst : 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)