C. Appendix C: Chapter 3 Exercise & Challenge Solutions

Written by Massimo Carli

Exercise 3.1

Is inc a pure function?

var count = 0

fun inc(x: Int): Int = ++count + x

Exercise 3.1 solution

In this case, inc is not a pure function because it increments a global variable that’s part of the external world. Incrementing count is a side effect. The function also doesn’t return the same value with the same input value, as you can verify by executing the following code:

fun main() {
  println(inc(1))
  println(inc(1))
  println(inc(1))
  println(inc(1))
}

Here, you invoke inc with the same value in input, but you get different values in output, as you can see in the following logs:

2
3
4
5

Exercise 3.2

Is inc2 a pure function?

val count = 0

fun inc2(x: Int): Int = x + count + 1

Exercise 3.2 solution

This function isn’t so obvious, but it is pure because it always returns the same value in output for the same value in input. It uses count, which is part of the universe, but it’s a val, so it never changes. You can see count as part of the universe’s state but, because it’s immutable, it can’t be the consequence of any side effect, and it wont change the output.

Exercise 3.3

Is expr3:

val expr3 = 42
val (a1, a2) = expr3 to expr3

The same as the following?

val (a1, a2) = 42 to 42

Exercise 3.3 solution

Yes, in this case, expr2 is referentially transparent. You can prove this by running the following code without any exceptions:

fun main() {
  // Expr3 is referentially transparent, as you can see here
  val expr3 = { 42 }
  val (a1, a2) = expr3() to expr3()
  val expr3Eval = expr3()
  val (a1Eval, a2Eval) = expr3Eval to expr3Eval
  assertOrThrow("expr3 is not RT") {
    a1 == a1Eval && a2 == a2Eval
  }
}

Additionally, expr3 doesn’t have any side effects.

Exercise 3.4

Suppose you have the following code:

val CounterIterator = object : Iterator<Int> {

  private var count = 0

  override fun hasNext(): Boolean = true

  override fun next(): Int = count++
}

Is the following expression referentially transparent?

val expr4 = { CounterIterator.next() }

Exercise 3.4 solution

In this case, expr4 is not referentially transparent because the expression has a side effect.

You can prove this with the following code:

fun main() {
  // Expr4 is not referentially transparent, as you can see here
  val expr4 = { CounterIterator.next() }
  val (a1, a2) = expr4() to expr4()
  val expr4Eval = expr4()
  val (a1Eval, a2Eval) = expr4Eval to expr4Eval
  assertOrThrow("expr4 is not RT") {
    a1 == a1Eval && a2 == a2Eval
  }
}

Run the code, and you’ll get:

Exception in thread "main" java.lang.AssertionError: expr4 is not RT

Every time you evaluate expr4, you change the internal state of CounterIterator, which is part of the external universe and, for the same reason, you get a different output value.

Exercise 3.5

The Writer<A, B> data type you defined earlier is a very important concept in functional programming. If you use types as objects and the functions Writer<A, B> as morphisms, you get a very special category: the Kleisli category.

Can you prove that by using types as objects and Writer<A, B> as morphisms, you get a category?

typealias Writer<A, B> = (A) -> Pair<B, String>

Exercise 3.5 solution

In Chapter 2, “Function Fundamentals”, you learned that some objects with arrows between them, known as morphisms, form a category if all the following rules are true:

1. Composition
2. Associativity
3. Identity

In this exercise, you basically need to prove these rules for every type A and every function you represent as Writer<A, B>.

Proving composition

In this case, you have to prove that for every morphism f from the objects A to B, and g from B to C, there’s always a morphism g◦f from A to C, which is the composition of f with g.

You’ve actually already proved this composition in this chapter, Chapter 3, “Functional Programming Concepts”, with the following higher-order function:

infix fun <A, B, C> Writer<B, C>.after(
  w: Writer<A, B>
): Writer<A, C> = { a: A ->
  val (b, str) = w(a)
  val (c, str2) = this(b)
  c to "$str\n$str2\n"
}

As you did in Chapter 2, “Function Fundamentals”, you might also define compose with the following code:

infix fun <A, B, C> Writer<A, B>.compose(
  w: Writer<B, C>
): Writer<A, C> = w after this

With these two functions, you prove composition.

Proving associativity

To prove associativity for Writer<A, B>, you basically need to prove that:

(h after g) after f == h after (g after f)

Where:

f: Writer<A, B>
g: Writer<B, C>
h: Writer<C, D>

A possible way of doing this is applying the substitution model, but there’s a simpler way. Look at how composition works in the previous paragraph, and you’ll notice that associativity is true if it’s true for both the first and second properties of the resulting Pairs of Writers. For first, you’re applying the normal composition of functions Fun<A, B>. For second, you’re basically concatenating Strings. Because you already know that associativity is true for function Fun<A, B>, you basically need to also prove that String concatenation is associative. Given three Strings — str1, str2 and str3 — you can easily prove that:

(str1 + str2) + str3 == str1 + (str2 + str3)

This proves that, using the composition you defined in the previous paragraph, associativity for Writer<A, B> is also true.

Proving identity

In this case, you need to prove that for every type A, there’s always a morphism Writer<A, A> called identity id<A>, such that, for every f of type Writer<A, B> the following is true:

f after id == id after f == f

In this chapter, Chapter 3, “Functional Programming Concepts”, you met the function:

fun <A, B> Fun<A, B>.liftW(
  log: (A, B) -> String
): Writer<A, B> =
  { a: A ->
    val b = this(a)
    b to log(a, b)
  }

This function suggests what the identity might be. Just imagine starting from the identity for Fun<A, B>, which is:

fun <A> identity(a: A) = a

And apply liftW() using the empty String. What you’ll get is simply:

fun <A> id(): Writer<A, A> = { a -> a to "" }

Now, you need to prove that, whatever f of type Writer<A, B> is, the following rule is true:

f after id == id after f == f

To prove this, you need to start with the implementation of composition for Writer<A, B>. Then, use id<A> both as the receiver and as the parameter w.

infix fun <A, B, C> Writer<B, C>.after(
  w: Writer<A, B>
): Writer<A, C> = { a: A ->
  val (b, str) = w(a)
  val (c, str2) = this(b)
  c to "$str\n$str2\n"
}

If you want to reduce the first part, you start from:

f after id

You can write the definition of composition assuming that w is id<A>, getting:

fun <A, C> Writer<A, C>.after(): Writer<A, C> = { a: A ->
  val (b, str) = id<A>()(a)
  val (c, str2) = this(b)
  c to "$str\n$str2\n"
}

In the above:

str = ""
b = a
c = f(b) = f(a)
"$str\n$str2\n" = "$str2\n"

The result is then:

f(a) to "$str2\n"

Which is exactly what you’d get from f of type Writer<A, B>.

Now, you need to prove that you get the same result starting from:

id after f

Doing the same substitution, you’ll get:

infix fun <A, C> Writer<A, C>.after(
  w: Writer<A, C>
): Writer<A, C> = { a: A ->
  val (b, str) = w(a)
  val (c, str2) = id<C>()(b)
  c to "$str$str2\n"
}

Which becomes:

val (b, str) = f(a)
c = id(b) = b to "$str\n"

Which is, again, what you’d get from f.

f(a) to "$str\n"

Just note that in this case, the decoration of f is str and not str2, like in the previous case.

This proves that by using types as objects and Writer<A, B> as morphisms, you get a category that’s actually very important: the Kleisli category!

Challenge 1: Pure or impure?

Is inc3 a pure function? Why or why not?

var count = 0
fun inc3(x: Int): Int {
  val result = x + ++count + 1
  println("Res: $result") // WHAT IF YOU REMOVE THIS?
  --count
  return result
}

What if you remove the println() with the comment?

Challenge 1 solution

The answer, in this case, isn’t so obvious. Every time you invoke inc3, you calculate a result incrementing count, a global variable. You then print the result and decrement the global variable count before returning the result. println makes this function impure.

But what if you remove the println? Is the function still impure? The function is still impure because it changes the values of count while executing. If you invoke another function in another thread accessing the same count variable, a race condition might cause some unexpected results.

Challenge 2: Pure or impure?

Is output a pure function? Why or why not?

fun output(x: Int): Unit = println("x = $x")

Challenge 2 solution

This function always provides the same output, Unit, for the same input. The problem is that it logs messages, so it has side effects. Because of this, output is not a pure function.

Challenge 3: Pure or impure?

Is randomAdd a pure function? Why or why not?

fun randomAdd(a: Int, b: Int): Int = a + b + Random.nextInt()

Challenge 3 solution

This function doesn’t provide the same output for the same input values because of the Random component. What about side effects? Even if it’s not directly visible, this function has a side effect: It changes the state of the Random object.