def List.pmap {α : Type u_1} {β : Type u_2} {P : α → Prop} (f : (a : α) → P a → β) (l : List α) (H : ∀ (a : α), a ∈ l → P a) : List β

Maps a partially defined function (defined on those terms of α that satisfy a predicate P) over a list l : List α, given a proof that every element of l in fact satisfies P.

O(|l|). List.pmap, named for “partial map,” is the equivalent of List.map for such partial functions.

Equations

• List.pmap f [] x_2 = []
• List.pmap f (a :: l) H = f a ⋯ :: List.pmap f l ⋯

@[implemented_by _private.Init.Data.List.Attach.0.List.attachWithImpl]

def List.attachWith {α : Type u_1} (l : List α) (P : α → Prop) (H : ∀ (x : α), x ∈ l → P x) : List { x : α // P x }

“Attaches” individual proofs to a list of values that satisfy a predicate P, returning a list of elements in the corresponding subtype { x // P x }.

O(1).

Equations

• l.attachWith P H = List.pmap Subtype.mk l H

@[inline]

def List.attach {α : Type u_1} (l : List α) : List { x : α // x ∈ l }

“Attaches” the proof that the elements of l are in fact elements of l, producing a new list with the same elements but in the subtype { x // x ∈ l }.

O(1).

This function is primarily used to allow definitions by well-founded recursion that use higher-order functions (such as List.map) to prove that an value taken from a list is smaller than the list. This allows the well-founded recursion mechanism to prove that the function terminates.

Equations

• l.attach = l.attachWith (Membership.mem l) ⋯

@[inline]

def List.pmapImpl {α : Type u_1} {β : Type u_2} {P : α → Prop} (f : (a : α) → P a → β) (l : List α) (H : ∀ (a : α), a ∈ l → P a) : List β

Implementation of pmap using the zero-copy version of attach.

Equations

• List.pmapImpl f l H = List.map (fun (x : { x : α // P x }) => match x with | ⟨x, h'⟩ => f x h') (l.attachWith P H)

@[csimp]

theorem List.pmap_eq_pmapImpl : @pmap = @pmapImpl

@[simp]

theorem List.pmap_nil {α : Type u_1} {β : Type u_2} {P : α → Prop} {f : (a : α) → P a → β} : pmap f [] ⋯ = []

@[simp]

theorem List.pmap_cons {α : Type u_1} {β : Type u_2} {P : α → Prop} {f : (a : α) → P a → β} {a : α} {l : List α} (h : ∀ (b : α), b ∈ a :: l → P b) : pmap f (a :: l) h = f a ⋯ :: pmap f l ⋯

@[simp]

theorem List.attach_nil {α : Type u_1} : [].attach = []

@[simp]

theorem List.attachWith_nil {α : Type u_1} {P : α → Prop} {H : ∀ (x : α), x ∈ [] → P x} : [].attachWith P H = []

@[simp]

theorem List.pmap_eq_map {α : Type u_1} {β : Type u_2} {p : α → Prop} {f : α → β} {l : List α} (H : ∀ (a : α), a ∈ l → p a) : pmap (fun (a : α) (x : p a) => f a) l H = map f l

theorem List.pmap_congr_left {α : Type u_1} {β : Type u_2} {p q : α → Prop} {f : (a : α) → p a → β} {g : (a : α) → q a → β} (l : List α) {H₁ : ∀ (a : α), a ∈ l → p a} {H₂ : ∀ (a : α), a ∈ l → q a} (h : ∀ (a : α), a ∈ l → ∀ (h₁ : p a) (h₂ : q a), f a h₁ = g a h₂) : pmap f l H₁ = pmap g l H₂

theorem List.map_pmap {α : Type u_1} {β : Type u_2} {γ : Type u_3} {p : α → Prop} {g : β → γ} {f : (a : α) → p a → β} {l : List α} (H : ∀ (a : α), a ∈ l → p a) : map g (pmap f l H) = pmap (fun (a : α) (h : p a) => g (f a h)) l H

theorem List.pmap_map {β : Type u_1} {γ : Type u_2} {α : Type u_3} {p : β → Prop} {g : (b : β) → p b → γ} {f : α → β} {l : List α} (H : ∀ (a : β), a ∈ map f l → p a) : pmap g (map f l) H = pmap (fun (a : α) (h : p (f a)) => g (f a) h) l ⋯

theorem List.attach_congr {α : Type u_1} {l₁ l₂ : List α} (h : l₁ = l₂) : l₁.attach = map (fun (x : { x : α // x ∈ l₂ }) => ⟨x.val, ⋯⟩) l₂.attach

theorem List.attachWith_congr {α : Type u_1} {l₁ l₂ : List α} (w : l₁ = l₂) {P : α → Prop} {H : ∀ (x : α), x ∈ l₁ → P x} : l₁.attachWith P H = l₂.attachWith P ⋯

@[simp]

theorem List.attach_cons {α : Type u_1} {x : α} {xs : List α} : (x :: xs).attach = ⟨x, ⋯⟩ :: map (fun (x_1 : { x : α // x ∈ xs }) => match x_1 with | ⟨y, h⟩ => ⟨y, ⋯⟩) xs.attach

@[simp]

theorem List.attachWith_cons {α : Type u_1} {x : α} {xs : List α} {p : α → Prop} (h : ∀ (a : α), a ∈ x :: xs → p a) : (x :: xs).attachWith p h = ⟨x, ⋯⟩ :: xs.attachWith p ⋯

theorem List.pmap_eq_map_attach {α : Type u_1} {β : Type u_2} {p : α → Prop} {f : (a : α) → p a → β} {l : List α} (H : ∀ (a : α), a ∈ l → p a) : pmap f l H = map (fun (x : { x : α // x ∈ l }) => f x.val ⋯) l.attach

theorem List.attachWith_eq_map_attach {α : Type u_1} {xs : List α} {P : α → Prop} {H : ∀ (a : α), a ∈ xs → P a} : xs.attachWith P H = map (fun (x : { x : α // x ∈ xs }) => match x with | ⟨x, h⟩ => ⟨x, ⋯⟩) xs.attach

@[simp]

theorem List.pmap_eq_attachWith {α : Type u_1} {p q : α → Prop} {f : ∀ (a : α), p a → q a} {l : List α} (H : ∀ (a : α), a ∈ l → p a) : pmap (fun (a : α) (h : p a) => ⟨a, ⋯⟩) l H = l.attachWith q ⋯

theorem List.attach_map_val {α : Type u_1} {β : Type u_2} {l : List α} {f : α → β} : map (fun (i : { i : α // i ∈ l }) => f i.val) l.attach = map f l

theorem List.attach_map_subtype_val {α : Type u_1} (l : List α) : map Subtype.val l.attach = l

theorem List.attachWith_map_val {α : Type u_1} {β : Type u_2} {p : α → Prop} {f : α → β} {l : List α} (H : ∀ (a : α), a ∈ l → p a) : map (fun (i : { i : α // p i }) => f i.val) (l.attachWith p H) = map f l

theorem List.attachWith_map_subtype_val {α : Type u_1} {p : α → Prop} {l : List α} (H : ∀ (a : α), a ∈ l → p a) : map Subtype.val (l.attachWith p H) = l

@[simp]

theorem List.mem_attach {α : Type u_1} (l : List α) (x : { x : α // x ∈ l }) : x ∈ l.attach

@[simp]

theorem List.mem_attachWith {α : Type u_1} {l : List α} {q : α → Prop} (H : ∀ (x : α), x ∈ l → q x) (x : { x : α // q x }) : x ∈ l.attachWith q H ↔ x.val ∈ l

@[simp]

theorem List.mem_pmap {α : Type u_1} {β : Type u_2} {p : α → Prop} {f : (a : α) → p a → β} {l : List α} {H : ∀ (a : α), a ∈ l → p a} {b : β} : b ∈ pmap f l H ↔ ∃ (a : α), ∃ (h : a ∈ l), f a ⋯ = b

theorem List.mem_pmap_of_mem {α : Type u_1} {β : Type u_2} {p : α → Prop} {f : (a : α) → p a → β} {l : List α} {H : ∀ (a : α), a ∈ l → p a} {a : α} (h : a ∈ l) : f a ⋯ ∈ pmap f l H

@[simp]

theorem List.length_pmap {α : Type u_1} {β : Type u_2} {p : α → Prop} {f : (a : α) → p a → β} {l : List α} {H : ∀ (a : α), a ∈ l → p a} : (pmap f l H).length = l.length

@[simp]

theorem List.length_attach {α : Type u_1} {l : List α} : l.attach.length = l.length

@[simp]

theorem List.length_attachWith {α : Type u_1} {p : α → Prop} {l : List α} {H : ∀ (x : α), x ∈ l → p x} : (l.attachWith p H).length = l.length

@[simp]

theorem List.pmap_eq_nil_iff {α : Type u_1} {β : Type u_2} {p : α → Prop} {f : (a : α) → p a → β} {l : List α} {H : ∀ (a : α), a ∈ l → p a} : pmap f l H = [] ↔ l = []

theorem List.pmap_ne_nil_iff {α : Type u_1} {β : Type u_2} {P : α → Prop} (f : (a : α) → P a → β) {xs : List α} (H : ∀ (a : α), a ∈ xs → P a) : pmap f xs H ≠ [] ↔ xs ≠ []

theorem List.pmap_eq_self {α : Type u_1} {l : List α} {p : α → Prop} {hp : ∀ (a : α), a ∈ l → p a} {f : (a : α) → p a → α} : pmap f l hp = l ↔ ∀ (a : α) (h : a ∈ l), f a ⋯ = a

@[simp]

theorem List.attach_eq_nil_iff {α : Type u_1} {l : List α} : l.attach = [] ↔ l = []

theorem List.attach_ne_nil_iff {α : Type u_1} {l : List α} : l.attach ≠ [] ↔ l ≠ []

@[simp]

theorem List.attachWith_eq_nil_iff {α : Type u_1} {l : List α} {P : α → Prop} {H : ∀ (a : α), a ∈ l → P a} : l.attachWith P H = [] ↔ l = []

theorem List.attachWith_ne_nil_iff {α : Type u_1} {l : List α} {P : α → Prop} {H : ∀ (a : α), a ∈ l → P a} : l.attachWith P H ≠ [] ↔ l ≠ []

@[simp]

theorem List.getElem?_pmap {α : Type u_1} {β : Type u_2} {p : α → Prop} {f : (a : α) → p a → β} {l : List α} (h : ∀ (a : α), a ∈ l → p a) (i : Nat) : (pmap f l h)[i]? = Option.pmap f l[i]? ⋯

@[simp]

theorem List.getElem_pmap {α : Type u_1} {β : Type u_2} {p : α → Prop} (f : (a : α) → p a → β) {l : List α} (h : ∀ (a : α), a ∈ l → p a) {i : Nat} (hn : i < (pmap f l h).length) : (pmap f l h)[i] = f l[i] ⋯

@[simp]

theorem List.getElem?_attachWith {α : Type u_1} {xs : List α} {i : Nat} {P : α → Prop} {H : ∀ (a : α), a ∈ xs → P a} : (xs.attachWith P H)[i]? = Option.pmap Subtype.mk xs[i]? ⋯

@[simp]

theorem List.getElem?_attach {α : Type u_1} {xs : List α} {i : Nat} : xs.attach[i]? = Option.pmap Subtype.mk xs[i]? ⋯

@[simp]

theorem List.getElem_attachWith {α : Type u_1} {xs : List α} {P : α → Prop} {H : ∀ (a : α), a ∈ xs → P a} {i : Nat} (h : i < (xs.attachWith P H).length) : (xs.attachWith P H)[i] = ⟨xs[i], ⋯⟩

@[simp]

theorem List.getElem_attach {α : Type u_1} {xs : List α} {i : Nat} (h : i < xs.attach.length) : xs.attach[i] = ⟨xs[i], ⋯⟩

@[simp]

theorem List.pmap_attach {α : Type u_1} {β : Type u_2} {l : List α} {p : { x : α // x ∈ l } → Prop} {f : (a : { x : α // x ∈ l }) → p a → β} (H : ∀ (a : { x : α // x ∈ l }), a ∈ l.attach → p a) : pmap f l.attach H = pmap (fun (a : α) (h : ∃ (h : a ∈ l), p ⟨a, h⟩) => f ⟨a, ⋯⟩ ⋯) l ⋯

@[simp]

theorem List.pmap_attachWith {α : Type u_1} {q : α → Prop} {β : Type u_2} {l : List α} {p : { x : α // q x } → Prop} {f : (a : { x : α // q x }) → p a → β} (H₁ : ∀ (x : α), x ∈ l → q x) (H₂ : ∀ (a : { x : α // q x }), a ∈ l.attachWith q H₁ → p a) : pmap f (l.attachWith q H₁) H₂ = pmap (fun (a : α) (h : ∃ (h : q a), p ⟨a, h⟩) => f ⟨a, ⋯⟩ ⋯) l ⋯

@[simp]

theorem List.head?_pmap {α : Type u_1} {β : Type u_2} {P : α → Prop} {f : (a : α) → P a → β} {xs : List α} (H : ∀ (a : α), a ∈ xs → P a) : (pmap f xs H).head? = Option.map (fun (x : { x : α // x ∈ xs }) => match x with | ⟨a, m⟩ => f a ⋯) xs.attach.head?

@[simp]

theorem List.head_pmap {α : Type u_1} {β : Type u_2} {P : α → Prop} {f : (a : α) → P a → β} {xs : List α} (H : ∀ (a : α), a ∈ xs → P a) (h : pmap f xs H ≠ []) : (pmap f xs H).head h = f (xs.head ⋯) ⋯

@[simp]

theorem List.head?_attachWith {α : Type u_1} {P : α → Prop} {xs : List α} (H : ∀ (a : α), a ∈ xs → P a) : (xs.attachWith P H).head? = xs.head?.pbind fun (a : α) (h : xs.head? = some a) => some ⟨a, ⋯⟩

@[simp]

theorem List.head_attachWith {α : Type u_1} {P : α → Prop} {xs : List α} {H : ∀ (a : α), a ∈ xs → P a} (h : xs.attachWith P H ≠ []) : (xs.attachWith P H).head h = ⟨xs.head ⋯, ⋯⟩

@[simp]

theorem List.head?_attach {α : Type u_1} {xs : List α} : xs.attach.head? = xs.head?.pbind fun (a : α) (h : xs.head? = some a) => some ⟨a, ⋯⟩

@[simp]

theorem List.head_attach {α : Type u_1} {xs : List α} (h : xs.attach ≠ []) : xs.attach.head h = ⟨xs.head ⋯, ⋯⟩

@[simp]

theorem List.tail_pmap {α : Type u_1} {β : Type u_2} {P : α → Prop} {f : (a : α) → P a → β} {xs : List α} (H : ∀ (a : α), a ∈ xs → P a) : (pmap f xs H).tail = pmap f xs.tail ⋯

@[simp]

theorem List.tail_attachWith {α : Type u_1} {P : α → Prop} {xs : List α} {H : ∀ (a : α), a ∈ xs → P a} : (xs.attachWith P H).tail = xs.tail.attachWith P ⋯

@[simp]

theorem List.tail_attach {α : Type u_1} {xs : List α} : xs.attach.tail = map (fun (x : { x : α // x ∈ xs.tail }) => match x with | ⟨x, h⟩ => ⟨x, ⋯⟩) xs.tail.attach

theorem List.foldl_pmap {α : Type u_1} {β : Type u_2} {γ : Type u_3} {l : List α} {P : α → Prop} {f : (a : α) → P a → β} (H : ∀ (a : α), a ∈ l → P a) (g : γ → β → γ) (x : γ) : foldl g x (pmap f l H) = foldl (fun (acc : γ) (a : { x : α // x ∈ l }) => g acc (f a.val ⋯)) x l.attach

theorem List.foldr_pmap {α : Type u_1} {β : Type u_2} {γ : Type u_3} {l : List α} {P : α → Prop} {f : (a : α) → P a → β} (H : ∀ (a : α), a ∈ l → P a) (g : β → γ → γ) (x : γ) : foldr g x (pmap f l H) = foldr (fun (a : { x : α // x ∈ l }) (acc : γ) => g (f a.val ⋯) acc) x l.attach

@[simp]

theorem List.foldl_attachWith {α : Type u_1} {β : Type u_2} {l : List α} {q : α → Prop} (H : ∀ (a : α), a ∈ l → q a) {f : β → { x : α // q x } → β} {b : β} : foldl f b (l.attachWith q H) = foldl (fun (b : β) (x : { x : α // x ∈ l }) => match x with | ⟨a, h⟩ => f b ⟨a, ⋯⟩) b l.attach

@[simp]

theorem List.foldr_attachWith {α : Type u_1} {β : Type u_2} {l : List α} {q : α → Prop} (H : ∀ (a : α), a ∈ l → q a) {f : { x : α // q x } → β → β} {b : β} : foldr f b (l.attachWith q H) = foldr (fun (a : { x : α // x ∈ l }) (acc : β) => f ⟨a.val, ⋯⟩ acc) b l.attach

theorem List.foldl_attach {α : Type u_1} {β : Type u_2} {l : List α} {f : β → α → β} {b : β} : foldl (fun (acc : β) (t : { x : α // x ∈ l }) => f acc t.val) b l.attach = foldl f b l

If we fold over l.attach with a function that ignores the membership predicate, we get the same results as folding over l directly.

This is useful when we need to use attach to show termination.

Unfortunately this can't be applied by simp because of the higher order unification problem, and even when rewriting we need to specify the function explicitly. See however foldl_subtype below.

theorem List.foldr_attach {α : Type u_1} {β : Type u_2} {l : List α} {f : α → β → β} {b : β} : foldr (fun (t : { x : α // x ∈ l }) (acc : β) => f t.val acc) b l.attach = foldr f b l

If we fold over l.attach with a function that ignores the membership predicate, we get the same results as folding over l directly.

This is useful when we need to use attach to show termination.

Unfortunately this can't be applied by simp because of the higher order unification problem, and even when rewriting we need to specify the function explicitly. See however foldr_subtype below.

theorem List.attach_map {α : Type u_1} {β : Type u_2} {l : List α} {f : α → β} : (map f l).attach = map (fun (x : { x : α // x ∈ l }) => match x with | ⟨x, h⟩ => ⟨f x, ⋯⟩) l.attach

theorem List.attachWith_map {α : Type u_1} {β : Type u_2} {l : List α} {f : α → β} {P : β → Prop} (H : ∀ (b : β), b ∈ map f l → P b) : (map f l).attachWith P H = map (fun (x : { x : α // (P ∘ f) x }) => match x with | ⟨x, h⟩ => ⟨f x, h⟩) (l.attachWith (P ∘ f) ⋯)

@[simp]

theorem List.map_attachWith {α : Type u_1} {β : Type u_2} {l : List α} {P : α → Prop} {H : ∀ (a : α), a ∈ l → P a} {f : { x : α // P x } → β} : map f (l.attachWith P H) = map (fun (x : { x : α // x ∈ l }) => match x with | ⟨x, h⟩ => f ⟨x, ⋯⟩) l.attach

theorem List.map_attachWith_eq_pmap {α : Type u_1} {β : Type u_2} {l : List α} {P : α → Prop} {H : ∀ (a : α), a ∈ l → P a} {f : { x : α // P x } → β} : map f (l.attachWith P H) = pmap (fun (a : α) (h : a ∈ l ∧ P a) => f ⟨a, ⋯⟩) l ⋯

theorem List.map_attach_eq_pmap {α : Type u_1} {β : Type u_2} {l : List α} {f : { x : α // x ∈ l } → β} : map f l.attach = pmap (fun (a : α) (h : a ∈ l) => f ⟨a, h⟩) l ⋯

See also pmap_eq_map_attach for writing pmap in terms of map and attach.

theorem List.attach_filterMap {α : Type u_1} {β : Type u_2} {l : List α} {f : α → Option β} : (filterMap f l).attach = filterMap (fun (x : { x : α // x ∈ l }) => match x with | ⟨x, h⟩ => (f x).pbind fun (b : β) (m : f x = some b) => some ⟨b, ⋯⟩) l.attach

theorem List.attach_filter {α : Type u_1} {l : List α} (p : α → Bool) : (filter p l).attach = filterMap (fun (x : { x : α // x ∈ l }) => if w : p x.val = true then some ⟨x.val, ⋯⟩ else none) l.attach

@[simp]

theorem List.filterMap_attachWith {α : Type u_1} {β : Type u_2} {q : α → Prop} {l : List α} {f : { x : α // q x } → Option β} (H : ∀ (x : α), x ∈ l → q x) : filterMap f (l.attachWith q H) = filterMap (fun (x : { x : α // x ∈ l }) => match x with | ⟨x, h⟩ => f ⟨x, ⋯⟩) l.attach

@[simp]

theorem List.filter_attachWith {α : Type u_1} {q : α → Prop} {l : List α} {p : { x : α // q x } → Bool} (H : ∀ (x : α), x ∈ l → q x) : filter p (l.attachWith q H) = map (fun (x : { x : α // x ∈ l }) => match x with | ⟨x, h⟩ => ⟨x, ⋯⟩) (filter (fun (x : { x : α // x ∈ l }) => match x with | ⟨x, h⟩ => p ⟨x, ⋯⟩) l.attach)

theorem List.pmap_pmap {α : Type u_1} {β : Type u_2} {γ : Type u_3} {p : α → Prop} {q : β → Prop} {g : (a : α) → p a → β} {f : (b : β) → q b → γ} {l : List α} (H₁ : ∀ (a : α), a ∈ l → p a) (H₂ : ∀ (a : β), a ∈ pmap g l H₁ → q a) : pmap f (pmap g l H₁) H₂ = pmap (fun (a : { x : α // x ∈ l }) (h : p a.val) => f (g a.val h) ⋯) l.attach ⋯

@[simp]

theorem List.pmap_append {ι : Type u_1} {α : Type u_2} {p : ι → Prop} {f : (a : ι) → p a → α} {l₁ l₂ : List ι} (h : ∀ (a : ι), a ∈ l₁ ++ l₂ → p a) : pmap f (l₁ ++ l₂) h = pmap f l₁ ⋯ ++ pmap f l₂ ⋯

theorem List.pmap_append' {α : Type u_1} {β : Type u_2} {p : α → Prop} {f : (a : α) → p a → β} {l₁ l₂ : List α} (h₁ : ∀ (a : α), a ∈ l₁ → p a) (h₂ : ∀ (a : α), a ∈ l₂ → p a) : pmap f (l₁ ++ l₂) ⋯ = pmap f l₁ h₁ ++ pmap f l₂ h₂

@[simp]

theorem List.attach_append {α : Type u_1} {xs ys : List α} : (xs ++ ys).attach = map (fun (x : { x : α // x ∈ xs }) => match x with | ⟨x, h⟩ => ⟨x, ⋯⟩) xs.attach ++ map (fun (x : { x : α // x ∈ ys }) => match x with | ⟨x, h⟩ => ⟨x, ⋯⟩) ys.attach

@[simp]

theorem List.attachWith_append {α : Type u_1} {P : α → Prop} {xs ys : List α} {H : ∀ (a : α), a ∈ xs ++ ys → P a} : (xs ++ ys).attachWith P H = xs.attachWith P ⋯ ++ ys.attachWith P ⋯

@[simp]

theorem List.pmap_reverse {α : Type u_1} {β : Type u_2} {P : α → Prop} {f : (a : α) → P a → β} {xs : List α} (H : ∀ (a : α), a ∈ xs.reverse → P a) : pmap f xs.reverse H = (pmap f xs ⋯).reverse

theorem List.reverse_pmap {α : Type u_1} {β : Type u_2} {P : α → Prop} {f : (a : α) → P a → β} {xs : List α} (H : ∀ (a : α), a ∈ xs → P a) : (pmap f xs H).reverse = pmap f xs.reverse ⋯

@[simp]

theorem List.attachWith_reverse {α : Type u_1} {P : α → Prop} {xs : List α} {H : ∀ (a : α), a ∈ xs.reverse → P a} : xs.reverse.attachWith P H = (xs.attachWith P ⋯).reverse

theorem List.reverse_attachWith {α : Type u_1} {P : α → Prop} {xs : List α} {H : ∀ (a : α), a ∈ xs → P a} : (xs.attachWith P H).reverse = xs.reverse.attachWith P ⋯

@[simp]

theorem List.attach_reverse {α : Type u_1} {xs : List α} : xs.reverse.attach = map (fun (x : { x : α // x ∈ xs }) => match x with | ⟨x, h⟩ => ⟨x, ⋯⟩) xs.attach.reverse

theorem List.reverse_attach {α : Type u_1} {xs : List α} : xs.attach.reverse = map (fun (x : { x : α // x ∈ xs.reverse }) => match x with | ⟨x, h⟩ => ⟨x, ⋯⟩) xs.reverse.attach

@[simp]

theorem List.getLast?_pmap {α : Type u_1} {β : Type u_2} {P : α → Prop} {f : (a : α) → P a → β} {xs : List α} (H : ∀ (a : α), a ∈ xs → P a) : (pmap f xs H).getLast? = Option.map (fun (x : { x : α // x ∈ xs }) => match x with | ⟨a, m⟩ => f a ⋯) xs.attach.getLast?

@[simp]

theorem List.getLast_pmap {α : Type u_1} {β : Type u_2} {P : α → Prop} {f : (a : α) → P a → β} {xs : List α} (H : ∀ (a : α), a ∈ xs → P a) (h : pmap f xs H ≠ []) : (pmap f xs H).getLast h = f (xs.getLast ⋯) ⋯

@[simp]

theorem List.getLast?_attachWith {α : Type u_1} {P : α → Prop} {xs : List α} {H : ∀ (a : α), a ∈ xs → P a} : (xs.attachWith P H).getLast? = xs.getLast?.pbind fun (a : α) (h : xs.getLast? = some a) => some ⟨a, ⋯⟩

@[simp]

theorem List.getLast_attachWith {α : Type u_1} {P : α → Prop} {xs : List α} {H : ∀ (a : α), a ∈ xs → P a} (h : xs.attachWith P H ≠ []) : (xs.attachWith P H).getLast h = ⟨xs.getLast ⋯, ⋯⟩

@[simp]

theorem List.getLast?_attach {α : Type u_1} {xs : List α} : xs.attach.getLast? = xs.getLast?.pbind fun (a : α) (h : xs.getLast? = some a) => some ⟨a, ⋯⟩

@[simp]

theorem List.getLast_attach {α : Type u_1} {xs : List α} (h : xs.attach ≠ []) : xs.attach.getLast h = ⟨xs.getLast ⋯, ⋯⟩

@[simp]

theorem List.countP_attach {α : Type u_1} {l : List α} {p : α → Bool} : countP (fun (a : { x : α // x ∈ l }) => p a.val) l.attach = countP p l

@[simp]

theorem List.countP_attachWith {α : Type u_1} {p : α → Prop} {q : α → Bool} {l : List α} (H : ∀ (a : α), a ∈ l → p a) : countP (fun (a : { x : α // p x }) => q a.val) (l.attachWith p H) = countP q l

@[simp]

theorem List.count_attach {α : Type u_1} [BEq α] {l : List α} {a : { x : α // x ∈ l }} : count a l.attach = count a.val l

@[simp]

theorem List.count_attachWith {α : Type u_1} [BEq α] {p : α → Prop} {l : List α} (H : ∀ (a : α), a ∈ l → p a) {a : { x : α // p x }} : count a (l.attachWith p H) = count a.val l

@[simp]

theorem List.countP_pmap {α : Type u_1} {β : Type u_2} {p : α → Prop} {g : (a : α) → p a → β} {f : β → Bool} {l : List α} (H₁ : ∀ (a : α), a ∈ l → p a) : countP f (pmap g l H₁) = countP (fun (x : { x : α // x ∈ l }) => match x with | ⟨a, m⟩ => f (g a ⋯)) l.attach

unattach

List.unattach is the (one-sided) inverse of List.attach. It is a synonym for List.map Subtype.val.

We use it by providing a simp lemma l.attach.unattach = l, and simp lemmas which recognize higher order functions applied to l : List { x // p x } which only depend on the value, not the predicate, and rewrite these in terms of a simpler function applied to l.unattach.

Further, we provide simp lemmas that push unattach inwards.

def List.unattach {α : Type u_1} {p : α → Prop} (l : List { x : α // p x }) : List α

Maps a list of terms in a subtype to the corresponding terms in the type by forgetting that they satisfy the predicate.

This is the inverse of List.attachWith and a synonym for l.map (·.val).

Mostly this should not be needed by users. It is introduced as an intermediate step by lemmas such as map_subtype, and is ideally subsequently simplified away by unattach_attach.

This function is usually inserted automatically by Lean as an intermediate step while proving termination. It is rarely used explicitly in code. It is introduced as an intermediate step during the elaboration of definitions by well-founded recursion. If this function is encountered in a proof state, the right approach is usually the tactic simp [List.unattach, -List.map_subtype].

Equations

• l.unattach = List.map (fun (x : { x : α // p x }) => x.val) l

@[simp]

theorem List.unattach_nil {α : Type u_1} {p : α → Prop} : [].unattach = []

@[simp]

theorem List.unattach_cons {α : Type u_1} {p : α → Prop} {a : { x : α // p x }} {l : List { x : α // p x }} : (a :: l).unattach = a.val :: l.unattach

@[simp]

theorem List.mem_unattach {α : Type u_1} {p : α → Prop} {l : List { x : α // p x }} {a : α} : a ∈ l.unattach ↔ ∃ (h : p a), ⟨a, h⟩ ∈ l

@[simp]

theorem List.length_unattach {α : Type u_1} {p : α → Prop} {l : List { x : α // p x }} : l.unattach.length = l.length

@[simp]

theorem List.unattach_attach {α : Type u_1} {l : List α} : l.attach.unattach = l

@[simp]

theorem List.unattach_attachWith {α : Type u_1} {p : α → Prop} {l : List α} {H : ∀ (a : α), a ∈ l → p a} : (l.attachWith p H).unattach = l

@[simp]

theorem List.getElem?_unattach {α : Type u_1} {p : α → Prop} {l : List { x : α // p x }} (i : Nat) : l.unattach[i]? = Option.map Subtype.val l[i]?

@[simp]

theorem List.getElem_unattach {α : Type u_1} {p : α → Prop} {l : List { x : α // p x }} (i : Nat) (h : i < l.unattach.length) : l.unattach[i] = l[i].val

Recognizing higher order functions on subtypes using a function that only depends on the value.

@[simp]

theorem List.foldl_subtype {α : Type u_1} {β : Type u_2} {p : α → Prop} {l : List { x : α // p x }} {f : β → { x : α // p x } → β} {g : β → α → β} {x : β} (hf : ∀ (b : β) (x : α) (h : p x), f b ⟨x, h⟩ = g b x) : foldl f x l = foldl g x l.unattach

This lemma identifies folds over lists of subtypes, where the function only depends on the value, not the proposition, and simplifies these to the function directly taking the value.

@[simp]

theorem List.foldr_subtype {α : Type u_1} {β : Type u_2} {p : α → Prop} {l : List { x : α // p x }} {f : { x : α // p x } → β → β} {g : α → β → β} {x : β} (hf : ∀ (x : α) (h : p x) (b : β), f ⟨x, h⟩ b = g x b) : foldr f x l = foldr g x l.unattach

This lemma identifies folds over lists of subtypes, where the function only depends on the value, not the proposition, and simplifies these to the function directly taking the value.

@[simp]

theorem List.map_subtype {α : Type u_1} {β : Type u_2} {p : α → Prop} {l : List { x : α // p x }} {f : { x : α // p x } → β} {g : α → β} (hf : ∀ (x : α) (h : p x), f ⟨x, h⟩ = g x) : map f l = map g l.unattach

This lemma identifies maps over lists of subtypes, where the function only depends on the value, not the proposition, and simplifies these to the function directly taking the value.

@[simp]

theorem List.filterMap_subtype {α : Type u_1} {β : Type u_2} {p : α → Prop} {l : List { x : α // p x }} {f : { x : α // p x } → Option β} {g : α → Option β} (hf : ∀ (x : α) (h : p x), f ⟨x, h⟩ = g x) : filterMap f l = filterMap g l.unattach

@[simp]

theorem List.flatMap_subtype {α : Type u_1} {β : Type u_2} {p : α → Prop} {l : List { x : α // p x }} {f : { x : α // p x } → List β} {g : α → List β} (hf : ∀ (x : α) (h : p x), f ⟨x, h⟩ = g x) : flatMap f l = flatMap g l.unattach

@[simp]

theorem List.findSome?_subtype {α : Type u_1} {β : Type u_2} {p : α → Prop} {l : List { x : α // p x }} {f : { x : α // p x } → Option β} {g : α → Option β} (hf : ∀ (x : α) (h : p x), f ⟨x, h⟩ = g x) : findSome? f l = findSome? g l.unattach

@[simp]

theorem List.find?_subtype {α : Type u_1} {p : α → Prop} {l : List { x : α // p x }} {f : { x : α // p x } → Bool} {g : α → Bool} (hf : ∀ (x : α) (h : p x), f ⟨x, h⟩ = g x) : Option.map Subtype.val (find? f l) = find? g l.unattach

@[simp]

theorem List.all_subtype {α : Type u_1} {p : α → Prop} {l : List { x : α // p x }} {f : { x : α // p x } → Bool} {g : α → Bool} (hf : ∀ (x : α) (h : p x), f ⟨x, h⟩ = g x) : l.all f = l.unattach.all g

@[simp]

theorem List.any_subtype {α : Type u_1} {p : α → Prop} {l : List { x : α // p x }} {f : { x : α // p x } → Bool} {g : α → Bool} (hf : ∀ (x : α) (h : p x), f ⟨x, h⟩ = g x) : l.any f = l.unattach.any g

Simp lemmas pushing unattach inwards.

@[simp]

theorem List.unattach_filter {α : Type u_1} {p : α → Prop} {l : List { x : α // p x }} {f : { x : α // p x } → Bool} {g : α → Bool} {hf : ∀ (x : α) (h : p x), f ⟨x, h⟩ = g x} : (filter f l).unattach = filter g l.unattach

@[simp]

theorem List.unattach_reverse {α : Type u_1} {p : α → Prop} {l : List { x : α // p x }} : l.reverse.unattach = l.unattach.reverse

@[simp]

theorem List.unattach_append {α : Type u_1} {p : α → Prop} {l₁ l₂ : List { x : α // p x }} : (l₁ ++ l₂).unattach = l₁.unattach ++ l₂.unattach

@[simp]

theorem List.unattach_flatten {α : Type u_1} {p : α → Prop} {l : List (List { x : α // p x })} : l.flatten.unattach = (map unattach l).flatten

@[simp]

theorem List.unattach_replicate {α : Type u_1} {p : α → Prop} {n : Nat} {x : { x : α // p x }} : (replicate n x).unattach = replicate n x.val

Well-founded recursion preprocessing setup

theorem List.map_wfParam {α : Type u_1} {β : Type u_2} {xs : List α} {f : α → β} : map f (wfParam xs) = map f xs.attach.unattach

theorem List.map_unattach {α : Type u_1} {β : Type u_2} {P : α → Prop} {xs : List (Subtype P)} {f : α → β} : map f xs.unattach = map (fun (x : Subtype P) => match x with | ⟨x, h⟩ => binderNameHint x f (binderNameHint h () (f (wfParam x)))) xs

theorem List.foldl_wfParam {α : Type u_1} {β : Type u_2} {xs : List α} {f : β → α → β} {x : β} : foldl f x (wfParam xs) = foldl f x xs.attach.unattach

theorem List.foldl_unattach {α : Type u_1} {β : Type u_2} {P : α → Prop} {xs : List (Subtype P)} {f : β → α → β} {x : β} : foldl f x xs.unattach = foldl (fun (s : β) (x : Subtype P) => match x with | ⟨x, h⟩ => binderNameHint s f (binderNameHint x (f s) (binderNameHint h () (f s (wfParam x))))) x xs

theorem List.foldr_wfParam {α : Type u_1} {β : Type u_2} {xs : List α} {f : α → β → β} {x : β} : foldr f x (wfParam xs) = foldr f x xs.attach.unattach

theorem List.foldr_unattach {α : Type u_1} {β : Type u_2} {P : α → Prop} {xs : List (Subtype P)} {f : α → β → β} {x : β} : foldr f x xs.unattach = foldr (fun (x : Subtype P) (s : β) => match x with | ⟨x, h⟩ => binderNameHint x f (binderNameHint s (f x) (binderNameHint h () (f (wfParam x) s)))) x xs

theorem List.filter_wfParam {α : Type u_1} {xs : List α} {f : α → Bool} : filter f (wfParam xs) = filter f xs.attach.unattach

theorem List.filter_unattach {α : Type u_1} {P : α → Prop} {xs : List (Subtype P)} {f : α → Bool} : filter f xs.unattach = (filter (fun (x : Subtype P) => match x with | ⟨x, h⟩ => binderNameHint x f (binderNameHint h () (f (wfParam x)))) xs).unattach

theorem List.reverse_wfParam {α : Type u_1} {xs : List α} : (wfParam xs).reverse = xs.attach.unattach.reverse

theorem List.reverse_unattach {α : Type u_1} {P : α → Prop} {xs : List (Subtype P)} : xs.unattach.reverse = xs.reverse.unattach

theorem List.filterMap_wfParam {α : Type u_1} {β : Type u_2} {xs : List α} {f : α → Option β} : filterMap f (wfParam xs) = filterMap f xs.attach.unattach

theorem List.filterMap_unattach {α : Type u_1} {β : Type u_2} {P : α → Prop} {xs : List (Subtype P)} {f : α → Option β} : filterMap f xs.unattach = filterMap (fun (x : Subtype P) => match x with | ⟨x, h⟩ => binderNameHint x f (binderNameHint h () (f (wfParam x)))) xs

theorem List.flatMap_wfParam {α : Type u_1} {β : Type u_2} {xs : List α} {f : α → List β} : flatMap f (wfParam xs) = flatMap f xs.attach.unattach

theorem List.flatMap_unattach {α : Type u_1} {β : Type u_2} {P : α → Prop} {xs : List (Subtype P)} {f : α → List β} : flatMap f xs.unattach = flatMap (fun (x : Subtype P) => match x with | ⟨x, h⟩ => binderNameHint x f (binderNameHint h () (f (wfParam x)))) xs