I ran out of time last night and I don’t think I really finished addressing the other important point of the foldl via foldr implementation (Haskell: foldl via foldr).  So I thought I might take just a minute and try to get this point down before I forget…

The thing is that the final expansion of the expression:

step 1 (step 2 (step 3 ( id ))) 0

(step 2 (step 3 (id))) ((+) 0 1)
step 2 (step 3 (id)) 1
(step 3 (id)) ((+) 1 2)
step 3 (id) 3
id ((+ 3 3)
id 6
6

forces the evaluation of the left-most term first – even though precedence would ordinarily force the right-most term to be evaluate first.

Think of it this way, ordinarily, the (id) term would evaluate first since it is the innermost term.  But id is a function that requires a parameter to evaluate so it must wait until other terms are evaluated.  It simply remains part of the expression as a function pointer to be evaluated later.

Next, we expand step 3 – remembering that step x g a is to be replaced by g (f a x):

step 1 (step 2 (step 3 ( id ))) 0
step 1 (step 2 (id (+) ? 3)) 0
step 1 ((id (+) ? 3) ((+) ? 2)) 0
((id (+) ? 3) ((+) ? 2)) ((+) ? 1) 0

In each of these expansions, I’m using a question mark as a placeholder for a parameter to a curried function. The re-ordering of the parameters in the step function actually obscures what’s going on but I think it’s about to be made clear anyway.

This final expanded expression now evaluates left to right with each question mark being filled in by the expression to the right.  The id operator simply returns the value of the expression that follows.  The expression that follows returns the sum of a yet-to-be determined value and 3.  This yet to be determined value is simply the following expression: ((+) ? 2) but this expression is another curried function whose missing parameter is ((+) ? 1).  But this final expression’s missing parameter is visible at the end of the line: 0.

((id (+) ? 3) ((+) ? 2)) ((+) ? 1) 0
 - becomes -
((id (+) ((+) ((+) 0 1) 2) 3))
 - which is simply -
id (((0 + 1) + 2) + 3)

Inserting this last parameter gives the preceding expression as ((+) 0 1) which gives the value 1.  This, in turn, allows us to complete the expression that preceded it, giving us ((+) 1 2) which results in 3.  And, finally, this allows us to complete the first expression ((+) ? 3) as ((+) 3 3), giving us the result 6.

So, following this logic, the curried function and the missing parameters results in a left-to right evaluation of our original list so that, even though foldr (+) [1,2,3] would ordinarily evaluate to (1 + (2 + (3 + 0))), we instead get id (((0 + 1) + 2) + 3)

Do we care?  Well, arguably, this is simply a trumped up example and should probably never be attempted in real life (for both readability and performance reasons), the exercise of understanding it helps to drive home the point about how Haskell’s partial function evaluation works.