Okasaki, C. DR EECS
Christopher.Okasaki at usma.edu
Tue Jun 15 10:57:31 EDT 2004
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
amortized bounds, but in Haskell, because everything's lazy, you're
with amortized bounds anyway. The advantage of bootstrapped queues is
that, in a (mostly) strict language, it only needs a tiny bit of
(O(log n) thunks compared to O(n) thunks for banker's queues). But
this advantage goes away in Haskell because everything's lazy.
For FingerTrees, I agree that it would probably make a better
implementation than Catenable or CatDequeue. As you noted, it's easy
to create microbenchmarks to make the O(1) append of Catenable or
win out, but in practice, FingerTrees would probably be better. I would
you could probably tweak maybe a few percent improvement out of
using a different balancing scheme than 2-3 (maybe red-black or even one
AVL variants), but the small gain may not be worth the effort.
More information about the Libraries