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 > > http://www.haskell.org/ghc/dist/current/docs/libraries/base/Data-Sequence.html
And as a bonus the append and prepend operations are O(1), which is nice since for my application these are probably more likely than inserting at arbitrary indexes. It's probably too much to ask, but here's a question: would it be possible to provide an operation that gives a left or right view from looking up an index. Say: viewrFromIndex :: Seq a -> Int -> ViewL a viewlFromIndex :: Seq a -> Int -> ViewR a The library currently provides views for the each end of the sequence. viewl :: Seq a -> ViewL a viewr :: Seq a -> ViewR a I suppose this would be a zipper-like iterator for the sequence? I ask since a common use in my application will involve sequential access (though random access is still required). So if I cached an iterator/zipper/view thing to use in case the next lookup happens to be the next in the sequence then I could do that in O(1) time rather than doing an ordinary O(log n) lookup. Just wondering. :-) Duncan _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
