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 _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
