sequences

[Okasaki, C. DR EECS]

Ross Patterson wrote:
>[Simon Marlow wrote:]
>> Why would anyone prefer Catenable over JoinList?
>
>Catenable has guaranteed bounds for head, even in a persistent setting,
>and JoinList doesn't.  But Catenable and CatDeque seem to be uniformly
>inferior to FingerTree.  Similarly real-time and bootstrapped queues
>are dominated by Banker's queues.

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.  The advantage of bootstrapped queues is
that, in a (mostly) strict language, it only needs a tiny bit of
laziness
(O(log n) thunks compared to O(n) thunks for banker's queues).  But
again,
this advantage goes away in Haskell because everything's lazy.

For FingerTrees, I agree that it would probably make a better
general-purpose
implementation than Catenable or CatDequeue.  As you noted, it's easy
enough
to create microbenchmarks to make the O(1) append of Catenable or
CatDequeue
win out, but in practice, FingerTrees would probably be better.  I would
guess
you could probably tweak maybe a few percent improvement out of
FingerTrees by
using a different balancing scheme than 2-3 (maybe red-black or even one
of the
AVL variants), but the small gain may not be worth the effort.

-- Chris