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

Duncan Coutts duncan.coutts at worc.ox.ac.uk
Fri Jan 13 08:18:35 EST 2006

Hi all,

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

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

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.


More information about the Haskell mailing list