K. Appendix K: Chapter 12 Exercise Solutions

Written by Massimo Carli

Exercise 12.1

Can you find an example of a monoid whose operation isn’t commutative?

Exercise 12.1 solution

A typical example of a monoid in programming that isn’t commutative is:

• A set of Strings
• Concatenation

Concatenation is associative because:

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

But it’s commutative because:

a + b != b + a

You can easily verify this with the following code:

fun main() {
  val str1 = "Hello"
  val str2 = " World!"

  println(str1 + str2)
  println(str2 + str1)
}

When you run it, you get:

Hello World!
 World!Hello

What about the unit element? Of course, this is the empty String. To test this, just add and run the following code:

fun main() {
  // ...
  val unit = ""
  println(str1 + unit)
  println(unit + str1)
}

Getting as output:

Hello
Hello

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?

Exercise 12.2 solution

To prove that the set of integer values and multiplication form a monoid, you have to prove that:

• Multiplication is associative.
• There’s a unit element.

The first property is obvious because:

a * (b * c) = (a * b) * c

In this case, of course, the unit element is 1 because:

a * 1 = a
1 * a = a

You can get a better idea of this with some simple code:

fun main() {
  val a = 3
  val b = 7
  val c = 13
  val res1 = a * (b * c)
  val res2 = (a * b) * c

  println(res1)
  println(res2)

  val unit = 1
  val res3 = a * unit
  val res4 = unit * a

  println(res3)
  println(res4)
}

When you run the code above, you get:

273
273
3
3

Exercise 12.3

How would you implement the monoid MonoidIntMult for Int and multiplication?

Exercise 12.3 solution

The implementation of MonoidIntMult is simple because it’s similar to MonoidIntAdd, which you saw in the chapter. Follow that pattern, and you can implement MonoidIntMult like this:

object MonoidIntMult : Monoid<Int> { // 1
  override val unit: Int
    get() = 1 // 2
  override val combine: Int.(Int) -> Int
    get() = Int::times // 3
}

In this case, you define:

1. MonoidIntMult as an object implementing Monoid<Int>.
2. 1 as the unit for the multiplication.
3. combine using Int::times, which is of type Int.(Int) -> Int.

Exercise 12.4

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

Exercise 12.4 solution

As mentioned in the chapter, String concatenation is an example of a monoid with an operation that isn’t commutative. The implementation of MonoidStringConcat isn’t so different from MonoidIntAdd. A possible implementation is:

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

In this code, you define:

1. MonoidStringConcat as an object implementing Monoid<String>.
2. The empty String ”” as the unit for the String concatenation.
3. combine using String::plus, which is of type String.(String) -> String.

Exercise 12.5

In the chapter, you proved that addition is different from multiplication using op(op(a, 1), 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?

Exercise 12.5 solution

Following the pattern you used previously in the chapter, a possible implementation is the following:

class DoubleIncrementProperty : Property<Int> { // 1
  override fun invoke(
    gen: Generator<Int>,
    fn: (List<Int>) -> Int
  ): Boolean { // 2
    val randomValue = gen.generate(1)[0] // 3
    val res1 = fn(listOf(fn(listOf(randomValue, 1)), 1)) // 4
    val res2 = fn(listOf(randomValue, 2)) // 5
    return res1 == res2 // 6
  }
}

In this code, you:

1. Define DoubleIncrementProperty as a Property<Int> implementation.
2. Override invoke, using Int as a value for the type parameter T.
3. Use the Generator<Int> to get a random Int value.
4. Invoke fn, passing 1 as the second parameter and then using the result to invoke fn again.
5. Invoke fn, using 2 as the second parameter.
6. Verify the two results are equal.

A possible test with DoubleIncrementProperty is:

class PropertyTestTest {

  @Test
  fun `Exercise 5 solution`() {
    100.times {
      val additionProp =
        CommutativeProperty<Int>() and
            DoubleIncrementProperty() and
            IdentityProperty(0)
      val evaluation = additionProp(IntGenerator) {
        sum(it[0], it[1])
      }
      Truth.assertThat(evaluation).isTrue()
    }
  }
}

As you see, this is very similar to the test you implemented in the chapter using DoubleIncrementProperty in place of AssociativeProperty.