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?

Have you looked at the source code for Data.Foldable? The definitions in the Foldable class should be informative enough to answer your question. — user824425
Haskell typeclasses can have default implementations of some methods in terms of others. In this they resemble how mixins work in other languages. For example, in Ruby you only need to define <=> to gain access to the rest of methods of Comparable. — danidiaz
possible duplicate of Foldr/Foldl for free when Tree is implementing Foldable foldmap? — Andrew B.

Petr Petr · Accepted Answer · 2013-05-26T11:06:14

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.

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

2 Answers