blob: 3adc32dd525f7dc361a4961ae02e29ed3e0da549 [file]
/-
Copyright (c) 2025 Lean FRO, LLC. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Paul Reichert
-/
module
prelude
public import Init.Control.Lawful.Basic
public import Init.Control.Lawful.MonadLift.Basic
public import Init.Ext
public import Init.NotationExtra
import Init.Data.Subtype.Basic
import Init.PropLemmas
public section
namespace Std.Iterators
/--
`PostconditionT m α` represents an operation in the monad `m` together with a
intrinsic proof that some postcondition holds for the `α` valued monadic result.
It consists of a predicate `P` about `α` and an element of `m ({ a // P a })` and is a helpful tool
for intrinsic verification, notably termination proofs, in the context of iterators.
`PostconditionT m` is a monad if `m` is. However, note that `PostconditionT m α` is a structure,
so that the compiler will generate inefficient code from recursive functions returning
`PostconditionT m α`. Optimizations for `ReaderT`, `StateT` etc. aren't applicable for structures.
Moreover, `PostconditionT m α` is not a well-behaved monad transformer because `PostconditionT.lift`
neither commutes with `pure` nor with `bind`.
-/
@[unbox]
structure PostconditionT (m : Type w → Type w') (α : Type w) where
/--
A predicate that holds for the return value(s) of the `m`-monadic operation.
-/
Property : α → Prop
/--
The actual monadic operation. Its return value is bundled together with a proof that
it satisfies `Property`.
-/
operation : m (Subtype Property)
/--
Lifts an operation from `m` to `PostconditionT m` without asserting any nontrivial postcondition.
Caution: `lift` is not a lawful lift function.
For example, `pure a : PostconditionT m α` is not the same as
`PostconditionT.lift (pure a : m α)`.
-/
@[always_inline, inline, expose]
def PostconditionT.lift {α : Type w} {m : Type w → Type w'} [Functor m] (x : m α) :
PostconditionT m α :=
⟨fun _ => True, (⟨·, .intro⟩) <$> x⟩
@[always_inline, inline, expose]
def PostconditionT.attachLift {α : Type w} {m : Type w → Type w'} [MonadAttach m]
(x : m α) : PostconditionT m α :=
⟨MonadAttach.CanReturn x, MonadAttach.attach x⟩
@[always_inline, inline, expose]
protected def PostconditionT.pure {m : Type w → Type w'} [Pure m] {α : Type w}
(a : α) : PostconditionT m α :=
⟨fun y => a = y, pure <| ⟨a, rfl⟩⟩
/--
Lifts a monadic value from `m { a : α // P a }` to a value `PostconditionT m α`.
-/
@[always_inline, inline]
def PostconditionT.liftWithProperty {α : Type w} {m : Type w → Type w'} {P : α → Prop}
(x : m { α // P α }) : PostconditionT m α :=
⟨P, x⟩
/--
Given a function `f : α → β`, returns a function `PostconditionT m α → PostconditionT m β`,
turning `PostconditionT m` into a functor.
The postcondition of the `x.map f` states that the return value is the image under `f` of some
`a : α` satisfying the `x.Property`.
-/
@[always_inline, inline, expose]
protected def PostconditionT.map {m : Type w → Type w'} [Functor m] {α : Type w} {β : Type w}
(f : α → β) (x : PostconditionT m α) : PostconditionT m β :=
⟨fun b => ∃ a : Subtype x.Property, f a.1 = b,
(fun a => ⟨f a.val, _, rfl⟩) <$> x.operation⟩
/--
Given a function `α → PostconditionT m β`, returns a function
`PostconditionT m α → PostconditionT m β`, turning `PostconditionT m` into a monad.
-/
@[always_inline, inline, expose]
protected def PostconditionT.bind {m : Type w → Type w'} [Monad m] {α : Type w} {β : Type w}
(x : PostconditionT m α) (f : α → PostconditionT m β) : PostconditionT m β :=
⟨fun b => ∃ a, x.Property a ∧ (f a).Property b,
x.operation >>= fun a =>
(fun b =>
⟨b.val, a.val, a.property, b.property⟩) <$> (f a).operation⟩
/--
A version of `bind` that provides a proof of the previous postcondition to the mapping function.
-/
@[always_inline, inline]
protected def PostconditionT.pbind {m : Type w → Type w'} [Monad m] {α : Type w} {β : Type w}
(x : PostconditionT m α) (f : Subtype x.Property → PostconditionT m β) : PostconditionT m β :=
⟨fun b => ∃ a, (f a).Property b,
x.operation >>= fun a => (fun b => ⟨b.val, a, b.property⟩) <$> (f a).operation⟩
/--
Lifts an operation from `m` to `PostConditionT m` and then applies `PostconditionT.map`.
-/
@[always_inline, inline]
protected def PostconditionT.liftMap {m : Type w → Type w'} [Monad m] {α : Type w} {β : Type w}
(f : α → β) (x : m α) : PostconditionT m β :=
⟨fun b => ∃ a, f a = b, (fun a => ⟨f a, a, rfl⟩) <$> x⟩
/--
Converts an operation from `PostConditionT m` to `m`, discarding the postcondition.
-/
@[always_inline, inline]
def PostconditionT.run {m : Type w → Type w'} [Monad m] {α : Type w} (x : PostconditionT m α) :
m α :=
(fun a => a.val) <$> x.operation
theorem PostconditionT.run_eq_map {m : Type w → Type w'} [Monad m] {α : Type w}
{x : PostconditionT m α} :
x.run = Subtype.val <$> x.operation :=
(rfl)
instance {m : Type w → Type w'} [Functor m] : Functor (PostconditionT m) where
map := PostconditionT.map
instance {m : Type w → Type w'} [Monad m] : Monad (PostconditionT m) where
pure := PostconditionT.pure
bind := PostconditionT.bind
theorem PostconditionT.pure_eq_pure {m : Type w → Type w'} [Monad m] {α} {a : α} :
pure a = PostconditionT.pure (m := m) a :=
rfl
@[simp]
theorem PostconditionT.property_pure {m : Type w → Type w'} [Monad m] {α : Type w}
{x : α} :
(pure x : PostconditionT m α).Property = (x = ·) := by
rfl
@[simp]
theorem PostconditionT.operation_pure {m : Type w → Type w'} [Monad m] {α : Type w}
{x : α} :
(pure x : PostconditionT m α).operation = pure ⟨x, property_pure (m := m) ▸ rfl⟩ := by
rfl
theorem PostconditionT.ext {m : Type w → Type w'} [Monad m] [LawfulMonad m]
{α : Type w} {x y : PostconditionT m α}
(h : x.Property = y.Property) (h' : (fun p => ⟨p.1, h ▸ p.2⟩) <$> x.operation = y.operation) :
x = y := by
cases x; cases y; cases h
simpa using h'
theorem PostconditionT.ext_iff {m : Type w → Type w'} [Monad m] [LawfulMonad m]
{α : Type w} {x y : PostconditionT m α} :
x = y ↔ ∃ h : x.Property = y.Property, (fun p => ⟨p.1, h ▸ p.2⟩) <$> x.operation = y.operation := by
constructor
· rintro rfl
exact ⟨rfl, by simp⟩
· rintro ⟨h, h'⟩
exact PostconditionT.ext h h'
@[simp]
protected theorem PostconditionT.map_eq_pure_bind {m : Type w → Type w'} [Monad m] [LawfulMonad m]
{α : Type w} {β : Type w} {f : α → β} {x : PostconditionT m α} :
x.map f = x.bind (pure ∘ f) := by
apply PostconditionT.ext <;> simp [PostconditionT.map, PostconditionT.bind]
@[simp]
protected theorem PostconditionT.pure_bind {m : Type w → Type w'} [Monad m] [LawfulMonad m]
{α : Type w} {β : Type w} {f : α → PostconditionT m β} {a : α} :
(pure a : PostconditionT m α).bind f = f a := by
apply PostconditionT.ext <;> simp [pure, PostconditionT.pure, PostconditionT.bind]
@[simp]
protected theorem PostconditionT.bind_pure {m : Type w → Type w'} [Monad m] [LawfulMonad m]
{α : Type w} {x : PostconditionT m α} :
x.bind pure = x := by
apply PostconditionT.ext <;> simp [pure, PostconditionT.pure, PostconditionT.bind]
@[simp]
protected theorem PostconditionT.bind_assoc {m : Type w → Type w'} [Monad m] [LawfulMonad m]
{α β γ: Type w} {x : PostconditionT m α} {f : α → PostconditionT m β} {g : β → PostconditionT m γ} :
(x.bind f).bind g = x.bind (fun a => (f a).bind g) := by
apply PostconditionT.ext
· simp [PostconditionT.bind]
· simp only [PostconditionT.bind, bind_assoc, bind_map_left, map_bind, Functor.map_map]
ext c
constructor
· rintro ⟨b, ⟨a, ha, hb⟩, h⟩
exact ⟨a, ha, b, hb, h⟩
· rintro ⟨a, ha, b, hb, h⟩
exact ⟨b, ⟨a, ha, hb⟩, h⟩
@[simp]
protected theorem PostconditionT.map_pure {m : Type w → Type w'} [Monad m] [LawfulMonad m]
{α : Type w} {β : Type w} {f : α → β} {a : α} :
(pure a : PostconditionT m α).map f = pure (f a) := by
apply PostconditionT.ext <;> simp [pure, PostconditionT.map, PostconditionT.pure]
instance [Monad m] [LawfulMonad m] : LawfulMonad (PostconditionT m) where
map_const {α β} := by ext a x; simp [Functor.mapConst, Functor.map]
id_map {α} x := by simp [Functor.map]
comp_map {α β γ} g h := by intro x; simp [Functor.map]; rfl
seqLeft_eq {α β} x y := by simp [SeqLeft.seqLeft, Functor.map, Seq.seq]; rfl
seqRight_eq {α β} x y := by simp [Seq.seq, SeqRight.seqRight, Functor.map]
pure_seq g x := by simp [Seq.seq, Functor.map]
bind_pure_comp f x := by simp [Functor.map, Bind.bind]; rfl
bind_map f x := by simp [Seq.seq, Functor.map]; rfl
pure_bind x f := PostconditionT.pure_bind
bind_assoc x f g := PostconditionT.bind_assoc
@[simp]
theorem PostconditionT.property_map {m : Type w → Type w'} [Functor m] {α : Type w} {β : Type w}
{x : PostconditionT m α} {f : α → β} {b : β} :
(x.map f).Property b ↔ (∃ a, f a = b ∧ x.Property a) := by
simp only [PostconditionT.map]
apply Iff.intro
· rintro ⟨⟨a, ha⟩, h⟩
exact ⟨a, h, ha⟩
· rintro ⟨a, h, ha⟩
exact ⟨⟨a, ha⟩, h⟩
@[simp]
theorem PostconditionT.operation_map {m : Type w → Type w'} [Functor m] {α : Type w} {β : Type w}
{x : PostconditionT m α} {f : α → β} :
(x.map f).operation =
(fun a => ⟨_, (property_map (m := m)).mpr ⟨a.1, rfl, a.2⟩⟩) <$> x.operation := by
rfl
@[simp]
theorem PostconditionT.operation_bind {m : Type w → Type w'} [Monad m] {α : Type w} {β : Type w}
{x : PostconditionT m α} {f : α → PostconditionT m β} :
(x.bind f).operation = (do
let a ← x.operation
(fun fa => ⟨fa.1, by exact⟨a.1, a.2, fa.2⟩⟩) <$> (f a.1).operation) := by
rfl
theorem PostconditionT.operation_bind' {m : Type w → Type w'} [Monad m] {α : Type w} {β : Type w}
{x : PostconditionT m α} {f : α → PostconditionT m β} :
(x >>= f).operation = (do
let a ← x.operation
(fun fa => ⟨fa.1, by exact⟨a.1, a.2, fa.2⟩⟩) <$> (f a.1).operation) := by
rfl
theorem PostconditionT.operation_eq_map_mk_operation {m : Type w → Type w'}
[Monad m] [LawfulMonad m] {x : PostconditionT m α} :
x.operation = (fun a => ⟨a.val, a.property⟩) <$> x.operation := by
simp
theorem PostconditionT.operation_bind_eq_operation_bind_mk {m : Type w → Type w'}
[Monad m] {x : PostconditionT m α} {f : Subtype x.Property → m β} :
x.operation >>= f = x.operation >>= (fun a => f ⟨a.val, a.property⟩) := by
rfl
@[simp]
theorem PostconditionT.run_bind {m : Type w → Type w'} [Monad m] [LawfulMonad m]
{α : Type w} {β : Type w} {x : PostconditionT m α} {f : α → PostconditionT m β} :
(x.bind f).run = x.run >>= (f · |>.run) := by
simp [run_eq_map]
@[simp]
theorem PostconditionT.run_bind' {m : Type w → Type w'} [Monad m] [LawfulMonad m]
{α : Type w} {β : Type w} {x : PostconditionT m α} {f : α → PostconditionT m β} :
(x >>= f).run = x.run >>= (f · |>.run) :=
run_bind
@[simp]
theorem PostconditionT.property_lift {m : Type w → Type w'} [Functor m] {α : Type w}
{x : m α} : (lift x : PostconditionT m α).Property = (fun _ => True) := by
rfl
@[simp]
theorem PostconditionT.operation_lift {m : Type w → Type w'} [Functor m] {α : Type w}
{x : m α} : (lift x : PostconditionT m α).operation =
(⟨·, property_lift (m := m) ▸ True.intro⟩) <$> x := by
rfl
@[simp]
theorem PostconditionT.run_attachLift {m : Type w → Type w'} [Monad m] [MonadAttach m]
[WeaklyLawfulMonadAttach m] {α : Type w}
{x : m α} : (attachLift x).run = x := by
simp [attachLift, run_eq_map, WeaklyLawfulMonadAttach.map_attach]
@[simp]
theorem PostconditionT.operation_attachLift {m : Type w → Type w'} [Monad m] [MonadAttach m]
{α : Type w} {x : m α} : (attachLift x : PostconditionT m α).operation =
MonadAttach.attach x := by
rfl
instance {m : Type w → Type w'} {n : Type w → Type w''} [MonadLift m n] :
MonadLift (PostconditionT m) (PostconditionT n) where
monadLift x := ⟨_, monadLift x.operation⟩
instance PostconditionT.instLawfulMonadLift {m : Type w → Type w'} {n : Type w → Type w''}
[MonadLift m n] [Monad m] [Monad n] [LawfulMonad m] [LawfulMonad n] [LawfulMonadLift m n] :
LawfulMonadLift (PostconditionT m) (PostconditionT n) where
monadLift_pure a := by
simp [MonadLift.monadLift, monadLift, LawfulMonadLift.monadLift_pure, pure,
PostconditionT.pure]
monadLift_bind x f := by
simp only [MonadLift.monadLift, bind, monadLift, LawfulMonadLift.monadLift_bind,
PostconditionT.bind, mk.injEq, heq_eq_eq, true_and]
simp only [map_eq_pure_bind, LawfulMonadLift.monadLift_bind, LawfulMonadLift.monadLift_pure]
end Std.Iterators