I’m re-reading Real World Haskell having spent time reading online material (such as the excellent Haskell Wiki) to supplement the book, it’s a much easier read the second time through!
That said, I still found myself a little puzzled by the section that provides an implementation of foldl, using foldr.
The type signatures of foldl and foldr are easy to understand:
foldl :: (a -> b -> a) -> a -> [b] -> a
foldr :: (a -> b -> b) -> b -> [a] -> b
Both take a function of two arguments, an initial value and a list of values.
The list is ‘folded’ into a single value, using the function. foldl sums
with left-associativity, foldr with right-associativity, e.g. summing
[1,2,3]:
foldl == (((0 + 1) + 2) + 3)
foldr == (1 + (2 + (3 + 0)))
Onto foldl using foldr! The implementation given in RWH is as follows:
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)
The key observations here are the use of the 3-parameter step function in
place of the usual 2-parameter function, and passing id instead of an initial
value.
To understand how this works, it’s useful to see how foldr is implemented:
foldr f e [] = e
foldr f e (x : xs) = f x (foldr f e xs)
Remember, in myFoldl, e is id and f is step
This means that when the foldr unwraps one layer of the list, instead of a
value, a one-parameter function (the partially applied step function) will be
returned; when e is returned by the base case, instead of an initial value, a
single-parameter function will be returned. So, we end up with a chain of one
argument functions.
To see this, let’s trace an execution (bear with it, as it is a little verbose):
1) myFoldl (-) 0 [1,2] = foldr step id [1,2] 0
For now we ignore the 0 and calculate foldr step id [1,2]:
2) foldr step id [1,2]
3) step 1 (foldr step id [2])
4) step 1 (step 2 (foldr step id []))
5) step 1 (step 2 (id))
6) step 1 (\a -> id ((-) a 2))
7) \b -> (\a -> id ((-) a 2))((-) b 1)
8) \b -> id ((-) ((-) b 1) 2)
9) \b -> ((-) ((-) b 1) 2)
Now we can see that we are left with a one-parameter function, so we can pass in 0 as the argument:
10) (\b -> ((-) ((-) b 1) 2)) 0
11) ((-) ((-) 0 1) 2)
The result: ((-)((-) 0 1) 2) can be rewritten as ((0 - 1) - 2) which shows
the left associativity.