The Recursion Scheme from the Cofree Recursive Comonad
Author(s) -
Tarmo Uustalu,
Varmo Vene
Publication year - 2011
Publication title -
electronic notes in theoretical computer science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.242
H-Index - 60
ISSN - 1571-0661
DOI - 10.1016/j.entcs.2011.02.020
Subject(s) - recursion (computer science) , mathematics , scheme (mathematics) , lemma (botany) , argument (complex analysis) , mathematical proof , extension (predicate logic) , algebra over a field , pure mathematics , computer science , algorithm , programming language , medicine , mathematical analysis , ecology , geometry , poaceae , biology
We instantiate the general comonad-based construction of recursion schemes for the initial algebra of a functor F to the cofree recursive comonad on F. Differently from the scheme based on the cofree comonad on F in a similar fashion, this scheme allows not only recursive calls on elements structurally smaller than the given argument, but also subsidiary recursions. We develop a Mendler formulation of the scheme via a generalized Yoneda lemma for initial algebras involving strong dinaturality and hint a relation to circular proofs à la Cockett, Santocanale
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom