Foldr/Foldl for free when Tree is implementing Foldable foldMap?
foldr can always be defined as:
foldr f z t = appEndo (foldMap (Endo . f) t) z
where appEndo and Endo are just newtype unwrappers/wrappers. In fact, this code got pulled straight from the Foldable typeclass. So, by defining foldMap, you automatically get foldr.
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).