[Haskell-cafe] Laziness leaks

[Don Stewart]

oddron:
> I was looking at the real time queues in [1] and I wanted to see what
> would happen if I tried to write one in Haskell.  The easy part was
> translating the real time queue from [1], p43 into Haskell.
> 
> The hard part is testing to see if the rotations really happen what
> they should.  Basically, I decided to use Debug.Trace.trace to see
> when rotations were actually occurring.
> 
> I pushed the numbers 1 to 10 into the queue, and then I popped the
> queue ten times.  What I found is that none of the rotations would
> actually take place until the first time I actually tried to /display
> the value/ of a popped element.  What I realized is that my test
> driver is lazy.  I figured out that I could put a bunch of 'seq'
> functions in the test driver to get the rotations to happen.
> 


Right, you have a requirement that things are evaluated earlier, but
you're representing this with a lazy list which will evaluate
them as late as possible.

Using something like weak strictness (seq) or deep strictness (rnf),
to enforce the requried level of evaluation prior to pushing things onto 
the queue is one way. Making the queue a stricter structure would also
work.

> My demonstration code is in:
> http://hpaste.org/8080
> 
> This leads to two questions:
> 
> 1. If I find a laziness leak, is 'seq' the appropriate way to plug it?

  * Strict data structures, for where you require stricness

    i.e. data Queue a = Nil | Node !a (Queue a)

  * Bang patterns on variables:

      foo !x = ... push x ....

  * Seq,

      foo x = x `seq` ... x ...

  * Deep seq:

      foo x = x `rnf` ... x ...

Are the main ways.
  
> 2. Is there any way to systematically search for or detect laziness
>    leaks?

Profiling, and looking at the Core. Being explicit about the evaluation
strategy you want is a fine idea though.

-- Don