Writer monad cost lemmas
DefinitionYukon_4231d0ef2a5eb8af03e94595better-codes
WriterT and additive-cost definitions and lemmas from the pinned VCVio dependency. Equivalent declarative notation replaces three custom parser rules; mathematical definitions and proofs are unchanged.
Definition code
/-
Copyright (c) 2024 Devon Tuma. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Devon Tuma
-/
module
public import Mathlib.Algebra.Group.TypeTags.Basic
public import Mathlib.Control.Monad.Writer
public import Mathlib.Order.Basic
public import Batteries.Control.AlternativeMonad
public import Init
set_option backward.isDefEq.respectTransparency.types false
/-!
# Writer Monad Transformer Utilities
This file extends `WriterT` with helper lemmas and the additive wrapper `AddWriterT`.
The first half of the file collects basic `WriterT` run, bind, and lifting lemmas, together with
the `LawfulAppend` class used to build lawful `WriterT` instances over append-like logs.
The second half specializes `WriterT` to additive cost accumulation via `Multiplicative`, and
introduces predicates and notation for reasoning about outputs and accumulated costs.
-/
@[expose] public section
universe u v w
/-- Typeclass for instances where `∅` is an identity for `++`. -/
class LawfulAppend (α : Type u)
[EmptyCollection α] [Append α] where
empty_append (x : α) : ∅ ++ x = x
append_empty (x : α) : x ++ ∅ = x
append_assoc (x y z : α) : x ++ (y ++ z) = x ++ y ++ z
namespace LawfulAppend
attribute [simp] LawfulAppend.empty_append LawfulAppend.append_empty
attribute [grind =] LawfulAppend.empty_append
LawfulAppend.append_empty LawfulAppend.append_assoc
instance _root_.LawfulAppend.instLawfulMonadWriterT {M : Type u → Type v} {ω : Type u} [Monad M]
[EmptyCollection ω] [Append ω] [LawfulAppend ω] [LawfulMonad M] :
LawfulMonad (WriterT ω M) := LawfulMonad.mk'
(bind_pure_comp := by simp [bind, WriterT.mk, WriterT.run, pure,
map_pure, LawfulAppend.append_empty, bind_pure_comp, Functor.map])
(id_map := by simp [Functor.map, WriterT.mk, WriterT.run])
(pure_bind := by simp [Bind.bind, Pure.pure, WriterT.mk, WriterT.run])
(bind_assoc := by simp [Bind.bind, WriterT.mk, WriterT.run, LawfulAppend.append_assoc])
instance _root_.LawfulAppend.instList (α : Type u) : LawfulAppend (List α) where
empty_append := by simp
append_empty := by simp
append_assoc := by grind
end LawfulAppend
namespace WriterT
section basic
variable {m : Type u → Type v} [Monad m] {ω : Type u} {α β γ : Type u}
section monoid
variable [Monoid ω]
@[simp]
lemma run_monadLift (x : m α) : (monadLift x : WriterT ω m α).run = (·, 1) <$> x := rfl
lemma liftM_def (x : m α) :
(liftM x : WriterT ω m α) = WriterT.mk ((·, 1) <$> x) := rfl
lemma monadLift_def (x : m α) :
(MonadLift.monadLift x : WriterT ω m α) = WriterT.mk ((·, 1) <$> x) := rfl
lemma bind_def (x : WriterT ω m α) (f : α → WriterT ω m β) :
x >>= f = WriterT.mk (x.run >>= fun (a, w₁) ↦
(Prod.map id (w₁ * ·)) <$> (f a)) := rfl
@[simp]
lemma run_seqLeft {m : Type u → Type v} [Monad m] {ω : Type u} [Monoid ω] {α β : Type u}
(x : WriterT ω m α) (y : WriterT ω m β) :
(x *> y).run = x.run >>= fun z => Prod.map id (z.2 * ·) <$> y.run := rfl
/-- `Prod.fst <$> WriterT.run` preserves `pure` (Monoid flavour). -/
lemma fst_map_run_pure [LawfulMonad m] (x : α) :
Prod.fst <$> ((pure x : WriterT ω m α).run) = pure x := by
simp [WriterT.run_pure]
/-- `Prod.fst <$> WriterT.run` preserves `bind` (Monoid flavour) — i.e. it is a
monad morphism `WriterT ω m → m`. -/
lemma fst_map_run_bind [LawfulMonad m] (b : WriterT ω m α) (f : α → WriterT ω m β) :
Prod.fst <$> (b >>= f).run =
(Prod.fst <$> b.run) >>= fun x => Prod.fst <$> (f x).run := by
simp only [WriterT.run_bind, map_bind, Functor.map_map]
exact (bind_map_left (m := m) Prod.fst b.run (fun x => Prod.fst <$> (f x).run)).symm
end monoid
section append
variable [EmptyCollection ω]
@[simp]
lemma run_monadLift' (x : m α) : (monadLift x : WriterT ω m α).run = (·, ∅) <$> x := rfl
lemma liftM_def' (x : m α) :
(liftM x : WriterT ω m α) = WriterT.mk ((·, ∅) <$> x) := rfl
lemma monadLift_def' (x : m α) :
(MonadLift.monadLift x : WriterT ω m α) = WriterT.mk ((·, ∅) <$> x) := rfl
variable [Append ω]
lemma bind_def' (x : WriterT ω m α) (f : α → WriterT ω m β) :
x >>= f = WriterT.mk (x.run >>= fun (a, w₁) ↦
(Prod.map id (w₁ ++ ·)) <$> (f a)) := rfl
@[simp]
lemma run_pure' [LawfulMonad m] (x : α) :
(pure x : WriterT ω m α).run = pure (x, ∅) := rfl
@[simp]
lemma run_bind' [LawfulMonad m] (x : WriterT ω m α) (f : α → WriterT ω m β) :
(x >>= f).run = x.run >>= fun (a, w₁) => Prod.map id (w₁ ++ ·) <$> (f a).run := rfl
@[simp]
lemma run_seqLeft' {m : Type u → Type v} [Monad m] {ω : Type u} [Monoid ω] {α β : Type u}
(x : WriterT ω m α) (y : WriterT ω m β) :
(x *> y).run = x.run >>= fun z => Prod.map id (z.2 * ·) <$> y.run := rfl
@[simp]
lemma run_map' (x : WriterT ω m α) (f : α → β) : (f <$> x).run = Prod.map f id <$> x.run := rfl
/-- `Prod.fst <$> WriterT.run` preserves `pure` (Append flavour). -/
lemma fst_map_run_pure' [LawfulMonad m] (x : α) :
Prod.fst <$> ((pure x : WriterT ω m α).run) = pure x := by
simp
/-- `Prod.fst <$> WriterT.run` preserves `bind` (Append flavour) — i.e. it is a
monad morphism `WriterT ω m → m`. -/
lemma fst_map_run_bind' [LawfulMonad m] (b : WriterT ω m α) (f : α → WriterT ω m β) :
Prod.fst <$> (b >>= f).run =
(Prod.fst <$> b.run) >>= fun x => Prod.fst <$> (f x).run := by
simp only [WriterT.run_bind', map_bind, Functor.map_map]
exact (bind_map_left (m := m) Prod.fst b.run (fun x => Prod.fst <$> (f x).run)).symm
end append
end basic
-- @[simp]
-- lemma run_fail [AlternativeMonad m] [LawfulAlternative m] :
-- (failure : WriterT ω m α).run = Failure.fail := by
-- simp [failureOfLift_eq_lift_fail, WriterT.liftM_def]
-- /-- The naturally induced `Failure` on `WriterT` is lawful. -/
-- instance [Monad m] [LawfulMonad m] [Failure m] [LawfulFailure m] :
-- LawfulFailure (WriterT ω m) where
-- fail_bind' {α β} f := by
-- show WriterT.mk _ = WriterT.mk _
-- simp [monadLift_def, map_eq_bind_pure_comp, WriterT.mk, bind_assoc,
-- failureOfLift_eq_lift_fail, liftM_def]
section fail
variable {m : Type u → Type v} [AlternativeMonad m] {ω : Type u} {α β γ : Type u}
@[always_inline, inline]
protected def orElse {α : Type u} (x₁ : WriterT ω m α)
(x₂ : Unit → WriterT ω m α) : WriterT ω m α :=
WriterT.mk (x₁.run <|> (x₂ ()).run)
@[always_inline, inline]
protected def failure {α : Type u} : WriterT ω m α := WriterT.mk failure
instance _root_.WriterT.instAlternativeMonadOfMonoid_toMathlib [Monoid ω] : AlternativeMonad (WriterT ω m) where
failure := WriterT.failure
orElse := WriterT.orElse
@[simp]
lemma run_failure [Monoid ω] {α : Type u} : (failure : WriterT ω m α).run = failure := rfl
-- instance [Monoid ω] [LawfulMonad m] [LawfulAlternative m] :
-- LawfulAlternative (WriterT ω m) := sorry
-- map_failure f := sorry
-- failure_seq f := sorry
-- orElse_failure f := sorry
-- failure_orElse f := sorry
-- orElse_assoc x y z := sorry
-- map_orElse f := sorry
instance _root_.WriterT.instLawfulMonadLiftOfLawfulMonad_toMathlib [Monoid ω] [LawfulMonad m] : LawfulMonadLift m (WriterT ω m) where
monadLift_pure x := map_pure (·, 1) x
monadLift_bind {α β} x y := by
change WriterT.mk _ = WriterT.mk _
simp [monadLift_def, WriterT.mk, WriterT.run]
end fail
end WriterT
/-! ## AddWriterT: Additive Writer Monad Transformer -/
/-- Writer monad transformer with additive cost accumulation.
Defined as `WriterT (Multiplicative ω) M`, which uses `Monoid (Multiplicative ω)`
(derived from `AddMonoid ω`) so that `tell` accumulates via `+` with identity `0`.
The types `Multiplicative ω` and `ω` are definitionally equal (`Multiplicative` is a plain
`def`, not a `structure`), so no runtime wrapping occurs. -/
abbrev AddWriterT (ω : Type u) (M : Type u → Type v) := WriterT (Multiplicative ω) M
namespace AddWriterT
variable {ω : Type u} {M : Type u → Type v} [Monad M] {α : Type u}
/-- Forget the additive cost log and keep only the outputs of an `AddWriterT` computation. -/
def outputs (oa : AddWriterT ω M α) : M α :=
Prod.fst <$> oa.run
/-- Observe only the accumulated additive cost of an `AddWriterT` computation. -/
def costs (oa : AddWriterT ω M α) : M ω :=
(fun z => Multiplicative.toAdd z.2) <$> oa.run
/-- Record an additive cost `w` in the writer log. -/
def addTell [AddMonoid ω] (w : ω) : AddWriterT ω M PUnit :=
tell (Multiplicative.ofAdd w)
@[simp]
lemma outputs_def (oa : AddWriterT ω M α) :
oa.outputs = Prod.fst <$> oa.run := rfl
@[simp]
lemma costs_def (oa : AddWriterT ω M α) :
oa.costs = (fun z => Multiplicative.toAdd z.2) <$> oa.run := rfl
@[simp]
lemma run_addTell [AddMonoid ω] (w : ω) :
(addTell (M := M) w).run = pure (⟨⟩, Multiplicative.ofAdd w) := rfl
@[simp]
lemma outputs_addTell [AddMonoid ω] [LawfulMonad M] (w : ω) :
(addTell (M := M) w).outputs = pure ⟨⟩ := by
simp [outputs, addTell]
@[simp]
lemma costs_addTell [AddMonoid ω] [LawfulMonad M] (w : ω) :
(addTell (M := M) w).costs = pure w := by
simp [costs, addTell]
section costPredicates
/-- `CostsAs oa f` means that the accumulated cost of `oa` is determined by its output via the
function `f`.
Concretely, whenever `oa` produces output `a`, the recorded cost is exactly `f a`. This is a
strong structural property: it can fail when the same output can be reached by different execution
paths carrying different costs. -/
def CostsAs (oa : AddWriterT ω M α) (f : α → ω) : Prop :=
oa.costs = f <$> oa.outputs
/-- `HasCost oa w` means that every execution path of `oa` incurs the constant cost `w`. -/
def HasCost (oa : AddWriterT ω M α) (w : ω) : Prop :=
oa.CostsAs (fun _ ↦ w)
/-- `OutputCostAtMost oa w` means that `oa` admits an output-indexed cost description bounded above
by the constant `w`.
Concretely, there is some function `f : α → ω` such that every execution producing output `a`
accumulates cost `f a`, and each such `f a` is at most `w`. This is stronger than a merely
pathwise upper bound when the same output can be reached with different costs. -/
def OutputCostAtMost [Preorder ω] (oa : AddWriterT ω M α) (w : ω) : Prop :=
∃ f : α → ω, oa.CostsAs f ∧ ∀ a, f a ≤ w
/-- `OutputCostAtLeast oa w` means that `oa` admits an output-indexed cost description bounded
below by the constant `w`.
As with [`AddWriterT.OutputCostAtMost`], this packages a cost function determined by the final
output, not just an arbitrary pathwise lower bound. -/
def OutputCostAtLeast [Preorder ω] (oa : AddWriterT ω M α) (w : ω) : Prop :=
∃ f : α → ω, oa.CostsAs f ∧ ∀ a, w ≤ f a
/-- `Cost[ oa ] = w` means that the `AddWriterT` computation `oa` incurs the same additive cost
`w` on every execution path.
This is notation for [`AddWriterT.HasCost`]. It is intended for theorem statements where the
constant-cost reading is more natural than the underlying output-indexed formulation
[`AddWriterT.CostsAs`]. -/
notation:max "Cost[ " oa " ]" " = " w:50 => AddWriterT.HasCost oa w
/-- `OutputCost[ oa ] ≤ w` means that `oa` admits an output-indexed additive-cost bound by `w`.
This is notation for [`AddWriterT.OutputCostAtMost`]. It is best used when cost is already known
to be determined by the final output, or when that stronger formulation is useful in a proof. -/
notation:max "OutputCost[ " oa " ]" " ≤ " w:50 => AddWriterT.OutputCostAtMost oa w
/-- `OutputCost[ oa ] ≥ w` means that `oa` admits an output-indexed additive-cost lower bound by
`w`.
This is notation for [`AddWriterT.OutputCostAtLeast`]. As with [`OutputCost[ oa ] ≤ w`], it is
formulated in terms of an output-indexed cost witness rather than arbitrary execution paths. -/
notation:max "OutputCost[ " oa " ]" " ≥ " w:50 => AddWriterT.OutputCostAtLeast oa w
@[simp]
lemma costsAs_iff (oa : AddWriterT ω M α) (f : α → ω) :
oa.CostsAs f ↔ oa.costs = f <$> oa.outputs :=
Iff.rfl
@[simp]
lemma hasCost_iff (oa : AddWriterT ω M α) (w : ω) :
(Cost[ oa ] = w) ↔ oa.costs = (fun _ ↦ w) <$> oa.outputs :=
Iff.rfl
@[simp]
lemma outputCostAtMost_iff [Preorder ω] (oa : AddWriterT ω M α) (w : ω) :
(OutputCost[ oa ] ≤ w) ↔ ∃ f : α → ω, oa.CostsAs f ∧ ∀ a, f a ≤ w :=
Iff.rfl
@[simp]
lemma outputCostAtLeast_iff [Preorder ω] (oa : AddWriterT ω M α) (w : ω) :
(OutputCost[ oa ] ≥ w) ↔ ∃ f : α → ω, oa.CostsAs f ∧ ∀ a, w ≤ f a :=
Iff.rfl
lemma outputCostAtMost_of_hasCost [Preorder ω] {oa : AddWriterT ω M α} {w b : ω}
(h : Cost[ oa ] = w) (hwb : w ≤ b) : OutputCost[ oa ] ≤ b := by
refine ⟨fun _ ↦ w, ?_, fun _ ↦ hwb⟩
exact h
lemma outputCostAtLeast_of_hasCost [Preorder ω] {oa : AddWriterT ω M α} {w b : ω}
(h : Cost[ oa ] = w) (hbw : b ≤ w) : OutputCost[ oa ] ≥ b := by
refine ⟨fun _ ↦ w, ?_, fun _ ↦ hbw⟩
exact h
end costPredicates
end AddWriterT
Source