[Haskell-beginners] foldl by foldr

[Matt Andrew]

Thanks Edward, that makes a lot more sense.

Matt Andrew

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.
> 
> Cheers,
> Edward