[Haskell-cafe] Would you mind explain such a code ?

staafmeister g.c.stavenga at uu.nl
Thu Sep 10 02:55:28 EDT 2009

zaxis wrote:
> myFoldl :: (a -> b -> a) -> a -> [b] -> a
> myFoldl f z xs = foldr step id xs z
>     where step x g a = g (f a x)
> I know myFoldl implements foldl using foldr. However i really donot know
> how it can do it ?
> Please shed a light one me, thanks!


Nice example! Well this is indeed an abstract piece of code. But basically
foldl f z xs starts with z and keeps applying (`f`x) to it
so for example foldl f z [1,2,3] = ((`f`3).(`f`2).(`f`1)) z

Because functions are first-class in haskell, we can also perform a foldl
where instead of calculating the intermediate values we calculate the
total function, i.e. ((`f`3).(`f`2).(`f`1)) and apply it to z.

When the list is empty z goes to z, so the start function must be id.
So we can write
(`f`3).(`f`2).(`f`1) = foldr (\x g -> g . (`f`x)) id xs

This is almost in your form.

Hope this helps,
View this message in context: http://www.nabble.com/Would-you-mind-explain-such-a-code---tp25377949p25378268.html
Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

More information about the Haskell-Cafe mailing list