More haste, less speed: lazy versus eager evaluation
RICHARD BIRD a1, GERAINT JONES a1andOEGE DE MOOR a1 a1 Oxford University Computing Laboratory,
Wolfson Building, Parks Road, Oxford OX1 3QD, UK
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
Ω(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.
