File(s) not publicly available
See more through lenses than bananas
journal contributionposted on 2023-05-16, 10:22 authored by Yarroll, LH
Meijer, 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.
Publication titleTheoretical Computer Science
Department/SchoolSchool of Natural Sciences
PublisherElsevier Science Bv
Place of publicationPo Box 211, Amsterdam, Netherlands, 1000 Ae