greetings, the problem is that (++) rebuilds its first argument. in the example bellow the leftmost ++ rebuilds a list of length 0, the next (++) rebuilds a list of length 1, next one rebuilds a list of length 2, etc. this is where the quadratic complexity comes in. i am counting how many consings are happening. of course this is only quadratic if you need all the elements in the new list. if as in the example bellow you only need the head of the list, you only need to rebuild enough to get it. you noticed that you need to call ++ 3 times (and in general as many times as there are ++s, so we have a linear-time opertaion). in contrast, if the ++s were associated to the right, this is a constant time operation. and of course if you dont use any of the new list the whole thing happens in constant time :-) bye iavor On Sun, Apr 07, 2002 at 12:04:04PM -0700, Konst Sushenko wrote:

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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- ---------------------------------------+---------------------------------------- Iavor S. Diatchki | email: diatchki@cse.ogi.edu Dept. of Computer Science | web: http://www.cse.ogi.edu/~diatchki OGI School of Science and Engineering | work phone: 5037481631 OHSU | home phone: 5034996536 ---------------------------------------+----------------------------------------