On Fri, 2006-01-13 at 14:41 +0100, Sebastian Sylvan wrote:
> On 1/13/06, Duncan Coutts <[EMAIL PROTECTED]> 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
_______________________________________________
Haskell mailing list
Haskell@haskell.org
http://www.haskell.org/mailman/listinfo/haskell
