[Haskell-cafe] Re: Laziness leaks

[Ryan Ingram]

On 6/4/08, apfelmus <apfelmus at quantentunnel.de> wrote:
> Note that lazy evaluation never wastes time; evaluating a term with lazy
> evaluation will always take less reduction steps than doing so eagerly or
> partly eagerly.

True, but you can still have a "time leak"; this is particularily
relevant in soft-real-time apps (like almost every app you use on a
regular basis, from your editor to games); a time leak is when a
computation that would take X time if evaluated every "time step" is
left for many timesteps without being evaluated, leading to a hitch in
responsiveness when it eventually is demanded N frames later taking
N*X time.

Eager applications almost never have this sort of "time leak", but
it's easy for it to happen with lazy evaluation.

A simple example: consider a variable that holds the number of
timesteps since the app launched, for example.  Every time step it
gets incremented by 1.  If the result is evaluated every time step, it
takes a constant amount of time per timestep.  But if you go a long
time without evaluating it, you end up with both a space leak (as the
+1 thunks build up) but a time leak as well--when you eventually
evaluate it, it takes O(n) time, where n is the number of frames since
the variable was last evaluated.

  -- ryan