RE: if (++) were left associative ?
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.
Thanks,
but you are assuming that foldl evaluates the intermediate result right away.
It must
My understanding of foldl is thus:
foldl (++) [] [[1],[2],[3],[4]]
[snip]
-> [] ++ [1] ++ [2] ++ [3] ++ [4]
Which brings me back to my original question...
Well, you've removed the parentheses that give you the information you want. 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]) 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. In the other case, you can get the head of (a:...)++ (b ++ c) by evaluating only the first steps of the first (++). Does that help? Jón -- Jón Fairbairn Jon.Fairbairn@cl.cam.ac.uk 31 Chalmers Road jf@cl.cam.ac.uk Cambridge CB1 3SZ +44 1223 570179 (after 14:00 only, please!)
On Sun, 7 Apr 2002, Jon Fairbairn wrote:
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.
In the other case, you can get the head of (a:...)++ (b ++ c) by evaluating only the first steps of the first (++).
Does that help?
Jón
Just to add a bit. "evaluate" is such a fuzzy word, especially in a lazy language. You must know the context of the expression in order to know how much of it is actually evaluated*. (* Eventually, the context of all expressions in haskell will be the evaluation of something in the IO monad, but generally you don't have to go that far in your reasoning about contexts and stuff.) Ok. I shall now attempt to explain a bit more deeply the differences between the evaluation expressions which use a left associative append versis expressions uing a right associative append. In the following,"tail" means any arbitrary tail of a list. Also, for the sake of argument, assume : binds closer than ++ and function application so we dont have to mess with so many damn parentheses. (in reality I don't think anything binds closer than function application in Haskell.) the definition of ++ is like [] ++ b = b (l:ls) ++ b = l:(ls++b) applist = ((w:tail ++ x:tail) ++ y:tail) ++ z:tail This can be rewritten as the following, so we can litterally see the leftmost-outermost-reduction. applist = (++) ((++) ((++) w:tail x:tail) y:tail) z:tail ick! lets say f=(++) (or that f is the same function as the append operator (++)) applist = f (f (f w:tail x:tail) y:tail) z:tail Alright. Now say we want the head of this applist. So lets use the head function. head patern matches against that thing, causing a reduction of the outmost f. Since f pattern matches against its first arguement, it must cause a reduction in the second f in that expression, and likewise the third f. The third f will succeed in its pattern match, namely (w:tail). Now, f, which was (++), will get unfolded. using the original definition of (++) (l:ls) ++ b = l:(ls++b) this becomes (w:tail) ++ (x:tail) = w:(tail ++ x:tail) (which in our notation is w:(f tail x:tail)) substuting our unfolding back into applist and continuing with reductions: f (f (f w:tail x:tail) y:tail) z:tail -> f (f w:(f tail x:tail) y:tail) z:tail -> f w:(f (f tail x:tail) y:tail) z:tail -> w:(f(f(f tail x:tail) y:tail) z:tail) so its not like it will take length (w:tail) + length (x:tail) + length(y:tail) reductions or whatever, but it does take 3 reductions to get to the head, AND WILL BY NECESSITY take 3 reductions to get each element of the rest of the tail of w:tail. I >think< in the end, if you need all of applist, you will need something like 3*length (w:tail) + 2*length(x:tail) + length(y:tail) reductions of f. That is definitely NOT linear with (length x:tail) + (length y:tail) + (length z:tail) Now. Lets try go get the head of w:tail ++ (x:tail ++ (y:tail ++ z:tail)) doing like before with (++), that is f w:tail (f x:tail (f y:tail z:tail)) and now f pattern matches, etc. ->w:(f tail (f x:tail (f y:tail z:tail))) and thats the ONLY reduction necessary. getting all of applist should only require something close to (length x:tail) + (length y:tail) + (length z:tail) reductions of f. I'm sure I'm not %100 accurate here, (and It's not worth the effort for this message!) but I hope this gives more insight and not more confusion! Cheers, Jay Cox
participants (3)
-
Jay Cox -
Jon Fairbairn -
Konst Sushenko