eCite Digital Repository

See more through lenses than bananas


Yarroll, LH, See more through lenses than bananas, Theoretical Computer Science, 169, (1) pp. 113-121. ISSN 0304-3975 (1996) [Refereed Article]

DOI: doi:10.1016/S0304-3975(96)00116-8


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.

Item Details

Item Type:Refereed Article
Research Division:Information and Computing Sciences
Research Group:Theory of computation
Research Field:Theory of computation not elsewhere classified
Objective Division:Expanding Knowledge
Objective Group:Expanding knowledge
Objective Field:Expanding knowledge in the mathematical sciences
UTAS Author:Yarroll, LH (Mr Yarroll)
ID Code:8877
Year Published:1996
Deposited By:Mathematics
Deposited On:1996-08-01
Last Modified:2011-08-22

Repository Staff Only: item control page