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