Exploring a simple but powerful concept in abstract Algebra and category theory
What Are Monoids?
If you’re not familiar with monoids, don’t worry. It’s a simple but powerful concept in abstract Algebra and category theory.
For this article, I will stick with the definition from abstract algebra, which is easier to understand.
To understand what a monoid is, we need to understand what a semigroup is first.
Semigroup
A semigroup is a set with a binary operation.
A binary operation is, for example, the addition operation +.
Monoids
A monoid is a semigroup with an identity element.
- Identity element — when an identity element is applied to any other element, it does not change its value. In the example below, e is an identity element.
e * a = a
Monoid examples (got to love them):
- Non-negative Integers
The set — non-negative integers.
The binary operation — addition.
The identity element — zero.
This binary operation is closed. No matter which two non-negative integers you add together, the sum will always be a non-negative integer:
5 + 3 = 8
This binary operation is associative:
(1 + 2) + 3 = 1 + (2 + 3)
And it has an identity element:
3 + 0 = 3
0 + 1 = 1
Therefore, it’s a monoid!!
2. Booleans
The set — {true, false}.
The binary operation — OR.
The identity element — true.
The binary operation is closed:
true OR false = false
false OR true = false
The binary operation is associative:
(true OR false) OR true = true OR (false OR true) // both false
It has an identity element true:
false OR true = false
true OR true = true
3. Strings (oh yes!)
The set — Strings.
The binary operation — string concatenation.
The identity element — empty string.
"A" + "B" = "AB"
("C" + "D") + "E" = "C" + ("D" + "E")
"A" + "" = "A"
"" + "A" = "A"
And many more!
Why Should I Care About Monoids?
We understood what monoids are and saw some nice examples, but why should we care?! We are tough-ass programmers, not mathematicians!
This basic mathematical structure shows up a lot in programming.
Monoids have broad applications in basic arithmetic, lists, strings, reactive programming, concurrent programming, etc.
They provide a simple yet powerful abstraction for combining values.
Build Our Own Monoid in TypeScript
First, we will define the semigroup type:
- concat — binary operation, which gets two elements of the same type and combines them.
The definition of the Monoid type only adds one thing: the identity element.
empty will return the identity element.
We’re now ready to implement our first monoid, which will be called the Sum monoid.
- The identity element for addition is 0.
- The binary operation is the addition operation (+).
How can we add two numbers using monoids?
It may seem strange and involve a lot of code, but hang on! We’ll soon discover why monoids are awesome.
How can we use the Sum monoid to add an array of numbers together?
Our goal is to take an array of numbers and reduce it to a single value:
Sum.concat serves as the callback function for reduce function, and the initial value is Sum.empty().
This code is wonderfully declarative!
Now, let’s move on to a less trivial example and create the Any monoid.
How can we use the logical OR operator monoid to check if any of the values in a boolean array are true?
Just like we did with the Sum monoid, I hope you guessed it!
A handy abstraction here can perform the same operation for any monoid. It’s called fold (name from Haskell).
The Fold Function
The first parameter of the fold function would be the array, which represents the foldable data structure.
A foldable data structure refers to any data structure that can be folded up into a summary value.
This means that the fold function can work with various data structures.
The second parameter would be our beloved monoid, which can be any monoid (that’s why it’s so powerful).
The return value of the fold function is the summary value.
Let’s take a look at the function signature:
And the implementation follows a similar pattern to what we have already done:
And now, we have a generic function that can be used with any monoid and foldable data structure.
Let’s revisit the examples we discussed earlier, this time using the fold function:
To the next level and beyond!
The foldMap Function
To understand foldMap, let’s consider an example.
Let’s say we are writing the code for a lottery company. We must create a function that determines whether a person has won. The rules are as follows:
- A person can submit multiple tickets.
- Each ticket is represented as an array of digits between 1 and 5.
- If the sum of the digits on all the tickets is 39, the person has won.
Here’s the function signature:
There are multiple ways to implement isWinner, but I will show you how to solve it using monoids.
We can now use the Any monoid, that, when combined with the fold function returns a boolean indicating whether any value in the array is true.
However, we then encounter a problem: we have an array of Tickets, not an array of boolean. This is where foldMap comes into play.
foldMap is similar to fold, only it allows us to map each element of the foldable data structure before performing the fold operation. That is exactly what we were missing in this case.
- Above, you can see the first parameter — the mapper function which maps an element into the monoid type.
- The second parameter is the monoid itself.
- The third parameter is the foldable data structure.
To use foldMap, we need to create the mapper function, so it can map a Ticket to a boolean.
The first step in creating the mapper function is writing a function that calculates the sum of the digits, which can be achieved using fold.
After calculating the sum, we need to check if the sum is equal to 39. We will incorporate this logic into our mapper function.
And now we are finally ready to use foldMap:
Unfortunately, we didn’t win this time, but our code looks beautiful. We let the monoid and the foldMap handle the heavy lifting, and we only needed to implement our business logic in the isWinnerTicket function.
You can check out the full example and experiment with it in the link below:
TS Playground – An online editor for exploring TypeScript and JavaScript
Conclusion
First, we discussed what semigroups and monoids are and how monoid provides us with a powerful abstraction and a clean interface.
We saw examples of popular monoids, such as Any, Sum (and there are many, many more).
We used fold and foldMap to obtain monoids’ power, write a clear, declarative, and reusable code.
Monoids have much more to offer. Here are the resources I have used in this article. Do feel free to explore. Happy learning!
Editing credit: Keren Haham.
- Data.Semigroup
- Monoid
- Foldable and Traversable
- Learn Functional Programming Architecture with Brian Lonsdorf
- Data.Monoid
Monoids in TypeScript was originally published in Better Programming on Medium, where people are continuing the conversation by highlighting and responding to this story.