if (++) were left associative ?

[David Feuer]

On Sun, Apr 07, 2002, Konst Sushenko wrote:
> This one helped. Thanks.
> 
> 'reduction' was the key word that made it clear for me. It is not that left associated (++) reconstructs the list once and again (although one can say that) it is just that to return the head from the recursive invocations takes quadratic number of reductions. Right?

I don't think so.  I think it only takes linear time to get the head.
But once you've gotten the head, it takes linear time again to get the
head of the tail, ....  You get (I think...) a progression like
n+(n-1)+(n-2)+...+1, which is in O(n^2).

David