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