instance Option.instSubsingletonSubtypeEqSome {α : Type u_1} {o : Option α} : Subsingleton { x : α // o = some x }

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

def Option.attachWith {α : Type u_1} (xs : Option α) (P : α → Prop) (H : ∀ (x : α), xs = some x → P x) : Option { x : α // P x }

“Attaches” a proof that some predicate holds for an optional value, if present, returning a subtype that expresses this fact.

This function is primarily used to implement Option.attach, which allows definitions by well-founded recursion that use iteration operators (such as Option.map) to prove that an optional value drawn from a parameter is smaller than the parameter. This allows the well-founded recursion mechanism to prove that the function terminates.

Equations

• none.attachWith P H_2 = none
• (some x).attachWith P H_2 = some ⟨x, ⋯⟩

@[inline]

def Option.attach {α : Type u_1} (xs : Option α) : Option { x : α // xs = some x }

“Attaches” a proof that an optional value, if present, is indeed this value, returning a subtype that expresses this fact.

This function is primarily used to allow definitions by well-founded recursion that use iteration operators (such as Option.map) to prove that an optional value drawn from a parameter is smaller than the parameter. This allows the well-founded recursion mechanism to prove that the function terminates.

Equations

• xs.attach = xs.attachWith (fun (x : α) => xs = some x) ⋯

@[simp]

theorem Option.attach_none {α : Type u_1} : none.attach = none

@[simp]

theorem Option.attachWith_none {α : Type u_1} {P : α → Prop} {H : ∀ (x : α), none = some x → P x} : none.attachWith P H = none

@[simp]

theorem Option.attach_some {α : Type u_1} {x : α} : (some x).attach = some ⟨x, ⋯⟩

@[simp]

theorem Option.attachWith_some {α : Type u_1} {x : α} {P : α → Prop} (h : ∀ (b : α), some x = some b → P b) : (some x).attachWith P h = some ⟨x, ⋯⟩

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

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

theorem Option.attach_map_val {α : Type u_1} {β : Type u_2} (o : Option α) (f : α → β) : Option.map (fun (i : { i : α // o = some i }) => f i.val) o.attach = Option.map f o

@[simp]

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

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

@[simp]

theorem Option.attachWith_map_subtype_val {α : Type u_1} {p : α → Prop} (o : Option α) (H : ∀ (a : α), o = some a → p a) : Option.map Subtype.val (o.attachWith p H) = o

theorem Option.attach_eq_some {α : Type u_1} (o : Option α) (x : { x : α // o = some x }) : o.attach = some x

theorem Option.mem_attach {α : Type u_1} (o : Option α) (x : { x : α // o = some x }) : x ∈ o.attach

@[simp]

theorem Option.isNone_attach {α : Type u_1} (o : Option α) : o.attach.isNone = o.isNone

@[simp]

theorem Option.isNone_attachWith {α : Type u_1} {p : α → Prop} (o : Option α) (H : ∀ (a : α), o = some a → p a) : (o.attachWith p H).isNone = o.isNone

@[simp]

theorem Option.isSome_attach {α : Type u_1} (o : Option α) : o.attach.isSome = o.isSome

@[simp]

theorem Option.isSome_attachWith {α : Type u_1} {p : α → Prop} (o : Option α) (H : ∀ (a : α), o = some a → p a) : (o.attachWith p H).isSome = o.isSome

@[simp]

theorem Option.attach_eq_none_iff {α : Type u_1} {o : Option α} : o.attach = none ↔ o = none

@[simp]

theorem Option.attach_eq_some_iff {α : Type u_1} {o : Option α} {x : { x : α // o = some x }} : o.attach = some x ↔ o = some x.val

@[simp]

theorem Option.attachWith_eq_none_iff {α : Type u_1} {p : α → Prop} {o : Option α} (H : ∀ (a : α), o = some a → p a) : o.attachWith p H = none ↔ o = none

@[simp]

theorem Option.attachWith_eq_some_iff {α : Type u_1} {p : α → Prop} {o : Option α} (H : ∀ (a : α), o = some a → p a) {x : { x : α // p x }} : o.attachWith p H = some x ↔ o = some x.val

@[simp]

theorem Option.get_attach {α : Type u_1} {o : Option α} (h : o.attach.isSome = true) : o.attach.get h = ⟨o.get ⋯, ⋯⟩

@[simp]

theorem Option.getD_attach {α : Type u_1} {o : Option α} {fallback : { x : α // o = some x }} : o.attach.getD fallback = fallback

@[simp]

theorem Option.get!_attach {α : Type u_1} {o : Option α} [Inhabited { x : α // o = some x }] : o.attach.get! = default

@[simp]

theorem Option.get_attachWith {α : Type u_1} {p : α → Prop} {o : Option α} (H : ∀ (a : α), o = some a → p a) (h : (o.attachWith p H).isSome = true) : (o.attachWith p H).get h = ⟨o.get ⋯, ⋯⟩

@[simp]

theorem Option.getD_attachWith {α : Type u_1} {p : α → Prop} {o : Option α} {h : ∀ (x : α), o = some x → p x} {fallback : { x : α // p x }} : (o.attachWith p h).getD fallback = ⟨o.getD fallback.val, ⋯⟩

theorem Option.toList_attach {α : Type u_1} (o : Option α) : o.attach.toList = List.map (fun (x : { x : α // x ∈ o.toList }) => ⟨x.val, ⋯⟩) o.toList.attach

theorem Option.toList_attachWith {α : Type u_1} {p : α → Prop} {o : Option α} {h : ∀ (x : α), o = some x → p x} : (o.attachWith p h).toList = List.map (fun (x : { x : α // x ∈ o.toList }) => ⟨x.val, ⋯⟩) o.toList.attach

theorem Option.toArray_attach {α : Type u_1} (o : Option α) : o.attach.toArray = Array.map (fun (x : { x : α // x ∈ o.toArray }) => ⟨x.val, ⋯⟩) o.toArray.attach

theorem Option.toArray_attachWith {α : Type u_1} {p : α → Prop} {o : Option α} {h : ∀ (x : α), o = some x → p x} : (o.attachWith p h).toArray = Array.map (fun (x : { x : α // x ∈ o.toArray }) => ⟨x.val, ⋯⟩) o.toArray.attach

@[simp]

theorem Option.attach_toList {α : Type u_1} (o : Option α) : o.toList.attach = (Option.map (fun (x : { x : α // o = some x }) => match x with | ⟨a, h⟩ => ⟨a, ⋯⟩) o.attach).toList

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

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

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

@[simp]

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

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

@[simp]

theorem Option.map_attach_eq_attachWith {α : Type u_1} {o : Option α} {p : α → Prop} (f : ∀ (a : α), o = some a → p a) : Option.map (fun (x : { x : α // o = some x }) => ⟨x.val, ⋯⟩) o.attach = o.attachWith p f

theorem Option.attach_bind {α : Type u_1} {β : Type u_2} {o : Option α} {f : α → Option β} : (o.bind f).attach = o.attach.bind fun (x : { x : α // o = some x }) => match x with | ⟨x, h⟩ => Option.map (fun (x_1 : { x_1 : β // f x = some x_1 }) => match x_1 with | ⟨y, h'⟩ => ⟨y, ⋯⟩) (f x).attach

theorem Option.bind_attach {α : Type u_1} {β : Type u_2} {o : Option α} {f : { x : α // o = some x } → Option β} : o.attach.bind f = o.pbind fun (a : α) (h : o = some a) => f ⟨a, h⟩

theorem Option.pbind_eq_bind_attach {α : Type u_1} {β : Type u_2} {o : Option α} {f : (a : α) → o = some a → Option β} : o.pbind f = o.attach.bind fun (x : { x : α // o = some x }) => match x with | ⟨x, h⟩ => f x h

theorem Option.attach_filter {α : Type u_1} {o : Option α} {p : α → Bool} : (Option.filter p o).attach = o.attach.bind fun (x : { x : α // o = some x }) => match x with | ⟨x, h⟩ => if h' : p x = true then some ⟨x, ⋯⟩ else none

theorem Option.filter_attachWith {α : Type u_1} {P : α → Prop} {o : Option α} {h : ∀ (x : α), o = some x → P x} {q : α → Bool} : (Option.filter q do let a ← o.attachWith P h pure a.val) = do let a ← (Option.filter q o).attachWith P ⋯ pure a.val

theorem Option.filter_attach {α : Type u_1} {o : Option α} {p : { x : α // o = some x } → Bool} : Option.filter p o.attach = o.pbind fun (a : α) (h : o = some a) => if p ⟨a, h⟩ = true then some ⟨a, h⟩ else none

theorem Option.toList_pbind {α : Type u_1} {β : Type u_2} {o : Option α} {f : (a : α) → o = some a → Option β} : (o.pbind f).toList = List.flatMap (fun (x : { x : α // o = some x }) => match x with | ⟨x, h⟩ => (f x h).toList) o.attach.toList

theorem Option.toArray_pbind {α : Type u_1} {β : Type u_2} {o : Option α} {f : (a : α) → o = some a → Option β} : (o.pbind f).toArray = Array.flatMap (fun (x : { x : α // o = some x }) => match x with | ⟨x, h⟩ => (f x h).toArray) o.attach.toArray

theorem Option.toList_pfilter {α : Type u_1} {o : Option α} {p : (a : α) → o = some a → Bool} : (o.pfilter p).toList = (List.filter (fun (x : { x : α // x ∈ o.toList }) => p x.val ⋯) o.toList.attach).unattach

theorem Option.toArray_pfilter {α : Type u_1} {o : Option α} {p : (a : α) → o = some a → Bool} : (o.pfilter p).toArray = (Array.filter (fun (x : { x : α // x ∈ o.toArray }) => p x.val ⋯) o.toArray.attach).unattach

theorem Option.toList_pmap {α : Type u_1} {β : Type u_2} {p : α → Prop} {o : Option α} {f : (a : α) → p a → β} (h : ∀ (a : α), o = some a → p a) : (pmap f o h).toList = List.map (fun (x : { x : α // o = some x }) => f x.val ⋯) o.attach.toList

theorem Option.toArray_pmap {α : Type u_1} {β : Type u_2} {p : α → Prop} {o : Option α} {f : (a : α) → p a → β} (h : ∀ (a : α), o = some a → p a) : (pmap f o h).toArray = Array.map (fun (x : { x : α // o = some x }) => f x.val ⋯) o.attach.toArray

theorem Option.attach_pfilter {α : Type u_1} {o : Option α} {p : (a : α) → o = some a → Bool} : (o.pfilter p).attach = o.attach.pbind fun (x : { x : α // o = some x }) (h : o.attach = some x) => if h' : p x.val ⋯ = true then some ⟨x.val, ⋯⟩ else none

theorem Option.attach_guard {α : Type u_1} {p : α → Bool} {x : α} : (guard p x).attach = if h : p x = true then some ⟨x, ⋯⟩ else none

theorem Option.attachWith_guard {α : Type u_1} {q : α → Bool} {x : α} {P : α → Prop} {h : ∀ (a : α), guard q x = some a → P a} : (guard q x).attachWith P h = if h' : q x = true then some ⟨x, ⋯⟩ else none

unattach

Option.unattach is the (one-sided) inverse of Option.attach. It is a synonym for Option.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 : Option { 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.

@[implicit_reducible]

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

Remove an attached proof that the value in an Option is indeed that value.

This function is usually inserted automatically by Lean, rather than 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 [Option.unattach, -Option.map_subtype].

It is a synonym for Option.map Subtype.val.

Equations

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

@[simp]

theorem Option.unattach_none {α : Type u_1} {p : α → Prop} : none.unattach = none

@[simp]

theorem Option.unattach_some {α : Type u_1} {p : α → Prop} {a : { x : α // p x }} : (some a).unattach = some a.val

@[simp]

theorem Option.isSome_unattach {α : Type u_1} {p : α → Prop} {o : Option { x : α // p x }} : o.unattach.isSome = o.isSome

@[simp]

theorem Option.isNone_unattach {α : Type u_1} {p : α → Prop} {o : Option { x : α // p x }} : o.unattach.isNone = o.isNone

@[simp]

theorem Option.unattach_attach {α : Type u_1} (o : Option α) : o.attach.unattach = o

@[simp]

theorem Option.unattach_attachWith {α : Type u_1} {p : α → Prop} {o : Option α} {H : ∀ (a : α), o = some a → p a} : (o.attachWith p H).unattach = o

theorem Option.unattach_eq_some_iff {α : Type u_1} {p : α → Prop} {o : Option { x : α // p x }} {x : α} : o.unattach = some x ↔ ∃ (h : p x), o = some ⟨x, h⟩

@[simp]

theorem Option.unattach_eq_none_iff {α : Type u_1} {p : α → Prop} {o : Option { x : α // p x }} : o.unattach = none ↔ o = none

theorem Option.get_unattach {α : Type u_1} {p : α → Prop} {o : Option { x : α // p x }} {h : o.unattach.isSome = true} : o.unattach.get h = (o.get ⋯).val

theorem Option.toList_unattach {α : Type u_1} {p : α → Prop} {o : Option { x : α // p x }} : o.unattach.toList = o.toList.unattach

theorem Option.toArray_unattach {α : Type u_1} {p : α → Prop} {o : Option { x : α // p x }} : o.unattach.toArray = o.toArray.unattach

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

@[simp]

theorem Option.map_subtype {α : Type u_1} {β : Type u_2} {p : α → Prop} {o : Option { x : α // p x }} {f : { x : α // p x } → β} {g : α → β} (hf : ∀ (x : α) (h : p x), f ⟨x, h⟩ = g x) : Option.map f o = Option.map g o.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 Option.bind_subtype {α : Type u_1} {β : Type u_2} {p : α → Prop} {o : Option { x : α // p x }} {f : { x : α // p x } → Option β} {g : α → Option β} (hf : ∀ (x : α) (h : p x), f ⟨x, h⟩ = g x) : o.bind f = o.unattach.bind g

@[simp]

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

@[simp]

theorem Option.unattach_guard {α : Type u_1} {p : α → Prop} {q : { x : α // p x } → Bool} {r : α → Bool} (hq : ∀ (x : α) (h : p x), q ⟨x, h⟩ = r x) {x : { x : α // p x }} : (guard q x).unattach = guard r x.val

@[simp]

theorem Option.unattach_pfilter {α : Type u_1} {p : α → Prop} {o : Option { x : α // p x }} {f : (a : { x : α // p x }) → o = some a → Bool} {g : (a : α) → o.unattach = some a → Bool} (hf : ∀ (x : α) (h : p x) (h' : o = some ⟨x, h⟩), f ⟨x, h⟩ h' = g x ⋯) : (o.pfilter f).unattach = o.unattach.pfilter g

@[simp]

theorem Option.unattach_merge {α : Type u_1} {p : α → Prop} {f : { x : α // p x } → { x : α // p x } → { x : α // p x }} {g : α → α → α} (hf : ∀ (x : α) (h : p x) (y : α) (h' : p y), (f ⟨x, h⟩ ⟨y, h'⟩).val = g x y) {o o' : Option { x : α // p x }} : (merge f o o').unattach = merge g o.unattach o'.unattach

theorem Option.any_attach {α : Type u_1} {p : α → Bool} {o : Option α} {q : { x : α // o = some x } → Bool} (h : ∀ (x : α) (h : o = some x), q ⟨x, h⟩ = p x) : Option.any q o.attach = Option.any p o

theorem Option.any_attachWith {α : Type u_1} {p : α → Bool} {o : Option α} {r : α → Prop} (hr : ∀ (x : α), o = some x → r x) {q : { x : α // r x } → Bool} (h : ∀ (x : α) (h : r x), q ⟨x, h⟩ = p x) : Option.any q (o.attachWith r hr) = Option.any p o

theorem Option.any_unattach {α : Type u_1} {p : α → Prop} {o : Option { x : α // p x }} {q : α → Bool} : Option.any q o.unattach = Option.any (q ∘ Subtype.val) o

theorem Option.all_attach {α : Type u_1} {p : α → Bool} {o : Option α} {q : { x : α // o = some x } → Bool} (h : ∀ (x : α) (h : o = some x), q ⟨x, h⟩ = p x) : Option.all q o.attach = Option.all p o

theorem Option.all_attachWith {α : Type u_1} {p : α → Bool} {o : Option α} {r : α → Prop} (hr : ∀ (x : α), o = some x → r x) {q : { x : α // r x } → Bool} (h : ∀ (x : α) (h : r x), q ⟨x, h⟩ = p x) : Option.all q (o.attachWith r hr) = Option.all p o

theorem Option.all_unattach {α : Type u_1} {p : α → Prop} {o : Option { x : α // p x }} {q : α → Bool} : Option.all q o.unattach = Option.all (q ∘ Subtype.val) o

@[instance_reducible, always_inline]

instance Option.instMonadAttach : MonadAttach Option

Equations

• Option.instMonadAttach = { CanReturn := fun {α : Type ?u.1} (x : Option α) (a : α) => x = some a, attach := fun {α : Type ?u.1} (x : Option α) => x.attach }

instance Option.instLawfulMonadAttach : LawfulMonadAttach Option

instance OptionT.instWeaklyLawfulMonadAttachOfLawfulMonad {m : Type u_1 → Type u_2} [Monad m] [MonadAttach m] [LawfulMonad m] [WeaklyLawfulMonadAttach m] : WeaklyLawfulMonadAttach (OptionT m)

instance OptionT.instLawfulMonadAttachOfLawfulMonad {m : Type u_1 → Type u_2} [Monad m] [MonadAttach m] [LawfulMonad m] [LawfulMonadAttach m] : LawfulMonadAttach (OptionT m)