[Haskell-beginners] foldl by foldr
mjsaand at gmail.com
Thu May 13 23:12:53 EDT 2010
Thanks Edward, that makes a lot more sense.
At Thu, 13 May 2010 22:40:39 -0400,
Edward Z. Yang wrote:
> 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