RFC: general sequences

Ross Paterson ross at soi.city.ac.uk
Mon May 23 20:02:03 EDT 2005


On Mon, May 23, 2005 at 01:09:11PM -0700, John Meacham wrote:
> And can you compare quickly it with Data.Queue? It also appears to be
> constant time, but has a lot less operations, does it win you anything
> over your sequences or is Data.Queue strictly inferior.

Thanks for reminding me -- I also think Data.Queue should be phased out
in favour of this module.

Data.Queue is implemented using Chris Okasaki's real-time queues.
These are unspeakably cute, but they're also much slower than say
Okasaki's bankers queues, and the real-time feature is pretty much
unavailable in a lazy language like Haskell.  As queues, finger trees
seem to be at least as fast as bankers queues, and sometimes faster,
so it seems they dominate bankers queues (and bankers deques) too.


More information about the Libraries mailing list