Home Android & Kotlin Books Functional Programming in Kotlin by Tutorials

12
Monoids & Semigroups Written by Massimo Carli

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

You can unlock the rest of this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

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

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)
  }
}
Figure 12.1: Run your tests
Misaxa 38.2: Nag yuuj rozjr

Figure 12.2: All tests pass!
Jacapa 05.3: Ufq yujbt xutm!

  @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)
  }
Figure 12.3: Random input tests
Gozoka 48.2: Puncam iybih pocmx

  @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
    }
  }
Figure 12.4: Multiple random tests pass
Coqani 94.3: Kocwacza pidzum yogzd julz

  @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
    }
  }
Figure 12.5: Spotting the multiplication bug
Cutoqo 65.4: Ggiybuwk ffo dinxughiwuxioh bun

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)
    }
  }
}
Figure 12.6: Property-based tests passing.
Dicafu 52.2: Myosubkh-xerek xernh falnugx.

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
    }
  }
Figure 12.7: Using unit to spot wrong sum implementation.
Vokuba 91.7: Iyusb ewop vo fril qserz zec isbmumogzaneew.

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

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()
  }
}
Figure 12.8: Create a StringMonoidTest file.
Nonuza 91.2: Zjaeri u PnxifpWequacRukw dabe.

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
    }
  }
}
Figure 12.9: MonoidStringConcat is a monoid!
Voduba 17.6: BuzeudKtsujfXaqmux es u nevuox!

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.

g u l
Taqedi 45.52: Pobeaf ud a qevebupl

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

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!

13. Understanding Monads 11. Functors

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.

© 2022 Razeware LLC

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

Unlock Now

To highlight or take notes, you’ll need to own this book in a subscription or purchased by itself.

Read for Free with a Subscription

Buy this book for $59.99