Comparison of Deforestation Techniques for Functional Programs And and for Tree Transducers

We compare transformations for the elimination of intermediate results in rst-order functional programs. We choose the well known deforestation technique of Wadler and composition techniques from the theory of tree transducers, of which the implementation of functional programs yet does not take advantage. We identify syntactic classes of function de nitions for which both techniques deliver equally ecient results and for which one technique is more powerful than the other