A. Gill and S. Peyton Jones, “Cheap deforestation in practice: An optimizer for Haskell,” in IFIP Congress (1), pp. 581–586, 1994.



We present a simple, automatic transformation - the foldr/build transformation - which successfully removes many intermediate lists from programs written in non-strict functional programming languages. While the idea is simple and elegant, it turns out that some care is needed in the compiler to set up the right conditions for the foldr/build transformation to be applicable. We report on this practical experience, and present results which quantify the benefits that can in practice be achieved.


  author = {Andrew Gill and Simon {Peyton Jones}},
  title = {Cheap Deforestation in Practice: An Optimizer for {H}askell},
  booktitle = {IFIP Congress (1)},
  year = {1994},
  pages = {581--586},