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

Sebastian Sylvan sebastian.sylvan at gmail.com
Fri Jan 13 08:41:24 EST 2006

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?

Sebastian Sylvan
UIN: 44640862

More information about the Haskell mailing list