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