Thanks, but it still does not help...
Well, you've removed the parentheses that give you the information you want.
Yes, I overlooked the parentheses. I meant what you said below:
foldl (++) [] [[1],[2],[3],[4]] ... -> (((([] ++ [1]) ++ [2]) ++ [3]) ++ [4])
now you have to ask what has to be evaluated in order to get the head of the result.
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.
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