12. Monoids & Semigroups

Written by Massimo Carli

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.
• Addition.

Addition is associative because:

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:

• A commutative combine operation of type (T, T) -> T.
• A unit element of type T.

Note: It’s important to understand that you could do this in multiple ways. The method you’ll implement here is just one possibility.

Open Monoid.kt in this chapter’s material, and add the following code:

interface Monoid<T> { // 1
  val unit: T // 2
  val combine: (T, T) -> T // 3
}

In this code, you define:

1. Monoid<T> as an interface with a generic type parameter T.
2. unit as the unit value of type T.
3. combine as a function of type (T, T) -> T.

The previous definition has a few significant things to note that have consequences on some implementation details. You might have the following questions in particular:

• combine has two input parameters of type T and returns another value of the same type T. You learned that composition is easier with functions with a single parameter. How, then, can you improve the Monoid<T> definition?
• Monoid<T> is an interface that a type might implement to provide unit and combine implementations. But you also know that you might have two monoids for the same set of values. For instance, multiplication and addition are both monoids on Int. How could you then provide a different monoid implementation for the same type T?
• At compile time, there’s no way to force the validity of the property about associativity and unit. This depends on the combine implementation. What can you do, then, to have confidence your implementation will work properly?

In Chapter 8, “Composition”, you implemented the curry function in the way you find in Definitions.kt:

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)
  }
}

curry allows you to represent a function of two input parameters of type (A, B) -> C as a higher-order function of a single parameter that returns another function of type (A) -> (B) -> C. This suggests that you can replace the previous Monoid<T> definition with the following in the same Monoid.kt:

interface Monoid<T> {
  val unit: T
  val combine: (T) -> (T) -> T // HERE
}

As you can see, now combine has a single input parameter of type T and returns a function of type (T) -> T. But you can do even better by replacing the previous definition with the following:

public interface Monoid<T> {
  val unit: T
  val combine: T.(T) -> T // HERE
}

Creating a single Monoid<T> implementation is relatively easy. Before implementing some, it’s important to emphasize that it’s not correct to say that some type A is a monoid. A monoid needs a type, which is essentially a set of values. It also needs an associative operation with unit. This means you can’t just make your class A to implement Monoid<A> because you need something more.

Previously, you used the Int type. Depending on if you’re using addition or multiplication, you can define two different monoids. Open Monoid.kt and add the following code:

object MonoidIntAdd : Monoid<Int> { // 1
  override val unit: Int
    get() = 0 // 2
  override val combine: Int.(Int) -> Int // 3
    get() = Int::plus // 4
}

In this code, you define:

1. MonoidIntAdd as an object implementing the Monoid<Int> interface. It represents a monoid for Int and addition. You use an object because you don’t have to handle any states. unit is just a value, and combine is a pure function.
2. 0, which is the unit value for addition.
3. combine as a function of type Int.(Int) -> Int which, as you’ll see very soon, might have some advantages in Kotlin. If it’s more familiar, you might also use the previous definition of Monoid<T> with combine of type (T) -> (T) -> T.
4. combine using the Int::plus definition, which is of type Int.(Int) -> Int. This is actually the main reason for defining combine as a function of type T.(T) -> T.

Exercise 12.3: How would you implement the monoid MonoidIntMult for Int and multiplication? Then, check out the solution in Appendix K.

Exercise 12.4: How would you implement the monoid MonoidStringConcat for String and String concatenation?

As you see, implementing a monoid is relatively simple, and you’ll implement others very soon. But how can you be sure that your implementation is actually a monoid?

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.

As you know, testing is one of the most challenging parts of the development process of any piece of software. To understand why, just look at the code in PropertyTest.kt:

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

The question now is: How can you test this code? sum is a basic function that adds two values you pass as input. The first approach is to implement some unit tests. You can implement some tests like the following. Add this code to PropertyTestTest.kt:

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)
  }
}

Here, you’re testing that 2 + 3 = 5, 2 + 5 = 7 and -2 + 5 = 3.

Run the tests by clicking the icon in Figure 12.1, and you’ll get what’s in Figure 12.2, proving that all the tests pass.

But you’re only testing some of the possible values! What about all the other possible inputs? You could add more cases, but how many tests do you actually need to implement to be sure your function is correct?

In this specific case, sum accepts two parameters of type Int. This means the possible combinations in input are the number of elements in the Cartesian product Int × Int, which has 4,294,967,295 × 4,294,967,295 elements! Of course, you can’t implement all those tests, so you need a smarter solution. What about generating some random values and checking whether sum works correctly?

In the same PropertyTestTest.kt, add the following code:

  @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)
  }

In this code, you:

1. Use Random.nextInt to get a random Int for the first parameter you store in firstValue.
2. Do the same for the second parameter, which you put in secondValue.
3. Calculate the expected value using +, which you store in expectedValue.
4. Check that the value you get from sum is what you expected.

Run the test as in Figure 12.3, and make it pass again.

If you run it once, you might’ve just been lucky. A possible option is to run the test more times. Add the following code in PropertyTestTest.kt, and run it again:

  @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
    }
  }

In this case, everything also seems fine, like in Figure 12.4:

This seems fine, but it’s not quite so simple. Can you see why?

The answer is highlighted in the following code:

  @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)
  }

To test sum, you’re re-implementing the same feature! How can you test that sum is correct if you compare its result with a value you get by doing exactly the same thing? Of course, it passes — but they might both be wrong.

So the big problem now is: How would you test sum without:

• Re-implementing the same operation in tests?
• Using specific examples?

The answer is property-based testing.

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?

The first step is to think about how sum is different from other operations. For instance, you previously learned that addition is commutative, meaning that for any a and b:

a + b = b + a

You know that this isn’t true for all operations. Subtraction, for example, is not commutative. You can then add the following test to PropertyTestTest.kt:

  @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
    }
  }

In this code, you:

1. Get two random values for firstValue and secondValue.
2. Invoke sum using firstValue and secondValue as first and second parameters.
3. Invoke sum with the same parameter values but in a different order.
4. Check that the results you got in the two cases are the same.

If you run this test, you’ll see it passes. This is an improvement over the previous solutions, but unfortunately, it’s not enough. You can easily test this by replacing the + with * in PropertyTest.kt:

fun sum(a: Int, b: Int): Int = a * b

The previous test still passes because, like addition, multiplication is also commutative. You don’t just give up, then, wondering what the difference is between addition and multiplication.

There are many, but a possible solution is that adding 1 twice to any value a is the equivalent of adding 2 to the same a. This isn’t true with multiplication. Multiplying by 1 twice isn’t equivalent to multiplying by 2 once. To spot the multiplication you introduced earlier, add the following test to PropertyTestTest.kt:

  @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
    }
  }

In this case, you:

1. Get a random Int value you put in randomValue.

2. Invoke sum, adding 1 to randomValue and then again to add 1 to the previous result.

3. Use sum, adding 2 to randomValue.

4. Check if the values you got are the same.

Run this test using the bugged sum implementation, and you’ll get what’s in Figure 12.5:

You can fix the problem in the sum implementation and restore this in PropertyTest.kt:

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

Now, comment out all the tests, keeping just the following, which you implemented as property-based tests:

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)
    }
  }
}

Run them, and you’ll see them all passing, like in Figure 12.6:

Everything looks fine, but you still need to fix something. Just replace the sum implementation with the following in PropertyTest.kt:

fun sum(a: Int, b: Int): Int = 0

Because sum always returns the same value, all the previous tests pass! Of course, this isn’t good. The output must be a function of the input. You don’t want to fail in the very first tests you wrote when you knew exactly what values to pass as input, and you had to re-implement the same sum in the tests.

A possible solution to this is the use of a special value that allows you to somehow predict the result without knowing all the input values. To understand what this value is, add the following test to PropertyTestTest.kt:

  @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
    }
  }

In this test, you:

1. Store a random Int value in randomValue.
2. Invoke sum, passing randomValue as the first parameter and 0 as the second.
3. Use the same randomValue as the expected result when adding 0.
4. Check if the result is what you’re expecting.

When you run the previous test with the last bugged sum implementation, you’ll see the test fails, like in Figure 12.7:

Resume the correct sum implementation in PropertyTest.kt like this:

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

All the tests now pass!

It’s crucial now to understand what you actually did. Instead of implementing unit tests using specific input values, you focused on the main properties of addition and proved that they’re valid regardless of the input values. This is the idea behind the concept of property-based testing.

You might wonder if this idea can somehow be abstracted and generalized. The answer is yes!

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!

Note: Some frameworks, like Kotest, allow you to use property-based testing in your code in a more robust and complete way. In this case, you’ll just implement some of the main abstractions as an example of the technique. It’s up to you to decide if you want to use Kotest, another framework or implement your own.

As you learned above, property-based testing uses some randomly generated values you can represent using the Generator<T> abstraction. In PropertyTest.kt, add the following code:

fun interface Generator<T> { // 1
  fun generate(n: Int): List<T> // 2
}

Here, you define:

1. The Generator<T> abstraction as a generic functional interface. Generator<T> is supposed to generate random values of type T.
2. generate as a function accepting an Int input parameter that defines the number of random elements you need to generate. The result value is List<T>, and it’s supposed to be a list of length n. This allows you to handle any number of random values.

In the same file, add the following implementation for Int values:

object IntGenerator : Generator<Int> {
  override fun generate(n: Int): List<Int> = List(n) {
    Random.nextInt()
  }
}

This is self-explanatory and simply returns a List<Int> containing n random Int values.

Now, you need a way to represent properties like commutativity, associativity and so on. A simple way to do this is adding the following definition in PropertyTest.kt:

interface Property<T> { // 1
  operator fun invoke( // 2
    gen: Generator<T>, // 3
    fn: (List<T>) -> T // 4
  ): Boolean // 5
}

In this code, you:

1. Define Property<T> as a generic interface in the type parameter T.

2. Declare invoke as the operator to define in every Property<T> implementation. This allows you to check the property directly using ().

3. Pass the Generator<T> as invoke’s first parameter. Each Property<T> is responsible for using the generator to get all the values it needs.

4. Need a function of the generated input values List<T> that returns another value of type T. The return type could be different in case you’d need to test more complex properties.

5. Require Boolean as the return type for invoke. This tells you whether the property is verified. Again, you’re keeping things simple, but in Chapter 14, “Error Handling With Functional Programming”, you’ll see how to get more information from a failing property verification using Either<A, B> or Kotlin’s built-in Result<T>.

As a first example of using Property<T>, it’s useful to define the implementation for the commutativity property. In PropertyTest.kt, add the following code:

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
  }
}

This is some very interesting code, where you:

1. Create CommutativeProperty<T> as a Property<T> implementation. Note how CommutativeProperty<T> is still generic in the type T.
2. Invoke generate on the Generator<T> you get as invoke’s input parameter to get 2 values you need to prove commutativity.
3. Invoke the function fn you get as invoke’s input parameter, passing the random values in the same order you got from Generator<T>.
4. Do the same, but using the random values you got from Generator<T> in a different order.
5. Check if the two results are the same. This is required to prove the commutative property.

Now, in a very similar way, you can implement Property<T> for associativity. In PropertyTest.kt, add the following code:

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
  }
}

In this case, you:

1. Need 3 values of type T.
2. Invoke the function fn you get as invoke‘s input parameter like op(op(a, b), c), assuming a, b and c are the 3 random values, and op is the operation you’re testing.
3. Do the same, but like op(a, op(b, c)).
4. Verify that the results in the two cases are the same.

Finally, you can implement Property<T> for the identity property by adding the following code in PropertyTest.kt:

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
  }
}

In this case, the implementation is slightly different. Here, you:

1. Need the unit element, which depends on the specific type T and operation.
2. Generate a single randomValue of type T.
3. Invoke fn in the form op(randomValue, unit).
4. Do the same by invoking fn in the form op(unit, randomValue).
5. Verify that unit is actually the unit for the given operation you invoke through fn.

It’s finally time to use these properties in a property-based test. But first, add the following utility function to PropertyTest.kt:

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
}

This utility function simplifies the verification of multiple properties, putting them all in and. Here, you:

1. Define and as an infix extension function of Property<T>, accepting another Property<T> in input. The return type is still a Property<T>, which is the logical AND with the receiver.
2. Create the Property<T> implementation to return using the receiver and the Property<T> you get as input.
3. Simply invoke the receiver Property<T> and the rightProp you get as an input parameter. This means that the returning Property<T> will evaluate to true if and only if both the receiver property and the one you pass as rightProp evaluate to true.

Now, open PropertyTestTest.kt, and add the following test:

  @Test
  fun `Property-based test for sum`() {
    100.times {
      val additionProp =
        CommutativeProperty<Int>() and // 1
            AssociativeProperty() and
            IdentityProperty(0)
      val evaluation = additionProp(IntGenerator) { // 2
        sum(it[0], it[1])
      }
      Truth.assertThat(evaluation).isTrue() // 3
    }
  }

In this test, you:

1. Create instances of CommutativeProperty<Int>, AssociativeProperty<Int> and IdentityProperty. Using the and utility function, you compose them into a single Property<Int> implementation you store in additionProp.
2. Evaluate additionProp, passing a reference to the IntGenerator and a lambda containing the actual invocation of sum, passing the values you get from the Generator<Int> in a List<Int>. You store the result in evaluation.
3. Confirm that all the properties are verified by testing the value of evaluation, which must be true.

Run the previous test, and you’ll see that all the tests pass! You can also verify that the test fails if you change the sum implementation like you did above.

Exercise 12.5: In the previous section, you proved that addition is different from multiplication using op(op(a), 1) and op(a, 2). The two expressions are equal for any Int a if op is addition, but the same isn’t true if op is multiplication. Can you implement a Property<Int> implementation for this rule and use it to create a new test?

You can find the solution in Appendix K and the challenge project for this chapter.

A crucial aspect of what you just did is that the properties you’ve defined for sum aren’t just properties you use for testing. They’re actually the specification for sum or addition in general. Every operation that satisfies CommutativeProperty, AssociativeProperty and IdentityProperty is addition.

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.

In this chapter, you’ve learned what property-based testing is. You also implemented a very small framework with the goal of having a way to verify if your monoid implementations work. Property-based testing is useful with monoid laws but is also one of the main techniques for verifying any typeclass law.

To prove this, you’ll now implement a Monoid<String> implementation for the String type and the String concatenation operation. Then, you’ll prove it’s actually a monoid.

Note: Spoiler alert! You should’ve already implemented a Monoid<String> for the String type and String concatenation operation as an exercise. If you haven’t, please review Exercise 12.4 before proceeding.

You know that a Monoid<T> consists of a type T, which represents a set of values and a binary operation that’s associative and has a unit. A possible implementation for String with String concatenation, then, is the following. Add this to Monoid.kt if not already present in your exercise solution:

object MonoidStringConcat : Monoid<String> {
  override val unit: String
    get() = ""
  override val combine: String.(String) -> String
    get() = String::plus
}

To implement a property-based test for this implementation, you need a Generator<String>. A possible implementation is the following, which you can add to PropertyTest.kt:

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()
  }
}

The next step is providing Property<T> implementation for:

• Associativity
• Identity

Hey, you already have them! In the test build type, create a new file named StringMonoidTest.kt, like in Figure 12.8:

Now, add the following code:

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
    }
  }
}

In this code, you:

1. Use an AssociativeProperty<String> instance.
2. Create an instance of IdentityProperty<String> using the empty String as a unit.
3. Combine the two properties in stringConcatProp and invoke it, passing an instance of StringGenerator.
4. Use MonoidStringConcat.combine as the operation to test.
5. Verify that evaluation always evaluates to true.

Run the test, and you’ll get what’s in Figure 12.9:

Great! You managed to implement a monoid and test its properties using property-based testing.

But why are monoids so important? Where do you actually use them?

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 }

As an example of foldRight, you implemented the function reverseString like this:

fun String.reverseString() = foldRight("") { char, str -> str + char }

Note: You called these functions sumList and reverseString so they wouldn’t conflict with the existing sum and reverse.

To test these functions, just run the following code:

fun main() {
  listOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10).sumList() pipe ::println
  "supercalifragilisticexpialidocious".reverseString() pipe ::println
}

Getting the following output:

55
suoicodilaipxecitsiligarfilacrepus

As you see, fold and foldRight both need an initial value and a combine function that’s reminiscent of the concept of Monoid<T>. It’s crucial to note how a Monoid<T> has a single type parameter T, so the combine has type (T, T) -> T. This makes fold and foldRight basically the same.

For this reason, it’s often useful to create an abstraction for any object with a fold function like this, which you should add in the same Foldable.kt file:

typealias Foldable<T> = Iterable<T>

Kotlin defines fold as an extension function for Iterable<T>, so you can create a Foldable<T> typealias of it and then define the following function:

fun <T> Foldable<T>.fold(monoid: Monoid<T>): T =
  fold(monoid.unit, monoid.combine)

Once your data type implements Iterable<T>, it also has the fold function accepting a Monoid<T> as an input parameter.

For example, you can implement the previous sumList function like this:

fun List<Int>.sumList() = fold(MonoidIntAdd)

How can you implement the reverseString using a Monoid<String> instead? You learned that combine in a monoid doesn’t need to be commutative. It’d be useful, then, to implement a function that commutates a Monoid<T> like the following you can write in Foldable.kt:

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()
}

This isn’t obvious code. Here, you implement:

1. swap as a function that converts a function of type A.(B)->C in a function of type B.(A)->C, basically swapping the receivers of types A and B.
2. commutate as an extension function for Monoid<T> that swaps the input parameter for the combine function of the Monoid<T> you use as a receiver. The unit is the same, while the combine is the one you get invoking swap in the combine for the receiver.

A String doesn’t implement Iterable<T>, so you need to provide a specific fold overload for CharSequence you implement like this:

fun CharSequence.fold(monoid: Monoid<String>): CharSequence = // 1
  this.fold(monoid.unit) { a, b ->
    monoid.combine(a, "$b") // 2
  }

The problem here is that you have to:

1. Use a Monoid<String>.
2. Convert the Char you get as an input parameter for the fold lambda in a String.

Now, you can implement reverseString like this:

fun String.reverseString() = fold(MonoidStringConcat)

When you run the following code:

fun main() {
  listOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10).sumList() pipe ::println
  "supercalifragilisticexpialidocious".reverseString() pipe ::println
}

You get:

55
supercalifragilisticexpialidocious // WRONG

Here, you see that the reverseString doesn’t do its job. But you can fix this easily with the following implementation that uses commutate to invert the combine function of the MonoidStringConcat you pass as an input parameter:

fun String.reverseString() =
  fold(MonoidStringConcat.commutate())

Run main again, and now you’ll get what you expect:

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.

Look at Figure 12.10:

This is a category with a single object, m. Of course, because it’s a category, you have an identity im, but you also have many other morphisms from m to itself. You also have composition, so you can compose all those morphisms, getting other morphisms. Compared to other categories, in this case, all the morphisms are composable because they all start and end at m.

The uniqueness of the object in this category is the characteristic that gives it the name monoid.

You already learned that a monoid needs a set of values and a binary associative operation along with a special value called a unit. How is this definition related to the one you saw in category theory?

Look at Figure 12.10, and you see that the category with one object, m, has only one hom-set, M(m, m). Remember, the hom-set is the set of all morphisms between objects that, in this case, are equal to m, which is the only object of the category. Because that’s a category, you say that for every couple of morphisms in M(m, m), another morphism exists: the composition of the two that you can call, for instance, multiplication. The composition is also part of M(m, m). This is equivalent to the combine you met in the first — and more familiar — definition of monoid.

In M(m, m), you also have a special morphism, called unit, that you compose with any other morphisms m, getting m itself. This is true because every category must have the identity morphism.

Finally, composition is associative, as is the composition of any triplet of morphisms in the hom-set M(m, m).

It’s surprising how all the concepts you’ve seen in the previous examples can be explained using objects and morphisms in category theory.

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:

• A binary associative operation called combine.
• A special element called unit.

You represented a monoid using the following abstraction:

public interface Monoid<T> {
  val unit: T
  val combine: T.(T) -> T
}

Looking at Monoid<T>, you might ask if the unit is always necessary, and the answer is no. In the case of fold, you used the unit as a possible initial value. What if you don’t need it?

An example is the implementation of a function that merges two List<T>s into one. In Semigroup.kt, add the following code:

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) {
      result.add(combine(first, second))
    } else if (first != null) {
      result.add(first)
    } else if (second != null) {
      result.add(second)
    }
    i++
    j++
  }
  return result
}

The implementation for mergeAndCombine has some controlled mutability. It allows you to use a combine function when creating a List<T> from two other List<T>s, which might have different sizes. This is an example of a function that doesn’t need a unit.

In this case, the typeclass that defines a set of values and an associative binary operation is a semigroup you can represent like this in Semigroup.kt:

public interface Semigroup<T> {
  val combine: T.(T) -> T
}

This allows you to update the definition of Monoid<T> in Monoid.kt like this:

public interface Monoid<T> : Semigroup<T> {
  val unit: T
}

A monoid is basically a semigroup with a unit. This allows you to implement mergeAndCombine like this:

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) {
      result.add(semigroup.combine(first, second)) // 2
    } else if (first != null) {
      result.add(first)
    } else if (second != null) {
      result.add(second)
    }
    i++
    j++
  }
  return result
}

This code is very similar to the previous one where you:

1. Pass a Semigroup<T> as a parameter.
2. Use the semigroup to combine the values in the two List<T>s.

As a simple test, add and run the following code:

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
}

Getting in output:

[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!