[Haskell] Looking for a random-access sequence data structure
Ross Paterson
ross at soi.city.ac.uk
Fri Jan 13 08:53:13 EST 2006
On Fri, Jan 13, 2006 at 01:18:35PM +0000, Duncan Coutts wrote:
> 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
Have a look at Data.Sequence (in CVS/darcs version), docs at
http://www.haskell.org/ghc/dist/current/docs/libraries/base/Data-Sequence.html
insert and delete aren't provided, but are easily derived:
insert :: Seq a -> Int -> a -> Seq a
insert xs i x = front >< x <| back
where (front, back) = splitAt i xs
delete :: Seq a -> Int -> Seq a
delete xs i = front >< drop 1 back
where (front, back) = splitAt i xs
(where splitAt and drop are the sequence versions).
Each of the three operations takes O(log(min(i,n-i))) time.
More information about the Haskell
mailing list