Ronald Guida wrote:
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.
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?
2. Is there any way to systematically search for or detect laziness
leaks?
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
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
thunk:
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
cost.
A true cause of laziness is in accumulating a chain of tail's and snocs
without intermediate forcing, as observed.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
