This post assumes basic experience with functional programming in Scala/Cats, Haskell or other languages.
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.
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
flatMap) and call it a day, right?
We were looking for something elegant!
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?
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) where M is a set, ∘ a binary operator and x ∈ M that satisfies the following properties:
- ∘ is closed, that is, for all x, y ∈ M: x ∘ y ∈ M
- e is the identity of ∘, that is, for all x ∈ 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
Tcorresponds to the set M,
emptymethod corresponds to the identity element e, and
combinefunction 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
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:
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
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:
Option, we can either return the first
Someor, when encountering two
combinethe contained values.
List, instead of concatenation, we can “zip” them together (discarding extra elements if one list is longer than the other) and then
- For any ordered type, we have a monoid where
combinereturns 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
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 => _).
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
Fun fact: Cats has a dedicated type class for the binary
mapN operator required for the
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
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 (
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
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?
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.