Intrinsically correct & total functional programming with enrichment, contractive functors, recursive coalgebras and cofree presheaves
Cass Alexandru
RPTU Kaiserslautern-Landau
Abstract:
Recent progress has been made (Alexandru et al. PLDI 2026) in formalising synergies between proofs of partial and total correctness of algorithms defined using structured recursion (Hinze et al. POPL 2015)
This was achieved with the introduction of the novel notion of a well founded functor.
We achieve the same result, i.e. a criterion for all coalgebras for an endofunctor on the power category 𝒞^A, for A the carrier of a well founded ordering <, to be recursive.
Our criterion is a novel instantiation of the preexisting notion of a locally contractive functor (Birkedal et al. LMCS 2012).
This instantiation is achieved by enriching 𝒞^A in presheaves over (A,<) using change of base of enrichment along the cofree presheaf functor.
Our hope is that demonstrating how this preexisting notion can be instantiated for this novel application may lead to a broader adoption of the technique, as well as enabling reuse of all existing known results about locally contractive functors in this setting.
This is joint work with Steven Schaefer and Max S. New.