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

[Duncan Coutts]

Hi all,

I've been looking around (unsuccessfully) for an efficient data
structure to implement a sequence data type with indexed
insert/delete/lookup.

lookup :: Sequence a -> Int -> Maybe a
insert :: Sequence a -> Int -> a -> Sequence a
delete :: Sequence a -> Int -> Sequence a

Obviously I can implement this with ordinary lists in O(n) time for each
operation. It seems that this could be done in O(log n) time for each
operation.

This seems like a fairly common collection signature to want but to my
surprise I've not been able to find any existing implementations that
support it. There are several that have almost all the necessary
operations. 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'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.

Duncan