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

Reply via email to