Documentation

ToCslib.Data.PFunctor.Free.Basic

Algebraic operations on the free polynomial monad #

cslib's catamorphism FreeM.foldFreeM evaluates a tree in an arbitrary algebra of its signature, with its universal property foldFreeM_unique and substitution law foldFreeM_bind. This module adds the constructor-spelled node equations for the fold and for FreeM.map, which supplement cslib's (lift a).bind spellings and universe-polymorphic functor laws. Heterogeneous map composition and bind-after-map laws support changes of leaf universe. Monadic interpretation and handler fusion use cslib's FreeM.liftM and IsMonadHom API; the primed liftM_lift_bind' and liftM_lift' leave the call's value type unindexed, so that simp also fires on programs over concrete interfaces, and liftM_ite / liftM_dite interpret a conditional.

theorem PFunctor.FreeM.map_map {P : PFunctor.{uA, uB}} {α : Type u_1} {β : Type u_2} {γ : Type u_3} (f : β → γ) (g : α → β) (program : P.FreeM α) :
map f (map g program) = map (f ∘ g) program

Mapping twice composes the leaf functions, including across independent universes.

theorem PFunctor.FreeM.bind_map {P : PFunctor.{uA, uB}} {α : Type u_1} {β : Type u_2} {γ : Type u_3} (f : α → β) (program : P.FreeM α) (next : β → P.FreeM γ) :
(map f program).bind next = program.bind (next ∘ f)

A heterogeneous leaf map can be absorbed by the subsequent continuation.

Constructor-spelled node equations #

theorem PFunctor.FreeM.map_liftBind {P : PFunctor.{uA, uB}} {α : Type u_1} {β : Type u_2} (f : α → β) (a : P.A) (cont : P.B a → P.FreeM α) :
map f (liftBind a cont) = liftBind a fun (b : P.B a) => map f (cont b)

Mapping through a node maps every continuation, in constructor spelling.

theorem PFunctor.FreeM.foldFreeM_liftBind {P : PFunctor.{uA, uB}} {α : Type u_1} {β : Type u_2} (onValue : α → β) (onEffect : (a : P.A) → (P.B a → β) → β) (a : P.A) (cont : P.B a → P.FreeM α) :
foldFreeM onValue onEffect (liftBind a cont) = onEffect a fun (b : P.B a) => foldFreeM onValue onEffect (cont b)

Folding a node applies the node handler to the folded continuation, in constructor spelling.

@[simp]
theorem PFunctor.FreeM.liftM_lift_bind' {P : PFunctor.{uA, uB}} {m : Type uB → Type v} [Monad m] {γ : Type uB} (interp : (a : P.A) → m (P.B a)) (a : P.A) (cont : P.B a → P.FreeM γ) :
FreeM.liftM interp (lift a >>= cont) = do let u ← interp a FreeM.liftM interp (cont u)

FreeM.liftM_lift_bind with the bound value type left unindexed, so that simp fires on programs over concrete interfaces, whose direction types have been reduced.

@[simp]
theorem PFunctor.FreeM.liftM_lift' {P : PFunctor.{uA, uB}} {m : Type uB → Type v} [Monad m] [LawfulMonad m] (interp : (a : P.A) → m (P.B a)) (a : P.A) :
FreeM.liftM interp (lift a) = interp a

FreeM.liftM_lift with the value type left unindexed, for concrete interfaces.

theorem PFunctor.FreeM.liftM_ite {P : PFunctor.{uA, uB}} {m : Type uB → Type v} [Monad m] {γ : Type uB} (interp : (a : P.A) → m (P.B a)) (c : Prop) [Decidable c] (x y : P.FreeM γ) :
FreeM.liftM interp (if c then x else y) = if c then FreeM.liftM interp x else FreeM.liftM interp y

Interpreting a conditional program interprets the chosen branch.

theorem PFunctor.FreeM.liftM_dite {P : PFunctor.{uA, uB}} {m : Type uB → Type v} [Monad m] {γ : Type uB} (interp : (a : P.A) → m (P.B a)) (c : Prop) [Decidable c] (x : c → P.FreeM γ) (y : ¬c → P.FreeM γ) :
FreeM.liftM interp (if h : c then x h else y h) = if h : c then FreeM.liftM interp (x h) else FreeM.liftM interp (y h)

Interpreting a dependent conditional program interprets the chosen branch.