[Haskell-cafe] Laziness leaks
Albert Y. C. Lai
trebla at vex.net
Tue Jun 3 19:16:08 EDT 2008
Ronald Guida wrote:
> I was looking at the real time queues in  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 , 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.
> My demonstration code is in:
> This leads to two questions:
> 1. If I find a laziness leak, is 'seq' the appropriate way to plug it?
> 2. Is there any way to systematically search for or detect laziness
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
I want to point out several non-causes of laziness. For a no-magic,
no-surprise understanding, it is important to know both what causes
laziness and what does not.
A. The lazy list at rtqRear, which is originally a strict list. It is an
invariant that every thunk you put there is  or x:y. (As a result, it
is unnecessary to make RTQueue a strict record, since you want two of
the fields to be lazy, and the remaining field rtqRear is de facto strict.)
B. rtqueue's thunked call to rotate, i.e.,
rtqueue f r  = let f' = rotate f r  in RTQueue f'  f'
Originally f' is forced before the record is returned (SML convention).
In Haskell the rotate call is thunked as f' and the record is returned.
But there will not be an accumulation of such rotate thunks. For example
if you snoc twice in succession and the first instance builds a rotate
snoc p (snoc q (RTQueue f r ))
-> snoc p (rtqueue f (q:r) )
-> snoc p (RTQueue f'  f') where f' = thunk
-> rtqueue f' p: f' where f' = thunk
-> f' is now forced by rtqueue's pattern matching on the 3rd param
So if one snoc builds a rotate thunk, the next snoc kills it. And
similarly any interleaving of queue operations. (head and tail add their
extra pattern matching.) Thus it can be proved that Haskell lags behind
the original by just one step in this regard. This is ok unless you're
done with reducing asymptotic cost and start looking at constant factor
A true cause of laziness is in accumulating a chain of tail's and snocs
without intermediate forcing, as observed.
More information about the Haskell-Cafe