[Haskell-beginners] foldl by foldr
Edward Z. Yang
ezyang at MIT.EDU
Thu May 13 22:40:39 EDT 2010
Excerpts from Matt Andrew's message of Thu May 13 22:29:01 -0400 2010:
> The offending code is:
> myFoldl :: (a -> b -> a) -> a -> [b] -> a
> myFoldl f zero xs = foldr step id xs zero
> where step x g a = g (f a x)
> The thing I am having trouble understanding is what the 'id' function is
> doing in a function that expects 3 arguments and is given 4 (foldr).
The trick between building foldl with foldr is the fact that, where other
folds might be accumulating values like integers or lists, this foldr is
accumulating *functions*. This parenthesized version is equivalent:
myFoldl f zero xs = (foldr step id xs) zero
Since foldr is returning a function. In this case, id seems like a natural
base case, since it is an extremely simple function.
Hint: Try specializing this over some f and zero you know well, like + and 0,
and then manually drawing out the structure and seeing what happens.
More information about the Beginners