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.
Constructor-spelled node equations #
Folding a node applies the node handler to the folded continuation, in constructor spelling.
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.
FreeM.liftM_lift with the value type left unindexed, for concrete interfaces.
Interpreting a dependent conditional program interprets the chosen branch.