Thanks, but you are assuming that foldl evaluates the intermediate result right away. If it were, then I have no problem seeing why time is quadratic. I am concerned about laziness though... My understanding of foldl is thus: foldl (++) [] [[1],[2],[3],[4]] -> foldl (++) ([] ++ [1]) [[2],[3],[4]] -> foldl (++) ([] ++ [1] ++ [2]) [[3],[4]] -> foldl (++) ([] ++ [1] ++ [2] ++ [3]) [[4]] -> foldl (++) ([] ++ [1] ++ [2] ++ [3] ++ [4]) [] -> [] ++ [1] ++ [2] ++ [3] ++ [4] Which brings me back to my original question...
-----Original Message----- From: David Feuer [mailto:dfeuer@cs.brown.edu] Sent: Sunday, April 07, 2002 3:21 AM To: haskell-cafe@haskell.org Subject: Re: if (++) were left associative ?
On Sun, Apr 07, 2002, Konst Sushenko wrote:
Hello,
this is probably embarrassing, but I just realised that I do not understand why list concatenation operation takes quadratic time if it is associated from left to right (see e.g. 'The Haskell School of Expression' by Hudak, p. 335):
cat1 = (++) cat2 = (++)
( [1,2] `cat1` [3,4] ) `cat2` [5,6]
My understanding is that cat2 is invoked before cat1, and as soon as the first element of cat1 is available, cat2 starts building its own result. cat2 does not need to wait until the whole list is emitted by cat1, does it? Where is quadratic time complexity?
Suppose we define
listseq [] x = x listseq (a:b) x = listseq b x
l = [1..n]
inter = foldl (++) [] (map (:[]) foo)
final = listseq inter inter
Then inter will be the result of concatenating [1],[2],[3],... from left to right. One meaningful question is: how long will it take to calculate "final"? This is (I believe) called the _shared cost_ of inter (while inter does not actually do any significant work, it produces a chain of suspensions that together do quite a bit.... I'm not sure if the way they are chained still allows this to be considered the shared cost, but I'm not sure).
1. How long does it take to calculate final ? Well, let's try it for n = 4:
inter = foldl (++) [] [[1],[2],[3],[4]] = foldl (++) ([]++[1]) [[2],[3],[4]] = foldl (++) [1] [[2],[3],[4]] = foldl (++) ([1]++[2]) [[3],[4]] = foldl (++) [1,2] [[3],[4]] = foldl (++) ([1,2]++[3]) [[4]] = foldl (++) [1,2,3] [[4]] = foldl (++) ([1,2,3]++[4]) [] = foldl (++) [1,2,3,4] [] = [1,2,3,4]
Note that in successive iterations, the following are calculated:
[]++[1] [1]++[2] [1,2]++[3] [1,2,3]++[4]
Since l1++l2 takes order length(l1), each concatenation takes more time than the previous one (linearly), so the total time for all of them is quadratic.