This one helped. Thanks. 'reduction' was the key word that made it clear for me. It is not that left associated (++) reconstructs the list once and again (although one can say that) it is just that to return the head from the recursive invocations takes quadratic number of reductions. Right?
konst > -----Original Message----- > From: Jay Cox [mailto:[EMAIL PROTECTED]] > Sent: Sunday, April 07, 2002 11:09 AM > To: Konst Sushenko > Cc: [EMAIL PROTECTED]; Jon Fairbairn > Subject: Re: if (++) were left associative ? > > > 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 > > > _______________________________________________ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
