Intrinsically Correct Algorithms and Recursive Coalgebras
Cass Alexandru, Henning Urbat, Thorsten Wißmann
Abstract
Recursive coalgebras provide an elegant categorical tool for modelling recursive algorithms and analysing their termination and correctness. By considering coalgebras over categories of suitably indexed families, the correctness of the corresponding algorithms follows intrinsically just from the type of the computed maps. However, proving recursivity of the underlying coalgebras is non-trivial, and proofs are typically ad hoc. This layer of complexity impedes the formalization of coalgebraically defined recursive algorithms in proof assistants. We introduce a framework for constructing coalgebras which are intrinsically recursive in the sense that the type of the coalgebra guarantees recursivity from the outset. Our approach is based on the novel concept of a well-founded functor on a category of families indexed by a well-founded relation. We show as our main result that every coalgebra for a well-founded functor is recursive, and demonstrate that well-known techniques for proving recursivity and termination such as ranking functions are subsumed by this abstract setup. We present a number of case studies, including Quicksort, the Euclidian algorithm, and CYK parsing. Both the main theoretical result and selected case studies have been formalized in Cubical Agda.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
Builds on1
Related papers
- Initial Algebras Unchained - A Novel Initial Algebra Construction Formalized in AgdaThorsten Wißmann, Stefan MiliusLICS 2024
- A Type-Based Approach to Divide-and-Conquer Recursion in CoqPedro Abreu, Benjamin Delaware, Alex Hubers, Christa Jenkins et al.POPL 2023
- Zigzag normalisation for associative n-categoriesLukas Heidemann, David Reutter, Jamie VicaryLICS 2022 · 1 citation
- Formalising Graph Algorithms with CoinductionDonnacha Oisín Kidney, Nicolas WuPOPL 2025 · 2 citations
- Coherence via Well-Foundedness: Taming Set-Quotients in Homotopy Type TheoryNicolai Kraus, Jakob von RaumerLICS 2020 · 8 citations
