File(s) not publicly available
See more through lenses than bananas
journal contribution
posted on 2023-05-16, 10:22 authored by Yarroll, LHMeijer, Fokkinga, and Paterson introduced several recursion operators associated with data type definitions, including catamorphisms and anamorphisms. These operators capture familiar patterns of recursion over recursive data types. We show for recursive data structures that generating a structure from a seed value (anamorphism, lens) is more general than reducing a structure to a value (catamorphism, banana). More precisely, we show that any catamorphism may be written in terms of an anamorphism, and that it is not generally possible to do the converse. For the specific case of lists this means that unfold is more general than fold.
History
Publication title
Theoretical Computer ScienceVolume
169Pagination
113-121ISSN
0304-3975Department/School
School of Natural SciencesPublisher
Elsevier Science BvPlace of publication
Po Box 211, Amsterdam, Netherlands, 1000 AeRepository Status
- Restricted