A note on the connections between the Foldable methods

Show and Tell
1

Here is an account of how we know that each of the core methods of Foldable – foldMap, foldr and toList – suffices to characterise the other two. While there are no earth-shattering news in what follows, I can’t recall having seen this argument being spelled out explicitly and in full (though perhaps I just haven’t looked hard enough), so it might be worth it to put it down to paper.

foldMap

I will use foldMap as a starting point because, for our current purposes, it is easier to work with than the other two.

The argument hinges on how, for any f :: Monoid m => a -> m, and any monoid homomorphism h :: (Monoid m, Monoid n) => m -> n:

h . foldMap f = foldMap (h . f)

This property is ensured by parametricity – in fact, it is a part of the free theorem for foldMap.

foldr

Endo . mappend :: a -> Endo m happens to be a monoid homomorphism. Plugging that into the property above, we get:

Endo . mappend . foldMap f = foldMap (Endo . mappend . f)

Now, apply both sides to some xs container, and then to mempty:

appEndo (Endo . mappend . foldMap f xs) mempty 
    = appEndo (foldMap (Endo . mappend . f) xs) mempty
mappend (foldMap f xs) mempty 
    = appEndo (foldMap (Endo . mappend . f) xs) mempty
foldMap f xs = appEndo (foldMap (Endo . mappend . f) xs) mempty

At this point, we can adopt the following definition:

foldr :: Foldable t => (a -> (b -> b)) -> b -> t a -> b
foldr g i = appEndo (foldMap (Endo . g) xs) i

From the result just above, it immediately follows we can also define foldMap in terms of foldr:

foldMap f xs = foldr (mappend . f) mempty xs

toList

Two other monoid homomorphisms, this time involving lists map g :: [a] -> [m] for any g, and mconcat :: Monoid m => [a] -> m. The composition of two monoid homomorphisms is also a monoid homomorphism; therefore, we can substitute mconcat . map g into that parametricity property:

mconcat . map g . foldMap f = foldMap (mconcat . map g . f)

As for f, we now need it to produce lists, so let’s pick the simplest non-trivial choice, (:[]) :: a -> [a]:

mconcat . map g . foldMap (:[]) = foldMap (mconcat . map g . (:[]))

Since (:[]) returns single-element lists, we can simplify the right side to:

mconcat . map g . foldMap (:[]) = foldMap g

We might as well give a name to the list-making fold that has shown up here:

toList :: Foldable t => t a -> [a]
toList = foldMap (:[])

It is therefore possible to define foldMap for any Foldable in terms of toList plus a couple list operations:

foldMap g = mconcat . map g . toList

Or, since the chosen monoid homomorphism mconcat . map g happens to be foldMap g for lists:

foldMap g = foldMap g . toList

In other words: as far as Foldable is concerned, xs and toList xs boil down to the same thing upon folding.

(On a final note, the role of lists here has fundamentally to do with how lists are, caveats about bottoms aside, free monoids for Haskell types. In particular, it is interesting to read the discussion in the “Free Monoid Universal Construction” section of Category Theory for Programmers’ chapter about free monoids with the derivation above in mind.)

4 Likes