# A note on the connections between the Foldable methods

**URL:** <https://discourse.haskell.org/t/a-note-on-the-connections-between-the-foldable-methods/685>\
**Category:** Show and Tell\
**Created:** [May 18, 2019, 12:58am UTC](https://discourse.haskell.org/t/a-note-on-the-connections-between-the-foldable-methods/685 "2019-05-18T00:58:21Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![duplode](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/duplode/32/456_2.png) [@duplode](https://discourse.haskell.org/u/duplode)\
**Post date:** [May 18, 2019, 12:58am UTC](https://discourse.haskell.org/t/a-note-on-the-connections-between-the-foldable-methods/685/1 "2019-05-18T00:58:22Z")

</div>

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](https://en.wikibooks.org/wiki/Haskell/Monoids#Homomorphisms) `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](http://comonad.com/reader/2015/free-monoids-in-haskell/) 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](https://bartoszmilewski.com/2015/07/21/free-monoids/) with the derivation above in mind.)