do-notation for IPFunctor.FreeM with deterministic transitions #
Importing PolyFun.IPFunctor.Notation transitively here registers the generic
single-index overrides before the deterministic ones. The keyed-attribute
lookup therefore tries the deterministic override first, independently of
downstream import order. PolyFunTest/IPFunctor/Notation/Mixed.lean pins this
priority contract.
The single-index do-notation in
PolyFun/IPFunctor/Notation.lean restricts the
remainder of a do-block after a let ← … to be polymorphic in the
fresh post-state s', because IPFunctor.FreeM.bind quantifies the
continuation universally. That kills most realistic chains.
This file lifts that restriction in the common case where every
P.src s a b is independent of the response b — i.e. P has deterministic
transitions. When that holds, an IPFunctor.FreeM.lift s a-style step
lands at a single concrete post-state next s a, and the continuation can
be specialized to that state instead of left polymorphic. Chains like
do
let _ ← IPFunctor.FreeM.lift false () -- post-state: next false () = true
let n ← IPFunctor.FreeM.lift true () -- post-state: next true () = true
pure n -- at state true
then elaborate via a specialized bind IPFunctor.FreeM.bindLiftA rather
than the generic state-polymorphic one.
Activation #
The extensible do elaborator is already the pinned toolchain's default. Users
must
- provide an
IPFunctor.DeterministicTransitions Pinstance, and - express each monadic step using
IPFunctor.FreeM.liftdirectly (or a@[reducible]alias). Steps that don't reduce toIPFunctor.FreeM.lift s afall through to the generic single-indexIPFunctor.FreeMelaborator, where they hit the usual polymorphic-continuation constraint.
Limitations #
We only specialize single-action steps (those reducing to
IPFunctor.FreeM.lift s a). A step that is itself a multi-step
do-block is not specialized — its internal leaves might genuinely
diverge, and detecting "all leaves land at one state" by structural
analysis would require an inductive proof we don't construct. Users who
hit this should nest a do-block of IPFunctor.FreeM₂ instead, via the
conversion IPFunctor.FreeM₂.toFreeM.
See Indexed.lean for IPFunctor.FreeM₂ do-notation,
which sidesteps the universal-quantification issue entirely by tracking
pre/post-state in the type.
Bind builder using IPFunctor.FreeM.bindLiftA #
The monad-info detector is shared with the generic single-index notation:
this file reuses IPFunctor.FreeMNotation.isFreeMMonad?,
brought into scope by the open above, so the @[doElem_elab] guard
matches exactly the same shapes the generic elaborator recognizes.
Build @IPFunctor.FreeM.bindLiftA for a step that reduced to
FreeM.lift s a, followed by the continuation in dec. The
continuation is elaborated at FreeM P (next s a) β, where next s a
comes from the DeterministicTransitions P instance — no universal
quantification, so subsequent steps can be state-specific.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Elaborator #
Only doExpr is overridden here. The doLetArrow form let x ← rhs is
delegated to the generic single-index elaborator in
../Notation.lean (elabFreeMLetArrow), which
recursively invokes doElem on rhs — and Lean's keyed-attribute
priority then picks this file's doExpr first for
IPFunctor.FreeM.lift-style steps. So a single doLetArrow override at
the bottom of the dispatch chain is enough; we just need a specialized
doExpr that catches the deterministic-step shape before the generic
one does.
doExpr override for FreeM P s blocks where a DeterministicTransitions P
instance is in scope and the step's RHS reduces to FreeM.lift s a.
Specializes the continuation's pre-state to det.next s a so that the
rest of the block can use state-specific operations.
Falls through to the generic single-index FreeM elaborator if any
condition fails (no instance, non-lift shape, etc.).
Equations
- One or more equations did not get rendered due to their size.