Everything about Corecursion
Type of algorithm in computer science
In computer science, corecursion is a type of operation that is dual to (structural) recursion. Whereas recursion consumes a data structure by first handling the topmost layer before descending into its inner parts, corecursion produces a data structure by first defining the topmost layer before defining its inner parts. Corecursion is a particularly important in total languages, as it allows encoding potentially non-terminating computations in a context where every function must terminate. It is supported by theorem provers Agda and Rocq. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: CorecursionA 5-minute orientation
- Skim a recent paper: Coco: Corecursion with Compositional Heterogeneous ProductivityInfluential work since 2022
- Pick up a classic book: The Haskell Road To Logic, Maths And Programming (Texts in Computing S.)The most-reprinted book on the subject
- Read the landmark paper: Parametric corecursionCited 44 times
- Go sideways: Initial algebraA closely related topic
- Go sideways: CatamorphismA closely related topic
📖 Definitions
Noun The dual to recursion, that acts on the computed result, rather than the input.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
Parametric corecursion
Mechanizing coinduction and corecursion in higher-order logic
On the Foundations of Corecursion
Recursion and corecursion have the same equational logic
FUNCTIONAL PROGRAMMING WITH APOMORPHISMS (CORECURSION)
Foundational extensible corecursion: a proof assistant perspective
Productive corecursion in logic programming
Pure type systems with corecursion on streams
🆕 Influential since 2022
📚 Books worth reading
The Haskell Road To Logic, Maths And Programming (Texts in Computing S.)Jan van Eijck · 2004
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Initial algebra In mathematics, an initial algebra is an initial object in the category of F-algebras for a given endofunctor F. This initiality provides a general framework…
- Catamorphism In functional programming, the concept of catamorphism (from the Ancient Greek: κατά "downwards" and μορφή "form, shape") denotes the unique homomorphism…
- Coinduction In computer science, coinduction is a technique for defining and proving properties of systems of concurrent interacting objects. Coinduction is the mathematica…
- F-algebra In mathematics, specifically in category theory, F-algebras generalize the notion of algebraic structure. Rewriting the algebraic laws in terms of morphisms…
- Anamorphism In computer programming, an anamorphism is a function that generates a sequence by repeated application of the function to its previous result. You begin…
- Inductive type In type theory, a system has inductive types if it has facilities for creating a new type from constants and functions that create terms of that type.…
- F-coalgebra In mathematics, specifically in category theory, an F-coalgebra is a structure defined according to a functor F, with specific properties as defined below…
- Recursive data type In computer programming, a recursive data type is a data type whose definition contains values of the same type. It is also known as a recursively defined…