Title: Haskell Magic: From semigroup to Foldable Date: 2018-09-24 Modified: 2018-09-26 Category: Blog Slug: haskell-magic-from-semigroup-to-foldable Tags: haskell-magic, haskell Summary: Where I talk about how I figured out why foldMap matters

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

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

or

```
:::haskell
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.

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:

```
:::haskell
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:

```
:::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:

```
:::haskell
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:

```
:::haskell
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`

:

```
:::haskell
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:

```
:::haskell
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.

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:

```
:::haskell
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:

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

the default `mconcat`

would 'flatten' them as so:

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

but thanks to associativity, we can instead do:

```
:::haskell
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.

Consider the following (considerably reduced) definition of `Foldable`

:

```
:::haskell
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 `a`

s into monoidal `m`

s, `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:

```
:::haskell
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) `Bool`

s, with which we can recover these functions:

```
:::haskell
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:

```
:::haskell
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:

```
:::haskell
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:

```
:::haskell
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:

`pure`

for lists defaults to creating a singleton list.`foldMap`

turns everything in an arbitrary`Foldable`

into some`Monoid`

, then smushes them all together.- This gives a demonstration of the essence of
`Foldable`

ness, 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.

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:

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

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

```
:::haskell
: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:

```
:::haskell
: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:

```
:::haskell
: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:

- We provide a
`Foldable`

full of`a`

s. `foldMap`

'maps'`f`

over all of them, currying in each of those`a`

s 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`

).`foldMap`

then smushes all of these`Endo b`

s together (essentially composing them all) into one big`Endo`

, representing every 'stage' of this computation all in one go.- 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.

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:

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

to this:

```
:::haskell
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:

```
:::haskell
: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:

```
:::haskell
: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).

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.