Helmut Seidl and Morten Heine Sørensen. Constraints to Stop Higher-Order Deforestation. Principles of programming languages, pages 400-413, 1997.
Wadler's deforestation algorithm eliminates intermediate data structures from functional programs. To be suitable for inclusion in a compiler, it must terminate on all programs. Several techniques to ensure termination of deforestation on all rst-order programs are known, but a technique for higher-order programs was only recently introduced by Hamilton, and elaborated and implemented in the Glasgow Haskell compiler by Marlow. We introduce a new technique for ensuring termination of deforestation on all higher-order programs that allows useful transformation steps prohibited in Hamilton's and Marlowe's techniques.