if (++) were left associative ?

[Jay Cox]

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