sequences

[Okasaki, C. DR EECS]

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