RFC: general sequences

[Josef Svenningsson]

On 5/23/05, Tomasz Zielonka <tomasz.zielonka at gmail.com> wrote:
> On Mon, May 23, 2005 at 12:13:48PM +0100, Ross Paterson wrote:
> > A general implementation of sequences (based on work with Ralf Hinze)
> > can be found at
> >
> >       http://www.soi.city.ac.uk/~ross/software/html/Data.Sequence.html
> >       http://www.soi.city.ac.uk/~ross/software/Data/Sequence.hs
> >
> > Our experiments indicate that its performance is comparable to (and
> > sometimes better than) the best known persistent implementations(*).
> > Non-persistent implementations are typically faster, but you need to be
> > more careful when using them.
> >
> > I'd like to propose this for base.
> >
> > Comments welcome.
> 
> Another thing: O(1) reverse would be very nice if it could be
> implemented with no overhead for other operations ;-)
> 
That should be trivial to implement. Just add a bit in the Seq data
type which indicates whether the sequence should be treated backwards
or forwards. The reverse operation then just toggles that bit. Or am I
missing something?

Also, I have some comments about the complexities in the
documentation. First of all I think it is useful to say what exactly
indices like n and i refer to even if it might not be that hard to
figure out. Secondly it seems that the complexity of the indexing
functions is wrong. Shouldn't they be O(log(min(i,n-i)))?

Otherwise I think it looks like a really useful library!

/Josef