How does Foldable.foldl work on Num a => a

Question

In LYAH, there is a piece of code that looks like this.

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)  

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  

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

As far as I know, foldMap is of type foldMap :: (Monoid m, Foldable t) => (a -> m) -> t a -> m, but Num a => a itself is not of type Monoid, so I am wondering how does Foldable.foldl actually work here? And since foldMap is called internally by Foldable.foldl, what is the type of the Monoid?

Answer 1

It's a bit easier to figure out if you consider foldr, which has the type (a -> b -> b) -> b -> t a -> b. The 'algebra' function has the type a -> b -> b, which you can view as a -> (b -> b) - that is: a function that takes a as input, and returns b -> b as output.

Now, b -> b is an endomorphism, which is also a monoid, and Data.Monoid defines a type Endo a (or here, it ought perhaps to be Endo b), which is, indeed, a Monoid.

foldr simply uses Endo internally to call foldMap:

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

foldl basically just flips the arguments around in order to do the same trick:

foldl :: (b -> a -> b) -> b -> t a -> b
foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z

To be clear, I literally copied these two function implementation from the Haskell source. If you go to the documentation of Data.Foldable, there are various links to view the source. That's what I did.