RFC: general sequences

[Ross Paterson]

On Mon, May 23, 2005 at 04:52:04PM +0200, Josef Svenningsson wrote:
> On 5/23/05, Tomasz Zielonka <tomasz.zielonka at gmail.com> wrote:
> > 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?

True -- it would mean a bit more code, though.

> 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)))?

Ouch! thanks.