Anyone who's been working with Haskell for a little while will encounter Foldable pretty quickly. This typeclass not only contains a range of useful operations, it is defined on a lot of different data types. However, every time I looked at the minimal required definition for a Foldable instance, I was always a bit puzzled. Essentially, you have the option of implementing one of either

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

or

foldMap :: (Monoid m, Foldable t) => (a -> m) -> t a -> m

While I had no issue understanding how everything provided by Foldable could be implemented based on foldr, I simply could not see how the same could be done with foldMap. I never gave it much thought until recently, when, on a whim, I decided to dig into this question. What I ended up discovering was both interesting and insightful, and I figured I'd share my thought process, as well as discoveries, with the world. So, here goes.

The smart semigroup, the marvelous monoid

Before we can discuss anything about Foldable or foldMap, we need to lay a few foundations. One such foundation is the semigroup, which is a structure that is both incredibly simple and common in mathematics. You can hardly go two steps into any mathematical discipline without seeing a semigroup, in fact. Intuitively, a semigroup is a set S with an associative binary operator · : (S, S) → S (that is, for any x, y, z in S, it should be the case that ((x · y) · z) = (x · (y · z))). Because of this associativity, we don't usually bother bracketing ·. In Haskell, we have an analogous type class, with appropriate laws, as follows:

class Semigroup a where
  (<>) :: a -> a -> a

-- Such that ((x <> y) <> z) == (x <> (y <> z))

We can extend this idea further by adding a unit element which does not change anything when combined with ·. In Haskell:

class (Semigroup m) => Monoid m where
  mempty :: a

-- Such that mempty <> x == x <> mempty == x

Now, this doesn't seem like much - I've had at least one person tell me that they don't see what the big deal about monoids is - but this simple idea is surprisingly powerful. It wouldn't be an exaggeration to say that many of the most critical parts of Haskell rely on monoids: for instance, both Applicative and Monad critically rely on the ideas behind monoids. In our case, though, it turns out that monoids also enable Foldable, which is why we need them around.

Just as with semigroups, monoids are everywhere; let's consider some notable ones. For starters, even something as simple as Bool can be a monoid - in two different ways! To distinguish between these (and help GHC understand which one we want), we define newtypes like so:

newtype Any = Any { getAny :: Bool }

instance Semigroup Any where
  (Any x) <> (Any y) = Any (x || y)

instance Monoid Any where
  mempty = False

newtype All = All { getAll :: Bool }

instance Semigroup All where
  (All x) <> (All y) = All (x && y)

instance Monoid All where
  mempty = True

Similarly, Int is also a monoid in two ways:

newtype Sum = Sum { getSum :: Int }

instance Semigroup Sum where
  (Sum x) <> (Sum y) = Sum (x + y)

instance Monoid Sum where
  mempty = 0

newtype Product = Product { getProduct :: Int }

instance Semigroup Product where
  (Product x) <> (Product y) = Product (x * y)

instance Monoid Product where
  mempty = 1

These are unsurprising and natural instances for which the respective laws are easy to verify. Another common and useful monoid is [a] for any a:

instance Semigroup [a] where
  x <> y = x ++ y

instance Monoid [a] where
  mempty = []

[a] is actually quite special as far as monoids are concerned, as it enables us to turn absolutely anything into a monoid; to use fancier language, [a] is the free monoid. Similarly, anything 'list-shaped' (such as Vector) can also be made into a monoid in a similar way.

We can also get more exotic monoids. Consider this (also important) example:

newtype Endo a = Endo { appEndo :: a -> a }

instance Semigroup (Endo a) where
  (Endo f) <> (Endo g) = Endo (f . g)

instance Monoid (Endo a) where
  mempty = Endo id

This is the monoid for endomorphisms, which are functions from values to values in the same type.

What's the point of these?

The commonality of monoids isn't their only notable features; they also define a way of 'folding'. Suppose we had a list of monoidal values, and we wanted to 'squash' it into a single value. Thanks to those values being in some monoid, we can do this operation no matter how many of them we have. To demonstrate, we have the following function:

mconcat :: (Monoid m) => [m] -> m
mconcat [] = mempty
mconcat (x : xs) = x <> mconcat xs

We have an mconcat for any Monoid whatsoever, although some monoids might be able to define this more efficiently. Additionally, because of the associativity of <>, we can perform mconcat in parallel by reassociating the uses of <> to look like a balanced binary tree instead of a list. For instance, if we had the following 2D list:

twoDee :: [[Int]]
twoDee = [[1, 2, 3], [4, 5], [6, 7, 8]]

the default mconcat would 'flatten' them as so:

slowFlatten :: [Int]
slowFlatten = [1, 2, 3] <> ([4, 5] <> ([6, 7, 8] <> []))

but thanks to associativity, we can instead do:

fastFlatten :: [Int]
fastFlatten = ([1, 2, 3] <> [4, 5]) <> ([6, 7, 8] <> [])

The savings between these can be substantial, especially if <> takes worse than O(1) time. More specifically, for any linear <>, performing the default mconcat on a list of length n full of monoidal values of 'length' k requires O(n²k) time, but by doing a reassocation similar to fastFlatten, we can bring this down to O(n log(n)k).

"Surely this isn't enough for us to define Foldable though?", I immediately hear you ask. You'd be right to think so, given the power and generality of foldr as a method. However, surprisingly, it is enough, and we're about to find out how.

Look Ma, no laws

Consider the following (considerably reduced) definition of Foldable:

class Foldable t where
  foldMap :: Monoid m => (a -> m) -> t a -> m

No, it's not a typo - there aren't any laws on this one. To quote the Haskell Wikibook, Foldable is both principled and general-purpose like that. There are definitely some expectations of what a sensible foldMap should do - it shouldn't 'skip' any values, for example - but we can't really pin any laws on it the same way we can for, say, Functor.

Let's think, intuitively, what foldMap says to us it can do. If we give a way of projecting as into monoidal ms, foldMap will do this for every a 'in' our Foldable, and then smush them all together similarly to mconcat above. An example of a (sensible) instance for [] would be:

instance Foldable [a] where
  foldMap f = mconcat . fmap f

The interesting thing about foldMap is that we can gain a massive diversity of behaviour by simply varying which Monoid we project our values into. Let's try a few, starting with the two different Monoid instances for (wrapped) Bools, with which we can recover these functions:

any :: Foldable t => (a -> Bool) -> t a -> Bool
any p = getAny . foldMap (Any . p)

all :: Foldable t => (a -> Bool) -> t a -> Bool
all p = getAll . foldMap (All . p)

We'll be seeing this 'project, wrap, foldMap, unwrap' pattern a lot in the rest of this post. Additionally, we can recover another useful function with a slight adjustment:

elem :: (Foldable t, Eq a) => a -> t a -> Bool
elem x = getAny . foldMap (Any . (==) x)

This is the first true sign of the power of foldMap. At a glance, elem has nothing to do with monoids or foldMap, yet the definition above demonstrates not only that these concepts are connected, but that we can define elem using only foldMap with an appropriate monoid.

So, Bool is getting a bit boring now; let's try Int instead. Defining sum and product is too easy (but worth doing for practice), so let's observe something more interesting:

length :: Foldable t => t a -> Int
length = getSum . foldMap (Sum . const 1)

count :: Foldable t => (a -> Bool) -> t a -> Bool
count p = getSum . foldMap (Sum . fromEnum . p)

Admittedly the second one is cheating a bit, as it takes advantage of the fact that fromEnum False = 0 and fromEnum True = 1, but at the same time, we again show the power of foldMap to define seemingly extremely unrelated concepts. count is especially clever, because it combines any and length in a clever way. Unfortunately for us, base doesn't provide count just yet (surprisingly).

Now I want to show probably the single coolest aspect of all this investigation (at least for me) - what we can define if we use [] as our monoid:

toList :: Foldable t => t a -> [a]
toList = foldMap pure

The sheer elegance of this definition amazes me - it's like all the pieces were invented the way they were just to make this work:

1. pure for lists defaults to creating a singleton list.
2. foldMap turns everything in an arbitrary Foldable into some Monoid, then smushes them all together.
3. This gives a demonstration of the essence of Foldableness, in a similar way to the way the Typeclassopedia describes it.

I have to state, for the record, that this definition of toList is definitely not efficient for almost any Foldable - we can usually define a toList that runs in O(n) for almost any Foldable, but this one will be O(n²) (at worst) or O(n log(n)) (at best). However, the elegance of this definition is still amazing.

The real heart of the problem

We can continue playing with our Foldable and different instances of Monoid for quite a while, and define some interesting and useful functions in the process. However, ultimately, what we want is to show just how something like foldr can be defined in terms of foldMap. It seems we need a truly special monoid to achieve this - and it happens to be Endo.

Now, suppose that, for some reason, we couldn't just look up Data.Foldable, and only had the above information to go on. Our goal is to define foldr, which we remind ourselves is:

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

Let's give it a whirl using our well-established pattern:

:t appEndo . foldMap (Endo . _)

-- Found hole: _ :: a -> b -> b

Hmm, we just happen to have something like that lying around: the first argument to foldr. So if we substitute that in and continue:

:t \f -> appEndo . foldMap (Endo . f)

-- Types as: Foldable t => (a -> b -> b) -> t a -> b -> b

This is really close to what we want, a bit of argument wrangling aside. At this stage, it's worth asking what exactly this is doing. Let's consider what happens when we provide a suitable function and Foldable instance to the skeleton above:

:t (\f -> appEndo . foldMap (Endo . f)) (+) [1,2,3,4]

-- Types as: Num a => a -> a

Ah, so our version of foldr essentially cooks us a custom function to transform some value into some other value of the same type (or, to use our already-established vocabulary, it cooks us a custom endomorphism). It does this 'cooking' as follows:

1. We provide a Foldable full of as.
2. foldMap 'maps' f over all of them, currying in each of those as as the first argument, then wraps each one up in an Endo b (which, as we know, is nothing other than a wrapper for b -> b).
3. foldMap then smushes all of these Endo bs together (essentially composing them all) into one big Endo, representing every 'stage' of this computation all in one go.
4. Lastly, we unwrap the resulting Endo to get our b -> b.

We now have a way of transforming any 'starting value' into whatever result would arise based on accumulating that starting value through multiple applications of f, using each a in our Foldable. Given that we specify nothing about b as part of the definition of foldr, we can, by definition, have this do anything that involves accumulation - which, as it turns out, is basically anything ever. Once again, the power of monoids and foldMap shows itself, and we now know why foldMap is enough.

Rounding out the fun

Just because we can, let's now consider how we can define foldMap with foldr, just to show that they are equivalent in power. Let's again imagine, for a second, that we couldn't just look up Data.Foldable. We have to go from this:

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

to this:

foldMap :: (Monoid m, Foldable t) => (a -> m) -> t a -> m

Given that foldr needs a 'starting value', let's try and figure that out first. We observe that this 'starting value' (typed b above) has to be the same as the final result. Given that we expect an m from foldMap, it means our 'starting value' has to be an m too. Additionally, this m is not provided - we have to be able to 'magic it up' regardless of what monoid we need. Clearly, only one thing fits: mempty. Let's see what this gives us:

:t \f t -> foldr f mempty t
-- Types as: (Foldable t, Monoid m) => (a -> m -> m) -> t a -> m

Close, but not quite - the signature for foldMap provides us a function of the type a -> m, but not a -> m -> m. We do, however, for anything that's an instance of Monoid, have a function of type m -> m -> m: (<>). Filling that in, we get this:

:t \f t -> foldr ((<>) . f) mempty t
-- Types as: (Foldable t, Monoid m) => (a -> m) -> t a -> m

Perfect! We have now closed the circle and demonstrated definitively that foldMap and foldr are equally powerful (if not necessarily efficient).

Wrapping up

Sorry, I couldn't resist that one. This foray into Foldable yielded me some interesting insights, which I hope will be useful for others. It once again reminds me how powerful good, law-abiding primitives, a little logic and creativity, and, of course, the power of Haskell, can be. Having read this, you can now better use Foldable in anger, understand why monoids are amazing, and had a fun time discovering something new (or at least, I did all the above; your mileage may vary).

For those who want to know more, I recommend mastering foldr by the late Ertugrul Söylemez (whose loss to the Haskell community is as major as it was sudden). If you enjoyed this sort of 'discovery post', I also recommend the following, which follow a similar approach:

• The Const Applicative and Monoids
• The Essence of the Iterator Pattern
• Lenses embody Products, Prisms embody Sums
• Free Lenses for Higher-Kinded Data
• You Could Have Invented Matrices!

Think hard and have fun, always.