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.