[Haskell-beginners] foldl by foldr

[Edward Z. Yang]

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.

Cheers,
Edward