*This post assumes basic experience with functional programming in Scala/Cats, Haskell or other languages.*

### The problem

The other day a colleague asked a question in our internal Scala channel.
They were writing some Scala code and assembled a list of functions `DomainType => Eval[DomainType]`

.
This list represents a „pipeline“ of sorts and they wanted to run all of them, one after the other.
The `Eval`

type comes from the Cats library and represents a lazily-evaluated computation.
To keep things simple, let’s assume the functions had the type `Int => Int`

.

The easiest solution would be a fold:

Let’s try this out:

Nice! Working as expected.
Now we can just extend this to `Eval`

(using `flatMap`

) and call it a day, right?
Well, no.
We were looking for something elegant!
The `eval`

function has to do a manual fold.
But us functional programmers are lazy.
We want to (ab)use some more abstract machinery to turn this into a one-liner.

### The problem (but abstract)

Let’s first hash out the types of the things we’re interested in.

We start with a *list* of *functions* with identical input and output type.
We want to obtain a *function* with the same type.

That sounds an awful lot like a higher-order function. What’s its type signature?

Cool.
But is the `List`

really relevant?
After all, if we know how to compose *two* functions, we can generalize that to an arbitrary amount of functions.

Something about that rings a bell. We’ll fetch our beloved algebra text book and look this up. What do we find?

A monoid is a triple (

M, ∘,e) whereMis a set, ∘ a binary operator andx∈Mthat satisfies the following properties:

- ∘ is
closed, that is, for allx,y∈M:x∘y∈Meis the identity of ∘, that is, for allx∈M:x∘e=e∘x=x- ∘ is associative, that is, for all
x,y,z∈M: (x∘y) ∘z=x∘ (y∘z)

Ah, right. Good old monoids!

### Monoids in programming

Unable to follow?
No problem.
All of the above is how a mathematician would express the concept of a *monoid*.
In Scala, we can use some more familiar terms:

This definition conveniently uses words instead of symbols. But there’s a clear mapping between those concepts:

- the type parameter
`T`

corresponds to the set*M*, - the
`empty`

method corresponds to the identity element*e*, and - the
`combine`

function is the binary operator ∘.

Cats and other libraries provide these trait representations for use as type classes.

Before we get to the main issue of this post, let’s briefly discuss how to map the mathematical properties to the `Monoid`

trait.
The first one is a given, because the types already prescribe that `combine`

returns a value of the same type.
The second and third properties can be expressed in ScalaCheck and must be tested manually.

### The function monoid

Cats already ships with a ton of monoid implementations. Let’s check if we can find one for our functions:

That’s dandy.
Conveniently, there’s also a pre-defined method on the `Monoid`

trait that’s called `combineAll`

and recursively applies `combine`

to a list of things (in other words, it performs the folding for us):

Uh oh. That looks unexpected. Maybe it composed those functions the other way round? Well, no, because 7 is not the result of taking 2, doubling it (4) and adding 1 (5) either. What happened here?

### Are monoids unique?

I hate to break it to you, but monoids are not unique.
That means that for any given type, there may be more than one valid instantiation of the `Monoid`

trait.

For starters, switching around the `combine`

operation *always* makes for a valid monoid, if the original one was valid:

Does the order matter? Not for common arithmetic operations, but there are certainly monoids for which it does matter:

Concatenation of lists is certainly a monoid:
the empty element is `Nil`

and to combine two lists we just use `:::`

.

The mathematicians have a particular name for this.
If in an operation ∘, the order of arguments does not matter, the operation is called *commutative*.
Formally: for all x, y: x ∘ y = y ∘ x.

If in a monoid, the operation is commutative, that monoid is called *abelian* (after the mathematician Niels Henrik Abel).

Long story short: for any non-abelian monoid, we can easily construct a different monoid by just flipping the order of arguments!
(For abelian monoids, the swapping doesn’t change the operation.)
In consequence that means that we can’t necessarily talk about „the list monoid“ or „the monoid for type `X`

“, because there might be more than one.

It appears that there is something similar going on for our functions.

### Very much not unique

It gets worse. We can define multiple competing monoids for lots of structures, without resorting to tricks like swapping the arguments:

- For
`Option`

, we can either return the first`Some`

or, when encountering two`Some`

s,`combine`

the contained values. - For
`List`

, instead of concatenation, we can „zip“ them together (discarding extra elements if one list is longer than the other) and then`combine`

the elements. - For any ordered type, we have a monoid where
`combine`

returns the maximum (or minimum) of the two arguments (monoid formed by a lattice). - For any type at all, we can define a monoid that just returns an arbitary „neutral“ value or always the first value or …

### About those functions

Now, let’s investigate what the default function monoid from above does. Here’s a brief reminder:

Got an idea?

The solution of this puzzle is as follows:

This construction is called *pointwise*.
Again, there is a meaning behind the term *point* (it’s from category theory), but that’s besides the point here (pun intended).

All so-called pointwise operations on functions follow the same structure:
they take a function argument *x* and then apply all functions on the same argument *x* and combine the results somehow.
Here, it literally uses the `combine`

method for the return type.

This also explains why this monoid for `A => B`

only requires a monoid implementation for `B`

, but not for `A`

.

In languages with stronger type inference than Scala, like in Haskell, we can completely get rid of those type parameters. Some readers may find this clearer (if not, just ignore it):

Type inference will figure out that the `mconcat`

on the right-hand side is the one for `b`

, whereas the one on the left-hand side is the one for `a -> b`

.

Frequently, functional programmers call such a construction like `functionMonoid`

a *lifting*.
The reason is that we take an existing structure (a monoid) over a type `B`

and raise it into a new context (`A => _`

).

##
Lifting into arbitrary contexts

Advanced functional programmers will have noticed that I used `A => _`

as context instead of `A => B`

.
This is on purpose:
the *context* in this scenario is a type with exactly one hole, i.e. a type constructor with one type argument.

With a little bit of imagination, this suggests that there may be other type constructors where monoids can be lifted into. It turns out that yes, this works for arbitrary applicative functors:

Notice two things about this definition: Firstly, it is very hard to give any kind of reasonable names to the type and value parameters because the concepts are becoming too abstract to have any relationship with any business domain. This is why functional programmers love single-letter names, since you can’t interpret them in any way; hence you can’t interpret them wrongly.

Secondly, we’re veering dangerously close into symbolic operator territory.

Let’s confirm that this is in fact the definition that Cats uses by default when summoning an implicit monoid for `Int => Int`

:

As it turns out, the pointwise function monoid is a special case of the applicative monoid for the reader (`F[x] = A => x`

) applicative.

It’s not entirely trivial to see that the monoid that comes out of this construction is in fact valid.
The high-level reasoning uses the fact that the `mapN`

operation is associative and respects the identity (i.e. the `pure`

operation).

Fun fact: Cats has a dedicated type class for the binary `mapN`

operator required for the `combine`

operation:

A monoid without the empty element is also called a *semigroup.*
Do you hear the sound of the plot thickening?
What happens when we add an „empty“ element to a „semigroupal“?

This operation is often also called `return`

(in Haskell) or `pure`

.

Ever heard of this infamous quote, popularized by James Iry:

A monad is just a monoid in the category of endofunctors, what’s the problem?

Various explanations of this witticism can be found on Stack Overflow, but let me say this:
A monad (which is also an applicative functor) is a thing that has an identity element and an associative bind (`flatMap`

) operation.
For the purpose of this post, I’ll leave it at that, since it is just an interesting tangent.

But clearly, this is not the monoid we are looking for.

### Monoids that compose

Let’s get back to the original mystery function we posited above:

Notice that as opposed to the monoid we saw above, we don’t have `A => B`

(i.e. different parameter and return type) but `T => T`

(i.e. same parameter and return type).

Haskellers tend to call such functions *endo*, which stems from the mathematical term *endofunctor*.
In my opinion, this naming is not entirely accurate, but let’s roll with it.
We can define a monoid for this type as follows:

Let’s verify that this works:

Nice! Working as expected.

Before we move on to the final complication, namely the return value that’s wrapped in `Eval`

, let me point out a very sad thing:
this monoid is almost never abelian, because you can’t just flip the order of function composition.
That means that you’ll have to be excrutiatingly careful when composing functions like this (not that that would be any different when using folds).

For the (frequent) use case of having a function that returns a value wrapped in a type constructor, Cats offers a convenient abstraction:

It comes with compose functions and everything that employ the `flatMap`

method of `M`

.
The name *Kleisli* comes from the mathematician Heinrich Kleisli.

We can also find a monoid instance for this, but it is slightly involved, as it goes through a bunch of other abstractions:

Now we just need to consider our *actual* list of lazy functions:

Let’s try this out:

Well, those have clearly been executed in the wrong order!
I said *careful*!

Much better! Now, what do we learn from this?

### Disambiguation

Choosing the correct monoid is hard.
Unfortunately, all of the different monoids for a given type are standing in each other’s way.
Type systems like Scala’s and Haskell’s however expect only at most one possible type class instance for a given type.
That’s why classes like `Kleisli`

exist, in order to somewhat artificially construct a distinct type that – while having the same capabilities as the original type – may have different instances.
For endo functions like in this blog post, this is currently still missing in Cats.

What do we learn from this? Monoids are an ubiquitous and versatile structure in functional programming and we’d better double-check which one we have before doing anything with it.