Unifying Structured Recursion Schemes

Ralf Hinze, Nicolas Wu

Research output: Contribution to journalArticle (Academic Journal)peer-review

2 Citations (Scopus)
872 Downloads (Pure)

Abstract

Folds and unfolds have been understood as fundamental building blocks for total programming, and have been extended to form an entire zoo of specialised structured recursion schemes. A great number of these schemes were unified by the introduction of adjoint folds, but more exotic beasts such as recursion schemes from comonads proved to be elusive. In this paper, we show how the two canonical derivations of adjunctions from (co)monads yield recursion schemes of significant computational importance: monadic catamorphisms come from the Kleisli construction, and more astonishingly, the elusive recursion schemes from comonads come from the Eilenberg-Moore construction. Thus we demonstrate that adjoint folds are more unifying than previously believed.
Original languageEnglish
Article numbere1
Number of pages49
JournalJournal of Functional Programming
Volume26
DOIs
Publication statusPublished - 3 Feb 2016

Cite this