blob: fccafe5507f839e5a0bf308244a4ade948541b08 [file]
/-
Copyright (c) 2024 Lean FRO. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Kim Morrison
-/
module
prelude
import all Init.Data.Option.Instances
public import Init.Control.Lawful
public import Init.Data.Option.Lemmas
public section
namespace Option
@[simp, grind =] theorem bindM_none [Pure m] (f : α → m (Option β)) : none.bindM f = pure none := rfl
@[simp, grind =] theorem bindM_some [Pure m] (a) (f : α → m (Option β)) : (some a).bindM f = f a := by
simp [Option.bindM]
-- We simplify `Option.forM` to `forM`.
@[simp] theorem forM_eq_forM [Monad m] : @Option.forM m α _ = forM := rfl
@[simp, grind =] theorem forM_none [Monad m] (f : α → m PUnit) :
forM none f = pure .unit := rfl
@[simp, grind =] theorem forM_some [Monad m] (f : α → m PUnit) (a : α) :
forM (some a) f = f a := rfl
@[simp, grind =] theorem forM_map [Monad m] [LawfulMonad m] (o : Option α) (g : α → β) (f : β → m PUnit) :
forM (o.map g) f = forM o (fun a => f (g a)) := by
cases o <;> simp
theorem forM_join [Monad m] [LawfulMonad m] (o : Option (Option α)) (f : α → m PUnit) :
forM o.join f = forM o (forM · f) := by
cases o <;> simp
@[simp, grind =] theorem forIn'_none [Monad m] (b : β) (f : (a : α) → a ∈ none → β → m (ForInStep β)) :
forIn' none b f = pure b := by
rfl
@[simp, grind =] theorem forIn'_some [Monad m] [LawfulMonad m] (a : α) (b : β) (f : (a' : α) → a' ∈ some a → β → m (ForInStep β)) :
forIn' (some a) b f = bind (f a rfl b) (fun r => pure (ForInStep.value r)) := by
simp only [forIn', bind_pure_comp]
rw [map_eq_pure_bind]
congr
funext x
split <;> simp
@[simp, grind =] theorem forIn_none [Monad m] (b : β) (f : α → β → m (ForInStep β)) :
forIn none b f = pure b := by
rfl
@[simp, grind =] theorem forIn_some [Monad m] [LawfulMonad m] (a : α) (b : β) (f : α → β → m (ForInStep β)) :
forIn (some a) b f = bind (f a b) (fun r => pure (ForInStep.value r)) := by
simp only [forIn, forIn', bind_pure_comp]
rw [map_eq_pure_bind]
congr
funext x
split <;> simp
@[congr] theorem forIn'_congr [Monad m] [LawfulMonad m] {as bs : Option α} (w : as = bs)
{b b' : β} (hb : b = b')
{f : (a' : α) → a' ∈ as → β → m (ForInStep β)}
{g : (a' : α) → a' ∈ bs → β → m (ForInStep β)}
(h : ∀ a m b, f a (by simpa [w] using m) b = g a m b) :
forIn' as b f = forIn' bs b' g := by
cases as <;> cases bs
· simp [hb]
· simp at w
· simp at w
· simp only [some.injEq] at w
subst w
simp [hb, h]
theorem forIn'_eq_pelim [Monad m] [LawfulMonad m]
(o : Option α) (f : (a : α) → a ∈ o → β → m (ForInStep β)) (b : β) :
forIn' o b f =
o.pelim (pure b) (fun a h => ForInStep.value <$> f a h b) := by
cases o <;> simp
@[simp] theorem forIn'_yield_eq_pelim [Monad m] [LawfulMonad m] (o : Option α)
(f : (a : α) → a ∈ o → β → m γ) (g : (a : α) → a ∈ o → β → γ → β) (b : β) :
forIn' o b (fun a m b => (fun c => .yield (g a m b c)) <$> f a m b) =
o.pelim (pure b) (fun a h => g a h b <$> f a h b) := by
cases o <;> simp
@[simp] theorem forIn'_pure_yield_eq_pelim [Monad m] [LawfulMonad m]
(o : Option α) (f : (a : α) → a ∈ o → β → β) (b : β) :
forIn' o b (fun a m b => pure (.yield (f a m b))) =
pure (f := m) (o.pelim b (fun a h => f a h b)) := by
cases o <;> simp
@[simp] theorem idRun_forIn'_yield_eq_pelim
(o : Option α) (f : (a : α) → a ∈ o → β → Id β) (b : β) :
(forIn' o b (fun a m b => .yield <$> f a m b)).run =
o.pelim b (fun a h => f a h b |>.run) :=
forIn'_pure_yield_eq_pelim _ _ _
@[simp, grind =] theorem forIn'_map [Monad m] [LawfulMonad m]
(o : Option α) (g : α → β) (f : (b : β) → b ∈ o.map g → γ → m (ForInStep γ)) :
forIn' (o.map g) init f = forIn' o init fun a h y => f (g a) (mem_map_of_mem g h) y := by
cases o <;> simp
theorem forIn'_join [Monad m] [LawfulMonad m] (b : β) (o : Option (Option α))
(f : (a : α) → a ∈ o.join → β → m (ForInStep β)) :
forIn' o.join b f = forIn' o b (fun o' ho' b => ForInStep.yield <$> forIn' o' b (fun a ha b' => f a (by simp_all) b')) := by
cases o with
| none => simp
| some a => simpa using forIn'_congr rfl rfl (by simp)
theorem forIn_eq_elim [Monad m] [LawfulMonad m]
(o : Option α) (f : (a : α) → β → m (ForInStep β)) (b : β) :
forIn o b f =
o.elim (pure b) (fun a => ForInStep.value <$> f a b) := by
cases o <;> simp
@[simp] theorem forIn_yield_eq_elim [Monad m] [LawfulMonad m] (o : Option α)
(f : (a : α) → β → m γ) (g : (a : α) → β → γ → β) (b : β) :
forIn o b (fun a b => (fun c => .yield (g a b c)) <$> f a b) =
o.elim (pure b) (fun a => g a b <$> f a b) := by
cases o <;> simp
@[simp] theorem forIn_pure_yield_eq_elim [Monad m] [LawfulMonad m]
(o : Option α) (f : (a : α) → β → β) (b : β) :
forIn o b (fun a b => pure (.yield (f a b))) =
pure (f := m) (o.elim b (fun a => f a b)) := by
cases o <;> simp
@[simp] theorem idRun_forIn_yield_eq_elim
(o : Option α) (f : (a : α) → β → Id β) (b : β) :
(forIn o b (fun a b => .yield <$> f a b)).run =
o.elim b (fun a => f a b |>.run) :=
forIn_pure_yield_eq_elim _ _ _
@[simp, grind =] theorem forIn_map [Monad m] [LawfulMonad m]
(o : Option α) (g : α → β) (f : β → γ → m (ForInStep γ)) :
forIn (o.map g) init f = forIn o init fun a y => f (g a) y := by
cases o <;> simp
theorem forIn_join [Monad m] [LawfulMonad m]
(o : Option (Option α)) (f : α → β → m (ForInStep β)) :
forIn o.join init f = forIn o init (fun o' b => ForInStep.yield <$> forIn o' b f) := by
cases o <;> simp
@[simp, grind =] theorem elimM_pure [Monad m] [LawfulMonad m] (x : Option α) (y : m β) (z : α → m β) :
Option.elimM (pure x : m (Option α)) y z = x.elim y z := by
simp [Option.elimM]
@[simp, grind =] theorem elimM_bind [Monad m] [LawfulMonad m] (x : m α) (f : α → m (Option β))
(y : m γ) (z : β → m γ) : Option.elimM (x >>= f) y z = (do Option.elimM (f (← x)) y z) := by
simp [Option.elimM]
@[simp, grind =] theorem elimM_map [Monad m] [LawfulMonad m] (x : m α) (f : α → Option β)
(y : m γ) (z : β → m γ) : Option.elimM (f <$> x) y z = (do Option.elim (f (← x)) y z) := by
simp [Option.elimM]
@[simp, grind =] theorem tryCatch_eq_or (o : Option α) (alternative : Unit → Option α) :
tryCatch o alternative = o.or (alternative ()) := by cases o <;> rfl
@[simp, grind =] theorem throw_eq_none : throw () = (none : Option α) := rfl
@[simp, grind =] theorem filterM_none [Applicative m] (p : α → m Bool) :
none.filterM p = pure none := rfl
@[grind =] theorem filterM_some [Applicative m] (p : α → m Bool) (a : α) :
(some a).filterM p = (fun b => if b then some a else none) <$> p a := rfl
theorem sequence_join [Applicative m] [LawfulApplicative m] {o : Option (Option (m α))} :
o.join.sequence = join <$> sequence (o.map sequence) := by
cases o <;> simp
theorem bindM_join [Pure m] {f : α → m (Option β)} {o : Option (Option α)} :
o.join.bindM f = o.bindM (·.bindM f) := by
cases o <;> simp
theorem mapM_join [Applicative m] [LawfulApplicative m] {f : α → m β} {o : Option (Option α)} :
o.join.mapM f = join <$> o.mapM (Option.mapM f) := by
cases o <;> simp
theorem mapM_guard [Applicative m] {x : α} {p : α → Bool} {f : α → m β} :
(guard p x).mapM f = if p x then some <$> f x else pure none := by
simp only [guard_eq_ite]
split <;> simp
end Option