Where do the foldl/foldr implementations of Foldable come from for binary trees in haskell?

Question

I'm working through Learn You a Haskell, and I'm on the section on monoids. In this section, the author defines the foldMap method for a tree as follows:

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  

Which works fine and is totally baller. However, he then states "Now that we have a Foldable instance for our tree type, we get foldr and foldl for free!" and shows the following code:

testTree = Node 5  
            (Node 3  
                (Node 1 Empty Empty)  
                (Node 6 Empty Empty)  
            )  
            (Node 9  
                (Node 8 Empty Empty)  
                (Node 10 Empty Empty)  
            )  

ghci> F.foldl (+) 0 testTree  
42  
ghci> F.foldl (*) 1 testTree  
64800  

Now I'm confused. Nowhere was an implementation for foldl or foldr written for Trees. The functions seem to work sort of like the foldmap, but putting the initial accumulator as the head of the tree, and then foldMapping over the appropriate monoid, but it can't actually be working like this because foldl and foldr take more general functions than the monoids '+' and '*' as arguments. Where are foldl and foldr actually implemented, how do they work, and why does defining foldMap cause them to exist?

Answer 1

Just have a look at the source of Foldable. It defines foldr using foldMap and vice versa, so it's enough to define the one that is more convenient for you (although implementing both can give you some performance benefits):

foldr :: (a -> b -> b) -> b -> t a -> b
foldr f z t = appEndo (foldMap (Endo . f) t) z

Let's examine what happens here on an example. Let's say we're about to fold a list [i, j, k]. The right fold with f and z is

f i (f j (f k z))

This can be expressed alternatively as

(f i . f j . f k) z

Using f, we convert each element of the list into an endomorphism on b and compose them together. Now endomorphisms form a monoid, which is expressed in Haskell using Endo: its mempty is just id and mappend is .. So we can rewrite it as

appEndo (Endo (f i) `mappend` Endo (f j) `mappend` Endo (f k)) z

and we can express the inner part as foldMap (Endo . f) [i, j, k].

To summarise: The key idea is that endomorphisms over some domain form a monoid, and f :: a -> (b -> b) maps elements of a into endomorphisms over b.

---

The reverse is expressed as

foldMap f = foldr (mappend . f) mempty

Here we have f :: a -> m where m is a monoid, and composing it with mappend we get mappend . f :: a -> (m -> m), which takes an element x of type a and construct a function on m that converts u :: m into mappend (f u) k. And then it uses this function to fold over all elements of the structure.