Foldr/Foldl for free when Tree is implementing Foldable foldMap?

Question

I am a beginner at Haskell and learning from "Learn You a Haskell".

There's something I don't understand about the Tree implementation of Foldable.

instance F.Foldable Tree where  
    foldMap f Empty = mempty  
    foldMap f (Node x l r) = F.foldMap f l `mappend`  
                             f x           `mappend`  
                             F.foldMap f r  

Quote from LYAH: "So if we just implement foldMap for some type, we get foldr and foldl on that type for free!".

Can someone explain this? I don't understand how and why do I get foldr and foldl for free now...

Metempsychosis

BTW, the mechanism for providing these free implementations is similar to the free implementation of /= you get if you implement == as discussed here – Revenge

Answer 1

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.

Histogenesis

Similarly, foldl can be defined in terms of foldr, and hence also foldMap, so that function comes for free also. – Koller

Answer 2

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).

Cumulation