Re: [Haskell] Looking for a random-access sequence data structure

I've been looking around (unsuccessfully) for an efficient data structure to implement a sequence data type with indexed insert/delete/lookup. [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. Stefan