I wrote:

For what it's worth, neither real-time nor bootstrapped queues really make sense in Haskell. The advantage of real-time queues is that, in a (mostly) strict language, you get O(1) *worst-case* bounds instead of amortized bounds, but in Haskell, because everything's lazy, you're stuck with amortized bounds anyway.

George Russel wrote:

I don't really see the point here. If I am writing an application where things need to respond to external interactions in guaranteed O(1) time, then I am going to need real-time queues whether I am writing in Haskell or FORTRAN. The only difference laziness makes is that I may have to put in strictness annotations to avoid the queue elements containing unbounded amounts of computation.

If you want guaranteed O(1) response time, you're going to have to work really hard to get it. You can't just drop in real-time queues for some other kind of queue and expect them to take care of everything behind the scenes. Real-time queues can take care of what they need to do internally once they get control, but it would be up to the user to make sure (via strictness annotations or seq's or the like) that they get control. Here's the catch. Suppose you do something like f (enqueue x q) Once the enqueue operation gets control, it can do whatever it needs to do with x and q. But the enqueue operation does not get control right away. Instead a thunk gets built, and there's nothing enqueue can do to prevent it. You can easily write code that will generate a long chain of such thunks. Then when you get around to calling something like dequeue q it ends up taking O(N) time because it has to evaluate that chain of enqueues before it can finally start the dequeue. (And in fact you can make it take longer than O(N) time if the chain includes a mix of enqueues and dequeues.) -- Chris