[Haskell] Looking for a random-access sequence data structure
S.M.Kahrs at kent.ac.uk
Fri Jan 13 08:41:05 EST 2006
> I've been looking around (unsuccessfully) for an efficient data
> structure to implement a sequence data type with indexed
[snip] For example the Data.Map supports all of these except
> insert. Okasaki's random access lists only support inserting elements at
> the head of the list.
I think it's possible to give an O(log n) insert-operation
of Okasaki's random access list, but I would expect it to be rather messy.
> I'd guess that some kind of (balanced) binary search tree where each
> node is annotated with the number of nodes below it could support all
> these operations.
Yes, but you don't need to go that far.
Braun trees should do fine.
More information about the Haskell