foldl implemented using foldr
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.
foldr with right-associativity, e.g. summing
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
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,
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
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
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 ) 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)
((-)((-) 0 1) 2) can be rewritten as
((0 - 1) - 2) which shows
the left associativity.