Non Homomorphic Reductions of Data Structures.
Luis A. Galán, Manuel A. Nunez, Cristóbal Pareja-Flores, Ricardo Peña · 1994
In this paper we study different kinds of reductions of data types. By reduction we mean applying the higher order function fold to a data structure. An appropriate fold function can be defined for any recursive data type. These reductions have been presented as homomorphisms by several authors [2, 6]. Although many useful functions on data structures can be programmed as instances of fold, there are some that cannot. This is due to the fact that they are not mathematical homomorphisms. We show some examples of these functions. Then, we introduce two generalizations of fold (one for lists and the other for binary trees) in terms of which many non homomorphic mappings can be defined. Some examples are presented. A second problem addressed in the paper is the relationship between the definitions of some particular reductions in different data types. We show that the definition of a particular reduction, e.g. to insert an element in a data structure, in terms of fold (either the generaliz...