[Haskell] Looking for a random-access sequence data structure
Duncan Coutts
duncan.coutts at worc.ox.ac.uk
Fri Jan 13 09:09:29 EST 2006
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
More information about the Haskell
mailing list