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

[Duncan Coutts]

On Fri, 2006-01-13 at 13:53 +0000, Ross Paterson wrote:
> 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

Ah, that's why I didn't find it! :-)

> 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.

Thanks very much, that's great.

Duncan