A note on the connections between the Foldable methods

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