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