Are new sequences really O(1)?

[Ross Paterson]

On Tue, May 24, 2005 at 08:29:57PM +0100, Adrian Hey wrote:
> Just been trying a few simple benchmarks to compare
> the new sequences with AVL trees for simple deque
> operations and I'm getting some strange results.

The stack overflow is interesting, and relates to all representations
based on lazy number systems.  If you build a structure without accessing
it, you get n/3 nested applications at the second level.  That's no more
space than they will evaluate to, but as soon as you access the second
level, they all go on the stack.  GCs that happen during this process
will be more expensive, as they have to scan the stack.  I suspect that
GC costs are swamping everything else for large n.

I've fixed the stack overflow; I believe this doesn't break the persistent
bounds.