Spent some time this afternoon reading through Real World Haskell this afternoon exploring the topic of strict evaluation versus non-strict evaluation and came across an example of foldl implemented using foldr.  After a mind-bending half-hour or so, I was able to piece together an idea of what is actually happening in this example so I’m noting it here to help me remember in the future.

The code in question is:

myFoldl :: (a -> b -> a) -> a -> [b] -> a
myFoldl f z xs = foldr step id xs z
    where step x g a = g (f a x)

I’m attempting the function expansion in phases based on the following invocation:

myFoldl (+) 0 [1, 2, 3]

First, I’m ignoring the step function and simply expanding for each list member:

foldr (step) id (1:2:3:[]) 0
step 1 (foldr (step) id (2:3:[])) 0
step 1 (step 2 (foldr (step) id (3:[]))) 0
step 1 (step 2 (step 3 (foldr (step) id ([])))) 0
step 1 (step 2 (step 3 ( id ))) 0

Note carefully that the first line is a simply foldr invocation but there are too many parameters – there is an extra 0 at the end.  This is carried through the entire expansion.

Now, I’ll expand the internal step method. This is tricky because it is a partial function and it seems to re-order the entire expression. As a reminder, the signature for this method is:

 step x g a = g ((+) a x)

As I pointed out earlier, this pretty much rewrites the expansion above.  To make it easier to follow, I’ll expand the outermost invocation of the step method first (see the block that follows the next paragraph – The line I’m going to expand appears first).  The x parameter of the step method takes the value 1, the g parameter takes the value (step 2 (step 3 (id))).

Now, initially, it might appear that the a parameter does not have a value but as I hinted earlier, this is a trick of Haskell because the step function has been “curried” by the foldr invocation.  In other words, this method has been partially invoked, resulting in a method that is awaiting its final parameter – a parameter that arrives by means of the extra 0 parameter supplied after the foldr.

This first invocation of step expands this way:

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

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

The (step 2 (step 3 (id))) clause has been moved to the front as parameter g.  Next, the f parameter passed into the outermost myFoldl function makes its return in the (f a x) clause of the step function body.  In our example, f is simply the plus operator.  Now that is followed by the step function’s a parameter then its x parameter.  In our example, this simply evaluates to (a + x) (though in the odd, but perfectly legal equivalent expression ((+) a x) – yielding ((+) 0 1) which evaluates to 1).

While it would be perfectly valid to repeat this step and then compute the result after, I find it a little bit more intuitive to evaluate the expression now and then expand the next level for each invocation of step:

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

So, you can see (at least I hope you can see) that the myFoldl function yields the same result as foldl would but in a very backhanded way – which teaches us a little bit more about Haskell under the covers…