|
Abstract : |
A catamorphism, generic version of our familiar foldr on lists, is quite a simple recursive scheme associated with data type definitions. It plays a very important role in program calculation, since for it there exists a general transformation rule known as Promotion Theorem. However, its structure is so tight that many recursions cannot be specified by catamorphisms because of their irregular reference to compound data structures. In this paper, aiming at manipulating functions defined by more general recursive schemes, we propose a method to factorize these functions into a composition of a catamorphism and a type reformer based on the construction of a medio-type-- suitable intermediate data type extracted from recursion. Consequently, our method extends the applicability of transformational techniques specially geared to catamorphisms. Some examples are also given to illustrate our idea., |
