C.
Appendix C: Chapter 3 Exercise & Challenge Solutions
Written by Massimo Carli
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as text.
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))
}
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
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
}
}
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++
}
val expr4 = { CounterIterator.next() }
Exercise 3.4 solution
In this case, expr4 is not referentially transparent because the expression has a side effect.
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
}
}
Exception in thread "main" java.lang.AssertionError: expr4 is not RT
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.
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:
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.
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"
}
infix fun <A, B, C> Writer<A, B>.compose(
w: Writer<B, C>
): Writer<A, C> = w after this
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)
f: Writer<A, B>
g: Writer<B, C>
h: Writer<C, D>
(str1 + str2) + str3 == str1 + (str2 + str3)
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
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)
}
fun <A> identity(a: A) = a
fun <A> id(): Writer<A, A> = { a -> a to "" }
f after id == id after f == f
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"
}
f after id
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"
}
str = ""
b = a
c = f(b) = f(a)
"$str\n$str2\n" = "$str2\n"
f(a) to "$str2\n"
id after f
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"
}
val (b, str) = f(a)
c = id(b) = b to "$str\n"
f(a) to "$str\n"
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
}
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.
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.