Lemmas about List.*Idx functions.

Some specification lemmas for List.mapIdx, List.mapIdxM, List.foldlIdx and List.foldrIdx.

def List.oldMapIdxCore {α : Type u} {β : Type v} (f : ℕ → α → β) : ℕ → List α → List β

Lean3 map_with_index helper function

Equations

• List.oldMapIdxCore f x [] = []
• List.oldMapIdxCore f x (a :: as) = f x a :: List.oldMapIdxCore f (x + 1) as

def List.oldMapIdx {α : Type u} {β : Type v} (f : ℕ → α → β) (as : List α) : List β

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

Equations

• List.oldMapIdx f as = List.oldMapIdxCore f 0 as

@[simp]

theorem List.mapIdx_nil {α : Type u_1} {β : Type u_2} (f : ℕ → α → β) : List.mapIdx f [] = []

theorem List.oldMapIdxCore_eq {α : Type u} {β : Type v} (l : List α) (f : ℕ → α → β) (n : ℕ) : List.oldMapIdxCore f n l = List.oldMapIdx (fun (i : ℕ) (a : α) => f (i + n) a) l

theorem List.list_reverse_induction {α : Type u} (p : List α → Prop) (base : p []) (ind : ∀ (l : List α) (e : α), p l → p (l ++ [e])) (l : List α) : p l

theorem List.oldMapIdxCore_append {α : Type u} {β : Type v} (f : ℕ → α → β) (n : ℕ) (l₁ : List α) (l₂ : List α) : List.oldMapIdxCore f n (l₁ ++ l₂) = List.oldMapIdxCore f n l₁ ++ List.oldMapIdxCore f (n + List.length l₁) l₂

theorem List.oldMapIdx_append {α : Type u} {β : Type v} (f : ℕ → α → β) (l : List α) (e : α) : List.oldMapIdx f (l ++ [e]) = List.oldMapIdx f l ++ [f (List.length l) e]

theorem List.mapIdxGo_append {α : Type u} {β : Type v} (f : ℕ → α → β) (l₁ : List α) (l₂ : List α) (arr : Array β) : List.mapIdx.go f (l₁ ++ l₂) arr = List.mapIdx.go f l₂ (List.toArray (List.mapIdx.go f l₁ arr))

theorem List.mapIdxGo_length {α : Type u} {β : Type v} (f : ℕ → α → β) (l : List α) (arr : Array β) : List.length (List.mapIdx.go f l arr) = List.length l + Array.size arr

theorem List.mapIdx_append_one {α : Type u} {β : Type v} (f : ℕ → α → β) (l : List α) (e : α) : List.mapIdx f (l ++ [e]) = List.mapIdx f l ++ [f (List.length l) e]

theorem List.new_def_eq_old_def {α : Type u} {β : Type v} (f : ℕ → α → β) (l : List α) : List.mapIdx f l = List.oldMapIdx f l

theorem List.map_enumFrom_eq_zipWith {α : Type u} {β : Type v} (l : List α) (n : ℕ) (f : ℕ → α → β) : List.map (Function.uncurry f) (List.enumFrom n l) = List.zipWith (fun (i : ℕ) => f (i + n)) (List.range (List.length l)) l

theorem List.mapIdx_eq_enum_map {α : Type u} {β : Type v} (l : List α) (f : ℕ → α → β) : List.mapIdx f l = List.map (Function.uncurry f) (List.enum l)

@[simp]

theorem List.mapIdx_cons {α : Type u_1} {β : Type u_2} (l : List α) (f : ℕ → α → β) (a : α) : List.mapIdx f (a :: l) = f 0 a :: List.mapIdx (fun (i : ℕ) => f (i + 1)) l

theorem List.mapIdx_append {β : Type v} {α : Type u_1} (K : List α) (L : List α) (f : ℕ → α → β) : List.mapIdx f (K ++ L) = List.mapIdx f K ++ List.mapIdx (fun (i : ℕ) (a : α) => f (i + List.length K) a) L

@[simp]

theorem List.length_mapIdx {α : Type u_1} {β : Type u_2} (l : List α) (f : ℕ → α → β) : List.length (List.mapIdx f l) = List.length l

@[simp]

theorem List.mapIdx_eq_nil {α : Type u_1} {β : Type u_2} {f : ℕ → α → β} {l : List α} : List.mapIdx f l = [] ↔ l = []

@[simp, deprecated]

theorem List.nthLe_mapIdx {α : Type u_1} {β : Type u_2} (l : List α) (f : ℕ → α → β) (i : ℕ) (h : i < List.length l) (h' : optParam (i < List.length (List.mapIdx f l)) ⋯) : List.nthLe (List.mapIdx f l) i h' = f i (List.nthLe l i h)

theorem List.mapIdx_eq_ofFn {α : Type u_1} {β : Type u_2} (l : List α) (f : ℕ → α → β) : List.mapIdx f l = List.ofFn fun (i : Fin (List.length l)) => f (↑i) (List.get l i)

def List.foldrIdxSpec {α : Type u} {β : Type v} (f : ℕ → α → β → β) (b : β) (as : List α) (start : ℕ) : β

Specification of foldrIdx.

Equations

• List.foldrIdxSpec f b as start = List.foldr (Function.uncurry f) b (List.enumFrom start as)

theorem List.foldrIdxSpec_cons {α : Type u} {β : Type v} (f : ℕ → α → β → β) (b : β) (a : α) (as : List α) (start : ℕ) : List.foldrIdxSpec f b (a :: as) start = f start a (List.foldrIdxSpec f b as (start + 1))

theorem List.foldrIdx_eq_foldrIdxSpec {α : Type u} {β : Type v} (f : ℕ → α → β → β) (b : β) (as : List α) (start : ℕ) : List.foldrIdx f b as start = List.foldrIdxSpec f b as start

theorem List.foldrIdx_eq_foldr_enum {α : Type u} {β : Type v} (f : ℕ → α → β → β) (b : β) (as : List α) : List.foldrIdx f b as = List.foldr (Function.uncurry f) b (List.enum as)

theorem List.indexesValues_eq_filter_enum {α : Type u} (p : α → Prop) [DecidablePred p] (as : List α) : List.indexesValues (fun (b : α) => decide (p b)) as = List.filter ((fun (b : α) => decide (p b)) ∘ Prod.snd) (List.enum as)

theorem List.findIdxs_eq_map_indexesValues {α : Type u} (p : α → Prop) [DecidablePred p] (as : List α) : List.findIdxs (fun (b : α) => decide (p b)) as = List.map Prod.fst (List.indexesValues (fun (b : α) => decide (p b)) as)

theorem List.findIdx_eq_length {α : Type u} {p : α → Bool} {xs : List α} : List.findIdx p xs = List.length xs ↔ ∀ x ∈ xs, ¬p x = true

theorem List.findIdx_le_length {α : Type u} (p : α → Bool) {xs : List α} : List.findIdx p xs ≤ List.length xs

theorem List.findIdx_lt_length {α : Type u} {p : α → Bool} {xs : List α} : List.findIdx p xs < List.length xs ↔ ∃ x ∈ xs, p x = true

theorem List.not_of_lt_findIdx {α : Type u} {p : α → Bool} {xs : List α} {i : ℕ} (h : i < List.findIdx p xs) : ¬p (List.get xs { val := i, isLt := ⋯ }) = true

p does not hold for elements with indices less than xs.findIdx p.

theorem List.le_findIdx_of_not {α : Type u} {p : α → Bool} {xs : List α} {i : ℕ} (h : i < List.length xs) (h2 : ∀ (j : ℕ) (hji : j < i), ¬p (List.get xs { val := j, isLt := ⋯ }) = true) : i ≤ List.findIdx p xs

theorem List.lt_findIdx_of_not {α : Type u} {p : α → Bool} {xs : List α} {i : ℕ} (h : i < List.length xs) (h2 : ∀ (j : ℕ) (hji : j ≤ i), ¬p (List.get xs { val := j, isLt := ⋯ }) = true) : i < List.findIdx p xs

theorem List.findIdx_eq {α : Type u} {p : α → Bool} {xs : List α} {i : ℕ} (h : i < List.length xs) : List.findIdx p xs = i ↔ p (List.get xs { val := i, isLt := h }) = true ∧ ∀ (j : ℕ) (hji : j < i), ¬p (List.get xs { val := j, isLt := ⋯ }) = true

def List.foldlIdxSpec {α : Type u} {β : Type v} (f : ℕ → α → β → α) (a : α) (bs : List β) (start : ℕ) : α

Specification of foldlIdx.

Equations

• List.foldlIdxSpec f a bs start = List.foldl (fun (a : α) (p : ℕ × β) => f p.1 a p.2) a (List.enumFrom start bs)

theorem List.foldlIdxSpec_cons {α : Type u} {β : Type v} (f : ℕ → α → β → α) (a : α) (b : β) (bs : List β) (start : ℕ) : List.foldlIdxSpec f a (b :: bs) start = List.foldlIdxSpec f (f start a b) bs (start + 1)

theorem List.foldlIdx_eq_foldlIdxSpec {α : Type u} {β : Type v} (f : ℕ → α → β → α) (a : α) (bs : List β) (start : ℕ) : List.foldlIdx f a bs start = List.foldlIdxSpec f a bs start

theorem List.foldlIdx_eq_foldl_enum {α : Type u} {β : Type v} (f : ℕ → α → β → α) (a : α) (bs : List β) : List.foldlIdx f a bs = List.foldl (fun (a : α) (p : ℕ × β) => f p.1 a p.2) a (List.enum bs)

theorem List.foldrIdxM_eq_foldrM_enum {m : Type u → Type v} [Monad m] {α : Type u_1} {β : Type u} (f : ℕ → α → β → m β) (b : β) (as : List α) [LawfulMonad m] : List.foldrIdxM f b as = List.foldrM (Function.uncurry f) b (List.enum as)

theorem List.foldlIdxM_eq_foldlM_enum {m : Type u → Type v} [Monad m] [LawfulMonad m] {α : Type u_1} {β : Type u} (f : ℕ → β → α → m β) (b : β) (as : List α) : List.foldlIdxM f b as = List.foldlM (fun (b : β) (p : ℕ × α) => f p.1 b p.2) b (List.enum as)

def List.mapIdxMAuxSpec {m : Type u → Type v} [Monad m] {α : Type u_1} {β : Type u} (f : ℕ → α → m β) (start : ℕ) (as : List α) : m (List β)

Specification of mapIdxMAux.

Equations

• List.mapIdxMAuxSpec f start as = List.traverse (Function.uncurry f) (List.enumFrom start as)

theorem List.mapIdxMAuxSpec_cons {m : Type u → Type v} [Monad m] {α : Type u_1} {β : Type u} (f : ℕ → α → m β) (start : ℕ) (a : α) (as : List α) : List.mapIdxMAuxSpec f start (a :: as) = Seq.seq (List.cons <$> f start a) fun (x : Unit) => List.mapIdxMAuxSpec f (start + 1) as

theorem List.mapIdxMGo_eq_mapIdxMAuxSpec {m : Type u → Type v} [Monad m] [LawfulMonad m] {α : Type u_1} {β : Type u} (f : ℕ → α → m β) (arr : Array β) (as : List α) : List.mapIdxM.go f as arr = (fun (x : List β) => Array.toList arr ++ x) <$> List.mapIdxMAuxSpec f (Array.size arr) as

theorem List.mapIdxM_eq_mmap_enum {m : Type u → Type v} [Monad m] [LawfulMonad m] {α : Type u_1} {β : Type u} (f : ℕ → α → m β) (as : List α) : List.mapIdxM as f = List.traverse (Function.uncurry f) (List.enum as)

theorem List.mapIdxMAux'_eq_mapIdxMGo {m : Type u → Type v} [Monad m] [LawfulMonad m] {α : Type u_1} (f : ℕ → α → m PUnit.{u + 1} ) (as : List α) (arr : Array PUnit.{u + 1} ) : List.mapIdxMAux' f (Array.size arr) as = SeqRight.seqRight (List.mapIdxM.go f as arr) fun (x : Unit) => pure PUnit.unit

theorem List.mapIdxM'_eq_mapIdxM {m : Type u → Type v} [Monad m] [LawfulMonad m] {α : Type u_1} (f : ℕ → α → m PUnit.{u + 1} ) (as : List α) : List.mapIdxM' f as = SeqRight.seqRight (List.mapIdxM as f) fun (x : Unit) => pure PUnit.unit