Re: Fast Sequences

On Sun, Mar 26, 2006 at 06:35:14PM -0500, Jim Apple wrote:

On 3/26/06, Ross Paterson wrote:

...

the cost of reverse can only be observed by traversing the whole sequence.

So, head . reverse is . . . O(1)?

Certainly. The middle subtree, containing all but 2 to 8 of the elements, is unused.