Shortcut Deforestation in Calculational Form(Theory of Rewriting Systems and Its Applications)
Akihiko Takano, Erik Meijer · Institutional Repositories DataBase (IRDB) · 1995
In functional programming, intermediate data structures are often used to "glue') together small programs.Deforestation is a program transformation to remove these intermediate data structures automatically.We present a simple algorithm for deforestation based on two fusion rules for hylomorphism, an expressive recursion pattern.A generic notation for hylo- morphisms is introduced, where natural transformations are explicitly factored out, and it is used to represent programs.Our method successfully eliminates intermediate data struc- tures of any algebraic type from a much larger class of compositional functional programs than previous techniques.Recently two new approaches to deforestation have been proposed [GLPJ93,SF93].Both of them pick up the function fold as a useful template to capture the structure of programs, and apply transformations only to programs written in terms of the fold function.Both techniques do not require any global analysis to guarantee termination and the applicability of their rules of transformation can be checked locally.Because their theoretical basis can be found in the study *Earlier version of this paper was presented at $\mathrm{F}\mathrm{P}\mathrm{C}\mathrm{A}' 95$ .