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

[Duncan Coutts]

On Fri, 2006-01-13 at 14:41 +0100, Sebastian Sylvan wrote:
> 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

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

It shifts all the elements after it one step. So that's why all the
finite map types are no help.

Here's the semantics I want, in terms of an implementation using lists:

-- for simplicity lets ignore the case of indexing out of range
lookup :: Sequence a -> Int -> a
lookup = (!!)

insert :: Sequence a -> Int -> a -> Sequence a
insert seq i x =
  case splitAt i seq of
    (before, after) -> before ++ x : after

delete :: Sequence a -> Int -> Sequence a
delete seq i =
  case splitAt i seq of
    (before, x : after) -> before ++ after

Duncan