More haste, less speed: lazy versus eager evaluation
Richard S. Bird, Geraint Jones, Oege de Moor · Journal of Functional Programming · 1997
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 Ω( 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.