Unifying structured recursion schemes: An Extended Study. (3rd February 2016)

• Record Type: Journal Article
• Authors: HINZE, RALF; WU, NICOLAS
• Is Part Of: Journal of functional programming. Volume 26(2016)
• Publication Date: 2016-02-03
• Subjects: Functional programming (Computer science) -- Periodicals
• DOI: 10.1017/S0956796815000258
• Languages: English
• ISSNs: 0956-7968

Abstract

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.