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

[Sebastian Sylvan]

On 1/13/06, Duncan Coutts <duncan.coutts at worc.ox.ac.uk> wrote:
> 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.

What's the semantics of insert? Does it replace an element, or does it
shirt all the elements after it one step?

/S
--
Sebastian Sylvan
+46(0)736-818655
UIN: 44640862