Monoids and Semigroups — Scala

Published in

carlos-hernandez

5 min readSep 28, 2020

In this article we’re going to explore the monoid and semigroup, this will be our first introduction to purely algebraic structures. The reason to start with these structures is that they are simple to understand, ubiquitous and really useful.

Monoids come up all the time in everyday programming, whether we’re aware of them or not. Working with strings, lists or accumulating values all these are cases where we are using them. We’ll see how monoids are useful in parallel computation and in solving complex problems. They give us the power to break our problems down into different pieces in order to simplify them or to calculate them in parallel.

At this point I’m sure that you want to know more about them, so let’s move on and take a look at them in more detail.

What is a monoid?

Let's introduce the mathematic definition of a monoid:

In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element.

Perhaps the previous definition sounds really technical. But what we are really saying is that monoids allow us to add or combine values. Working with lists, concatenating strings or adding values.

Let’s explain this definition by looking at a few examples:

Binary operation: This means that every time we are adding or combining two elements of the same type together we are going to produce another element with the same type:

Int * Int = Int
Float + Float = Float
Boolean && Boolean = Boolean

Identity element: The identity is a special type of element which leaves any element unchanged when combined with it. This property is easier to understand by using examples as seen below:

0 + 8 = 8 -> Identity element 0
1 * 8 = 8 -> Identity element 1
false || true = true -> Identity element false
true && false = false -> Identity element true

Associative: This means that rearranging the parentheses in an expression will not change the result. For example, the operation add is associative:

(8 + 9) + 7 = 24
8 + (9 + 7) = 24

Whereas the operation subtraction is not associative as we can see below:

(8 - 9) - 7 = -8
8 - (9 - 7) = 6

These properties are not only related to mathematical operations. For example, we have the same properties for the String:

Binary operation:

String ++ String = String

Identity:

"eight" ++ "" = "eight"
"" ++ "eight" = "eight"

Associative:

"one" ++ ("two" ++ "three") = "onetwothree"
("one" ++ "two") ++ "three" = "onetwothree"

So what exactly is a monoid? It’s simply a generic type that satisfies these laws. Started tersely a monoid is a generic type with a binary operation, with an identity element and satisfying associativity. For example, the operation add is a monoid but the operation subtraction isn’t because it doesn’t satisfy the associative law.

Maybe at this point you are thinking, “OK I already know all of this, but why is it important?” Well, like any abstraction a monoid is useful because we can use it to write more generic code assuming only the capabilities are provided by the abstraction. We can write a generic code that can be used by different types (string, list, boolean…).

What is a semigroup?

Now let’s introduce the mathematic definition of a semigroup:

In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative binary operation.

This means that a semigroup is a generic type with a binary operation and satisfying associativity. In other words, a monoid is a semigroup plus an identity element.

As we can see below a monoid is an extension of a semigroup:

Monoid and Parallelism

The fact that a monoid’s operation is associative means we can calculate the values in any order. In other words, we can calculate the different terms in parallels and join them all up at the end, without this affecting the result.

3 + 4 + 5 + 6 + 12 + 1 = (3 + 4) + (5 + 6) + (12 + 1)
(3 + 4) = 3 + 4 = 7
(5 + 6) = 5 + 6 = 11
(12 + 1) = 12 + 1 = 13
result = (3 + 4) + (5 + 6) + (12 + 1) = 31

This is a really simple example, but we can solve much more complex problems in parallel. This is the real power of the abstraction: we don’t need to know the details of the problem, if we know it is a monoid we know that it will fulfill all three laws.

Let's implement a foldMap that splits the sequence in two, recursively processing each half, and then adding the result together with the monoid:

Monoid in Cats

In Cats we can combine elements using monoid with the operation |+| as we can see below:

Exercise

In this section I’m going to give you a really simple real-world example and solve it using monoids.

Imagine that we are working at an eCommerce company and our first task at this company is to create a simple method to calculate the total of a list of tickets.

Below you can see my solution to this problem:

The most important method in this code is getTotalTicket. It receives a list of tickets and returns a ticket with the total. To calculate the total we are using a custom monoid for Ticket (lines 11–16). The key of use monoids is that our code is now coupled less and in the future if we need to add new properties to our Ticket class we only need to change the monoid implementation. We can even create a more generic code as you can see below:

Summary

In this article we saw how we can write useful abstract code using monoids and the laws that govern them. Also, we learned about some of the properties of the monoids that permit us to write code that can be processed in parallel.

If you want to learn more about monoids and semigroups I recommend you read the official Cats documentation which you can find in the reference section.