# Haskell Magic: From semigroup to Foldable

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

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

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

## 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 `a`s.
2. `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`).
3. `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.
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:

Think hard and have fun, always.