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

[S.M.Kahrs]

> 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