See more through lenses than bananas

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.