Bananas in space: extending fold and unfold to exponential types

Fold and unfold are general purpose functional for processing and constructing lists. By using the categorical approach of modelling recursive dat at ypes as fixed points of funct ors, these functional and their algebraic properties were generalised from lists to polynomial (sum-of-product) datatypes. However, the restriction to polynomial datatypes is a serious limitation: it precludes the use of exponential (functionspaces ), whereas it is central to functional programming that functions are first-class values, and so exponential should be able to be used freely in datatype definitions. In this paper we explain how Freyd's work on modelling recursive datatypes as fixed points of difunctors shows how to generalise fold and unfold from polynomial datatypes to those involving exponentials. Knowledge of category theory is not required; we use Gofer throughout as our meta-language, making extensive use of constructor classes. 1