RFC: general sequences

[Ross Paterson]

On Mon, May 23, 2005 at 04:19:12PM +0200, Tomasz Zielonka wrote:
> Are these operations really O(1) : (<|), (|>), viewL, viewR?

Yes, the amortized time of these operations is independent of the size of
the sequence.  Not worst case, but Haskell's laziness means most things
are amortized anyway.  Chris Okasaki's book "Purely Functional Data
Structures" contains a number of implementations of deques with such
bounds on these operations.  There are even implementations of deques
with O(1) worst case bounds, but these are quite a bit more complex.