We begin with the type of foldMap:
foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m
foldMap works by mapping the a -> m function over the data structure and then running through it smashing the elements into a single accumulated value with mappend.
Next, we note that, given some type b, the b -> b functions form a monoid, with (.) as its binary operation (i.e. mappend) and id as the identity element (i.e. mempty. In case you haven't met it yet, id is defined as id x = x). If we were to specialise foldMap for that monoid, we would get the following type:
foldEndo :: Foldable t => (a -> (b -> b)) -> t a -> (b -> b)
(I called the function foldEndo because an endofunction is a function from one type to the same type.)
Now, if we look at the signature of the list foldr
foldr :: (a -> b -> b) -> b -> [a] -> b
we can see that foldEndo matches it, except for the generalisation to any Foldable and for some reordering of the arguments.
Before we get to an implementation, there is a technical complication in that b -> b can't be directly made an instance of Monoid. To solve that, we use the Endo newtype wrapper from Data.Monoid instead:
newtype Endo a = Endo { appEndo :: a -> a }
instance Monoid (Endo a) where
mempty = Endo id
Endo f `mappend` Endo g = Endo (f . g)
Written in terms of Endo, foldEndo is just specialised foldMap:
foldEndo :: Foldable t => (a -> Endo b) -> t a -> Endo b
So we will jump directly to foldr, and define it in terms of foldMap.
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
foldr f z t = appEndo (foldMap (Endo . f) t) z
Which is the default definition you can find in Data.Foldable. The trickiest bit is probably Endo . f; if you have trouble with that, think of f not as a binary operator, but as a function of one argument with type a -> (b -> b); we then wrap the resulting endofunction with Endo.
As for foldl, the derivation is essentially the same, except that we use a different monoid of endofunctions, with flip (.) as the binary operation (i.e. we compose the functions in the opposite direction).
