## Functional Programming in Kotlin by Tutorials

First Edition · Android 12 · Kotlin 1.6 · IntelliJ IDEA 2022

#### Before You Begin

Section 0: 5 chapters

#### Section II: Data Types & Typeclasses

Section 2: 5 chapters

# 12. Monoids & Semigroups Written by Massimo Carli

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

In this chapter, you’ll learn everything you need to know about a couple of very important typeclasses. You may be surprised that you’ve used these typeclasses all the time without knowing it:

• Monoids
• Semigroups

You’ll understand their meaning in the context of category theory, and more importantly, you’ll learn their implications in your favorite category: types and functions. In particular, you’ll see:

• A first, familiar definition of monoid.
• A possible monoid typeclass definition in Kotlin.
• What property-based testing is.
• How to use property-based testing to verify the monoid laws.
• How monoids are handy when used with `Foldable` data types.
• The meaning of a monoid in category theory.
• What a semigroup is and how it differs from a monoid.

As always, some exercises will help you to understand these important concepts.

## What is a monoid?

A monoid is a simple concept, but it has significant consequences and applications. To define a monoid, you need:

• A set of objects.
• A binary operation.

The operation must:

• Be associative.
• Have a unit value.

Being associative means that, given the elements a, b and c and the operation op, the following property must always be true:

``````a op (b op c) = (a op b) op c
``````

The unit for the operation op is a particular element of the set that, whatever the element a is, makes the following equivalences always true:

``````a op unit = a
unit op a = a
``````

Monoids are everywhere, and providing a familiar example is simple. A very important monoid is:

• The set of integer numbers.

``````a + (b + c) = (a + b) + c
``````

The particular integer value that’s the unit for the addition is, of course, 0. This is because:

``````a + 0 = a
0 + a = a
``````

Addition is a good example but can also be misleading. For instance, addition is commutative, which means that:

``````a + b = b + a
``````

Instead, a monoid doesn’t need to be commutative.

Exercise 12.1: Can you find an example of a monoid whose operation isn’t commutative? Remember, you can find the solutions for all exercises and challenges in Appendix K.

Exercise 12.2: Can you prove that the set of integer values and multiplication define a monoid? In this case, what would the unit element be?

From the previous definition, you understand that you can have many different types of monoids using the same set but a different operation or vice versa. But then, how would you define the typeclass `Monoid` in code?

### The Monoid<T> typeclass

If you use the set analogy for types, you can think of a monoid for a type `T` as:

``````interface Monoid<T> { // 1
val unit: T // 2
val combine: (T, T) -> T // 3
}
``````
``````typealias Fun2<A, B, C> = (A, B) -> C

fun <A, B, C> Fun2<A, B, C>.curry(): (A) -> (B) -> C = { a: A ->
{ b: B ->
this(a, b)
}
}
``````
``````interface Monoid<T> {
val unit: T
val combine: (T) -> (T) -> T // HERE
}
``````
``````public interface Monoid<T> {
val unit: T
val combine: T.(T) -> T // HERE
}
``````
``````object MonoidIntAdd : Monoid<Int> { // 1
override val unit: Int
get() = 0 // 2
override val combine: Int.(Int) -> Int // 3
get() = Int::plus // 4
}
``````

## Property-based testing

In the first part of this chapter, you learned that typeclasses are defined using particular rules often called laws. You already met them in Chapter 11, “Functors”. You also created some very simple `Monoid<T>` implementations that you’re confident follow the monoid rules, but how can you be sure of that? Answering this question is an ideal opportunity to introduce a technique called property-based testing.

``````fun sum(a: Int, b: Int): Int = a + b
``````
``````class PropertyTestTest {

@Test
fun `sum test using predefined values`() {
Truth.assertThat(sum(2, 3)).isEqualTo(5)
Truth.assertThat(sum(2, 5)).isEqualTo(7)
Truth.assertThat(sum(-2, 5)).isEqualTo(3)
}
}
``````

``````  @Test
fun `sum test using random values`() {
val firstValue = Random.nextInt() // 1
val secondValue = Random.nextInt() // 2
val expectedValue = firstValue + secondValue // 3
Truth.assertThat(sum(firstValue, secondValue)) // 4
.isEqualTo(expectedValue)
}
``````

``````  @Test
fun `sum test using random values 100 times`() {
100.times {
val firstValue = Random.nextInt()
val secondValue = Random.nextInt()
val expectedValue = firstValue + secondValue
Truth.assertThat(sum(firstValue, secondValue))
.isEqualTo(expectedValue) o
}
}
``````

``````  @Test
fun `sum test using random values`() {
val firstValue = Random.nextInt()
val secondValue = Random.nextInt()
val expectedValue = firstValue + secondValue // HERE
Truth.assertThat(sum(firstValue, secondValue))
.isEqualTo(expectedValue)
}
``````

### An example of property-based testing

In the previous section, you saw that implementing good testing isn’t obvious, even for a basic function like `sum`. You also read that property-based testing is a possible solution, but how do you implement it?

``````a + b = b + a
``````
``````  @Test
fun `test sum is commutative`() {
100.times {
val firstValue = Random.nextInt() // 1
val secondValue = Random.nextInt() // 1
val result1 = sum(firstValue, secondValue) // 2
val result2 = sum(secondValue, firstValue) // 3
Truth.assertThat(result1).isEqualTo(result2) // 4
}
}
``````
``````fun sum(a: Int, b: Int): Int = a * b
``````
``````  @Test
fun `test addition is not multiplication`() {
100.times {
val randomValue = Random.nextInt() // 1
val result1 = sum(sum(randomValue, 1), 1) // 2
val result2 = sum(randomValue, 2) // 3
Truth.assertThat(result1).isEqualTo(result2) // 4
}
}
``````

``````fun sum(a: Int, b: Int): Int = a + b
``````
``````class PropertyTestTest {
// ...
@Test
fun `test sum is symmetric`() {
100.times {
val firstValue = Random.nextInt()
val secondValue = Random.nextInt()
val result1 = sum(firstValue, secondValue)
val result2 = sum(secondValue, firstValue)
Truth.assertThat(result1).isEqualTo(result2)
}
}

@Test
fun `test addition is not multiplication`() {
100.times {
val randomValue = Random.nextInt()
val result1 = sum(sum(randomValue, 1), 1)
val result2 = sum(randomValue, 2)
Truth.assertThat(result1).isEqualTo(result2)
}
}
}
``````

``````fun sum(a: Int, b: Int): Int = 0
``````
``````  @Test
fun `test using unit value for addition`() {
100.times {
val randomValue = Random.nextInt() // 1
val result1 = sum(randomValue, 0) // 2
val expected = randomValue // 3
Truth.assertThat(result1).isEqualTo(expected) // 4
}
}
``````

``````fun sum(a: Int, b: Int): Int = a + b
``````

### Generalizing property-based testing

In the previous section, you used the property-based technique to test, with acceptable confidence, the implementation of a simple `sum` function. Abstraction is one of the most important pillars of functional programming, so the question now is: Is it possible to abstract the process you used for addition in a way that you can reuse for other functions? Of course you can!

``````fun interface Generator<T> { // 1
fun generate(n: Int): List<T> // 2
}
``````
``````object IntGenerator : Generator<Int> {
override fun generate(n: Int): List<Int> = List(n) {
Random.nextInt()
}
}
``````
``````interface Property<T> { // 1
operator fun invoke( // 2
gen: Generator<T>, // 3
fn: (List<T>) -> T // 4
): Boolean // 5
}
``````
``````class CommutativeProperty<T> : Property<T> { // 1
override fun invoke(
gen: Generator<T>,
fn: (List<T>) -> T
): Boolean {
val values = gen.generate(2)  // 2
val res1 = fn(listOf(values[0], values[1])) // 3
val res2 = fn(listOf(values[1], values[0])) // 4
return res1 == res2 // 5
}
}
``````
``````class AssociativeProperty<T> : Property<T> {
override fun invoke(
gen: Generator<T>,
fn: (List<T>) -> T
): Boolean {
val values = gen.generate(3) // 1
val res1 = fn(
listOf(fn(listOf(values[0], values[1])), values[2]))  // 2
val res2 = fn(
listOf(values[0], fn(listOf(values[1], values[2])))) // 3
return res1 == res2 // 4
}
}
``````
``````class IdentityProperty<T>(
private val unit: T // 1
) : Property<T> {
override fun invoke(
gen: Generator<T>,
fn: (List<T>) -> T
): Boolean {
val randomValue = gen.generate(1)[0] // 2
val res1 = fn(listOf(randomValue unit)) // 3
val res2 = fn(listOf(unit, randomValue)) // 4
return res1 == randomValue && res2 == randomValue // 5
}
}
``````
``````infix fun <T> Property<T>.and(
rightProp: Property<T>
): Property<T> = object : Property<T> { // 1
override fun invoke( // 2
gen: Generator<T>,
fn: (List<T>) -> T
): Boolean =
this@and(gen, fn) && rightProp(gen, fn) // 3
}
``````
``````  @Test
fun `Property-based test for sum`() {
100.times {
CommutativeProperty<Int>() and // 1
AssociativeProperty() and
IdentityProperty(0)
val evaluation = additionProp(IntGenerator) { // 2
sum(it[0], it[1])
}
Truth.assertThat(evaluation).isTrue() // 3
}
}
``````

### Property-based testing and monoids

Property-based testing comprises much more than what you’ve learned here. Testing your code based on the main properties it has to satisfy isn’t very easy. Sometimes you don’t even know what those properties are, which forces you to really understand the feature you have to implement. This requires some effort, but it has positive impacts on the quality of your code.

``````object MonoidStringConcat : Monoid<String> {
override val unit: String
get() = ""
override val combine: String.(String) -> String
get() = String::plus
}
``````
``````class StringGenerator(
private val minLength: Int = 0,
private val maxLength: Int = 10
) : Generator<String> {
val chars = "abcdefghijklmnopqrstuvwxyz" +
"ABCDEFGHIJKLMNOPQRSTUVWXYZ" +
"1234567890!±§!@£\$%^&*()_+-="
override fun generate(n: Int): List<String> = List(n) {
val length = Random.nextInt(minLength, maxLength)
val currentString = StringBuilder()
(1..length).forEach {
currentString.append(
chars[Random.nextInt(0, chars.length)])
}
currentString.toString()
}
}
``````

``````class StringMonoidTest {

@Test
fun `test string concat using generators`() {
100.times {
val stringConcatProp =
AssociativeProperty<String>() and // 1
IdentityProperty("") // 2
val evaluation = stringConcatProp(StringGenerator()) { // 3
MonoidStringConcat.combine(it[0], it[1]) // 4
}
Truth.assertThat(evaluation).isTrue() // 5
}
}
}
``````

## Monoids and foldable types

In Chapter 9, “Data Types”, you implemented two of the most important functions a data type usually provides: `fold` and `foldRight`. These are very helpful functions you can use, for instance, to calculate the sum of the values in a `List<Int>`, like the following in Foldable.kt:

``````fun List<Int>.sumList() = fold(0) { a, b -> a + b }
``````
``````fun String.reverseString() = foldRight("") { char, str -> str + char }
``````
``````fun main() {
listOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10).sumList() pipe ::println
"supercalifragilisticexpialidocious".reverseString() pipe ::println
}
``````
``````55
suoicodilaipxecitsiligarfilacrepus
``````
``````typealias Foldable<T> = Iterable<T>
``````
``````fun <T> Foldable<T>.fold(monoid: Monoid<T>): T =
fold(monoid.unit, monoid.combine)
``````
``````fun List<Int>.sumList() = fold(MonoidIntAdd)
``````
``````fun <A, B, C> (A.(B) -> C).swap(): (B.(A) -> C) = { a: A -> // 1
a.this@swap(this)
}

fun <T> Monoid<T>.commutate(): Monoid<T> = object : Monoid<T> { // 2
override val unit: T
get() = this@commutate.unit
override val combine: T.(T) -> T
get() = this@commutate.combine.swap()
}
``````
``````fun CharSequence.fold(monoid: Monoid<String>): CharSequence = // 1
this.fold(monoid.unit) { a, b ->
monoid.combine(a, "\$b") // 2
}
``````
``````fun String.reverseString() = fold(MonoidStringConcat)
``````
``````fun main() {
listOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10).sumList() pipe ::println
"supercalifragilisticexpialidocious".reverseString() pipe ::println
}
``````
``````55
supercalifragilisticexpialidocious // WRONG
``````
``````fun String.reverseString() =
fold(MonoidStringConcat.commutate())
``````
``````55
suoicodilaipxecitsiligarfilacrepus // OK!
``````

## Monoids and category theory

Now that you’ve learned what a monoid is from a practical point of view, it’s useful to see what it actually is in the context of category theory. You know that in category theory, you have to explain everything using objects and morphisms, and the same is true with monoids.

## The semigroup typeclass

Most of this chapter is dedicated to the monoid typeclass, which you know is defined as a set of values, or type, along with:

``````public interface Monoid<T> {
val unit: T
val combine: T.(T) -> T
}
``````
``````fun <T> mergeAndCombine(
listA: List<T>,
listB: List<T>,
combine: (T, T) -> T
): List<T> {
var i = 0
var j = 0
val result = mutableListOf<T>()
while (i < listA.size || j < listB.size) {
val first = if (i < listA.size) listA[i] else null
val second = if (j < listB.size) listB[i] else null
if (first != null && second != null) {
} else if (first != null) {
} else if (second != null) {
}
i++
j++
}
return result
}
``````
``````public interface Semigroup<T> {
val combine: T.(T) -> T
}
``````
``````public interface Monoid<T> : Semigroup<T> {
val unit: T
}
``````
``````fun <T> mergeAndCombine(
listA: List<T>,
listB: List<T>,
semigroup: Semigroup<T>
): List<T> { // 1
var i = 0
var j = 0
val result = mutableListOf<T>()
while (i < listA.size || j < listB.size) {
val first = if (i < listA.size) listA[i] else null
val second = if (j < listB.size) listB[j] else null
if (first != null && second != null) {
} else if (first != null) {
} else if (second != null) {
}
i++
j++
}
return result
}
``````
``````object SemigroupIntMult : Semigroup<Int> {
override val combine: Int.(Int) -> Int
get() = Int::times
}

fun main() {
val listA = listOf(1, 2, 3, 4, 5, 6)
val listB = listOf(3, 5, 6)
mergeAndCombine(listA, listB, SemigroupIntMult) pipe ::println
}
``````
``````[3, 10, 18, 4, 5, 6]
``````

## Key points

• A monoid is a set of values with an associative binary operation and a unit element.
• A monoid doesn’t need to be commutative.
• The existence of the associative binary operation and the unit element are the monoid laws.
• Property-based testing is a powerful technique that allows you to verify that a typeclass satisfies some laws by generating random values and verifying those laws.
• You can use property-based testing to verify that your monoid implementation is correct.
• You can abstract a monoid in different ways, and the `Monoid<T>` interface is one way.
• Monoids work very well with `Foldable` data types, which provide implementations for `fold` and `foldRight`.
• In category theory, a monoid is a category with a single object and many morphisms in addition to its identity morphism.
• A semigroup is a typeclass defining a binary associative function without the need for a unit element.
• A monoid is a semigroup with a unit element.

## Where to go from here?

Congratulations! You’ve completed these very important and fun chapters about monoids. Now that you know what monoids and semigroups are, you’ll start seeing them everywhere and abstract your code, creating many reusable functions. You’re now ready for one of the most exciting concepts: monads!

Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.