Journal of functional programming, volume 7, number 5, pp. 541-547, 1997.

Authors: Richard S. Bird, Geraint Jones and Oege de Moor
>

Abstract

Nicholas Pippenger has recently given a problem that, under two simple restrictions, can be solved in linear time by an impure Lisp program, but requires Omega(n log n) steps to be solved by any eager pure Lisp program. By showing how to solve the problem in linear time with a lazy functional program, we demonstrate that - for some problems at least - lazy evaluators are strictly more powerful than eager ones.

(PS)

BIBTEX:

           @article{jfp97bird, 
           author = "Richard S. Bird and Geraint Jones and De Moor, Oege",
           title = "More haste, less speed: lazy versus eager evaluation", 
           journal = "Journal of Functional Programming", 
           volume = "7",
           number = "5",
           pages = "541--547", 
           year = "1997"}