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:[EMAIL PROTECTED]] > Sent: Sunday, April 07, 2002 3:21 AM > To: [EMAIL PROTECTED] > 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. > _______________________________________________ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
