# if (++) were left associative ?

**Konst Sushenko
**
konsu@microsoft.com

*Sun, 7 Apr 2002 12:04:04 -0700*

Thanks, but it still does not help...
>* Well, you've removed the parentheses that give you the
*>* information you want.
*>*=20
*
Yes, I overlooked the parentheses. I meant what you said below:
>* foldl (++) [] [[1],[2],[3],[4]]
*...
>* -> (((([] ++ [1]) ++ [2]) ++ [3]) ++ [4])
*>*=20
*
>* now you have to ask what has to be evaluated in order to get
*>* the head of the result.
*>*=20
*>* The answer is that you have to evaluate ((([] ++ [1]) ++
*>* [2]) ++ [3]) before you can find it, and to get that, you
*>* have to evaluate (([] ++ [1]) ++ [2]) and so on.
*>*=20
*
I understand that I have to evaluate all that to get the head of the
result, I just do not see how this ends up being quadratic. I have no
problem seeing that if each function's argument had to be evaluated
before the function is called but this is not the case here, right?
To simplify, lets have (([] ++ [1]) ++ [2]) ++ [3].
To get the head of result (++) is called recursively three times. The
last invocation returns [1] because its left argument is []. The
invocation before it (... ++ [2]) receives [1], and can return (1:..)
now, so it does. It does not finish constructing its whole result before
something is returned to (... ++ [3]). Here is the root of my
misunderstanding. The way I see it is that every time an element is
output by (++) at the bottom of the invocation chain, it is propagated
up the chain. No?
konst