B. Appendix B: Chapter 2 Exercise & Challenge Solutions

Written by Massimo Carli

Exercise 2.1

Can you write an example of a function mapping distinct values in the domain to non-distinct values in the range, like f(b) and f(c) in Figure 2.2?

Hint: Think of a possible way to group values you get as input. A very simple example is to return a Boolean that tells if the value in input is positive or not.

Exercise 2.1 solution

A simple example of a function mapping distinct values in the domain to non-distinct values in the range is:

fun isEven(x: Int): Boolean = x % 2 == 0

This function uses a modulo to determine if a number is even or not.

You can prove this by running the following code:

fun main() {
  println(isEven(2))
  println(isEven(-2))
  println(isEven(12))
  println(isEven(18))
  println(isEven(19))
  println(isEven(-3))
  println(isEven(1))
  println(isEven(-5))
}

This is the output:

true
true
true
true
false
false
false
false

Here, distinct values for the input are mapped to the same values in the output.

As you’ll see in the rest of the book, a function mapping any type A to a Boolean is a Predicate. You can define all the predicates using the following typealias:

typealias Predicate<A> = Fun<A, Boolean> // (A) -> Boolean

Exercise 2.2

Can you write the inverse function of twice? What are the domain and range for the inverse function?

fun twice(x: Int) = 2 * x

Exercise 2.2 solution

This exercise isn’t as easy as it looks. If twice has type Fun<Int, Int>, the inverse function should have the same type. This is because if a function has type Fun<A,B>, the inverse should have type Fun<B,A>. You get this by inverting the input type A with the output type B.

The following is a possible candidate as an inverse function of twice:

fun half(x: Int) = x / 2

The half type is still Fun<Int, Int> but, because of the division between Int values, half isn’t invertible. This breaks the following required relation:

half after twice == twice after half

The first member is OK:

half after twice == half(twice(x)) == (2 * x) / 2 == x

But the second member isn’t:

twice after half == twice(half(x)) == 2 * ( x / 2)

To prove that the last equation isn’t valid, try giving it some values for x:

x = 0    2 * (x / 2) == 2 * (0 / 2) == 2 * 0 = 0 == x
x = 1    2 * (x / 2) == 2 * (1 / 2) == 2 * 0 = 0 != x
x = 2    2 * (x / 2) == 2 * (2 / 2) == 2 * 1 = 2 == x
x = 3    2 * (x / 2) == 2 * (2 / 2) == 2 * 1 = 2 != x

As you can see, this happens because half isn’t invertible, so it can’t be the inverse of twice. This is because if function f is the inverse of function g, then g must be the inverse of f. In this solution, half, seems to not work. Seems because if you consider half to be the inverse of twice, you shouldn’t invoke it using odd input values. This is because they wouldn’t be part of the range of twice. To be rigorous, the type of twice is Fun<Int, EvenInt>, where EvenInt is the type of all the even integer numbers. In that case, the inverse half would have the type Fun<EvenInt, Int>, and everything would be fine.

But how can you represent the EvenInt type? All the concepts are purposely being stressed a little bit here, but that’s the topic for Challenge 3!

It’s worth mentioning how, in practice, you usually come to compromises defining twice like this:

fun twice(x: Double): Double = 2 * x

Now, its type is Fun<Double, Double>, and the inverse function is:

fun half(x: Double): Double  = x / 2.0

Exercise 2.3

Can you prove that using Sets as objects and “is a subset of” as morphisms results in a category? In other words, a morphism from set A to set B would mean that A is a subset of B. In that case, what are the initial and terminal objects?

Hint: Think of any objects in the category as a set of elements. A morphism from A to B means that A is a subset of B. Can this help you to prove composition, associativity and identity?

Exercise 2.3 solution

To prove some kinds of objects and morphisms define a category, you need to prove the three fundamental properties:

• Composition
• Associativity
• Identity

In this case, objects are sets, and morphisms define the relation of inclusion you represent with the ⊆ symbol.

To prove composition, you need to prove that for every three sets A, B and C, if A is a subset of B and B is a subset of C, then it’s also true that A is a subset of C. Visualizing the relation with a Venn diagram, like in Figure 2a.1, helps to prove composition:

From the definition of category, to prove associativity, you need to prove that:

(h◦g)◦f = h◦(g◦f).

A similar Venn diagram helps to prove associativity:

Using the following morphisms:

• f = A is a subset of B
• g = B is a subset of C
• h = C is a subset of D

You can break it down like this:

• (h◦g) = B is a subset of D

• (g◦f) = A is a subset of C

• (h◦g)◦f = A is a subset of D

• h◦(g◦f) = A is a subset of D

Identity has a simple proof because each set contains itself, so A is a subset of A.

This proves that sets and the morphism “is a subset of” create a category.

What about the initial and terminal objects? Again, the definition comes to the rescue. The initial point is an object with outgoing arrows to all other objects in the category. In terms of sets, what set is the subset of all the other sets?

The terminal object is an object with unique incoming morphisms from all other objects in the category. What, then, is a set containing all the other sets? It has a name: superset.

The problem, in this case, is that the superset isn’t easy to represent in practice. Think of the set of all the subsets of integer values. This doesn’t exist because, for any candidate you find, there’s always another one containing it with some other integer values not included in the initial candidate. For this reason, the category of sets and the morphism “is a subset of” doesn’t have a terminal object. Categories using some kind of ordering relation like the one in this exercise don’t have terminal objects.

Exercise 2.4

In this chapter, you defined after, which allows you to write expressions like:

val formatTwice = g after f

Can you write compose instead, which would allow you to implement the same expression as:

val formatTwice = f compose g

Exercise 2.4 solution

In this case, you need to consider f as the receiver of the function and write the following code:

inline infix fun <A, B, C> Fun<A, B>.compose(
  crossinline g: Fun<B, C>
): Fun<A, C> =
  { a: A ->
    g(this(a))
  }

As you can see:

• The receiver of the function is Fun<A, B>.
• The parameter of compose is a function g of type Fun<B, C>.
• In the body, you invoke the f receiver first and then pass the result to the function g.

To test compose, use the following code with twice and format, which you created in the previous exercises.

fun main() {
  val f: Fun<Int, Int> = ::twice
  val g: Fun<Int, String> = ::format
  val formatTwice = f compose g // HERE
  println(formatTwice(37))
}

Note how the previous g after f is now f compose g.

Exercise 2.5

Can you write an example of an isomorphic function f and its inverse g and prove they always compose to identity?

Exercise 2.5 solution

The following is an example of a function and its inverse:

fun addOne(x: Int) = x + 1

fun removeOne(x: Int) = x - 1

To prove addOne and removeOne are the inverse of each other, you need to prove that:

addOne after removeOne = removeOne after addOne = identity

This is equivalent to proving that:

(x - 1) + 1 = 1 + (x - 1) = x

This is identity, so addOne and removeOne are the inverse of each other. They’re both isomorphic functions.

Challenge 1: Functions and sets

How would you represent a specific Set using a function? For instance, how would you represent the set of even numbers with a function? After that, how would you print all the values in the set?

Challenge 1 solution

A Set is something more than a bunch of things because it has some structure. An object can be in the set or not. If an object is in the Set, it must be unique. You can’t have the same object in a Set twice.

The type for a function describing a Set is then Fun<A, Boolean>. Boolean is an interesting type because you associate it with a set with just two elements: true or false. A function of type Fun<A, Boolean> is a predicate, and you can add the following definition to the Aliases.kt file in the project for this chapter:

typealias Predicate<A> = Fun<A, Boolean>

To represent the Set of even Int numbers, write:

val evenIntSet: Predicate<Int> = { a: Int -> a % 2 == 0}

To check if a value is in the Set of even numbers, you just invoke evenIntSet. For instance:

fun main() {
  println(" 0  is even?  ${evenIntSet(0)}")
  println(" 9  is even?  ${evenIntSet(-9)}")
  println(" 10 is even?  ${evenIntSet(10)}")
  println(" 3  is even?  ${evenIntSet(3)}")
}

Running the previous code, you’ll get:

 0  is even?  true
 9  is even?  false
 10 is even?  true
 3  is even?  false

Representing a set with a function allows you to check if a value is in the set or not. To actually print all the values in the set, you need to scan the whole domain and print the ones whose predicate function returns true.

For the previous example, do the following:

  (Int.MIN_VALUE..Int.MAX_VALUE)
    .filter(evenIntSet)
    .forEach { println(it) }

Challenge 2: Functions and set again

How would you represent the intersection and union of two sets using functions? The intersection is the set of objects that belong to set A and set B, and the union is the set of all objects that belong to set A or set B.

Challenge 2 solution

Suppose you have the following functions for two different sets:

/** The set of all the odd Ints */
val oddIntSet: Predicate<Int> = { a: Int -> a % 2 != 0 }

/** The set of all multiples of 37 */
val multipleOf37: Predicate<Int> = { a: Int -> a % 37 == 0 }

You would define the union like this:

/** The union of the two sets */
fun <A> union(
  set1: Predicate<A>,
  set2: Predicate<A>
): Predicate<A> = { a: A ->
  set1(a) || set2(a)
}

And the intersection like this:

/** The intersection of the two sets */
fun <A> intersection(
  set1: Predicate<A>,
  set2: Predicate<A>
): Predicate<A> = { a: A ->
  set1(a) && set2(a)
}

It’s interesting to note how the union and intersection sets are also Predicate<A>, and therefore functions of the same type as the ones you had as parameters.

You can test out your functions with the following:

val oddMultipleOf37Union =
    union(oddIntSet, multipleOf37)
val oddMultipleOf37Intersection =
  intersection(oddIntSet, multipleOf37)

println("1   is in union ${oddMultipleOf37Union(1)}")
println("37  is in union ${oddMultipleOf37Union(37)}")
println("74  is in union ${oddMultipleOf37Union(74)}")
println("100 is in union ${oddMultipleOf37Union(100)}")

println("1   is in intersection ${oddMultipleOf37Intersection(1)}")
println("37  is in intersection ${oddMultipleOf37Intersection(37)}")
println("74  is in intersection ${oddMultipleOf37Intersection(74)}")
println("100 is in intersection ${oddMultipleOf37Intersection(100)}")

Challenge 3: The right domain

Consider the following function:

fun oneOver(x: Int): Double = 1.0 / x

What’s the domain and the range for this function? When you invoke oneOver(0), you get an exception.

How can you be sure you only pass values in the domain as an input parameter?

Challenge 3 solution

You probably know from your math in school that the function 1/x doesn’t exist for x = 0. This means that the domain of oneOver is the set represented by all the Int values without 0.

The question now is: How would you represent the type of all the Int values without 0? If the related type was NonZeroInt, the previous function would become:

fun oneOver(x: NonZeroInt): Double = 1.0 / x

And, as said earlier, it would return a value for every input in its domain.

A possible option would be to define NonZeroInt like this:

@JvmInline
value class NonZeroInt private constructor(val value: Int) {
  companion object {
    operator fun invoke(value: Int): NonZeroInt? {
      return when (value) {
        0 -> null
        else -> NonZeroInt(value)
      }
    }
  }
}

In this case, you can create a NonZeroInt only using a value that isn’t 0. However, you have a problem. Try running the following code to understand what the problem is:

fun main() {
  println("1/3 = ${oneOver(NonZeroInt(3))}") // ERROR
}

This doesn’t compile because of what IntelliJ is telling you here:

oneOver is expecting a NonZeroInt and not the nullable version NonZeroInt?. As a shortcut, you might use the !! operator. In that case, the code compiles but throws an exception in case of 0: NonZeroInt(0).

fun main() {
  println("1/3 = ${oneOver(NonZeroInt(3)!!)}") // COMPILES
}

A better idea is moving the error to the creation of the NonZeroInt object itself, replacing the previous implementation of NonZeroInt with:

@JvmInline
value class NonZeroInt(val value: Int) {
  init {
    require(value != 0) { "O is not a value for this type!" }
  }
}

In this case, you can change main like this:

println("1/3 = ${oneOver(NonZeroInt(3))}")

When you run, you get the following output:

1/3 = 0.3333333333333333

Using the following code:

println("1/3 = ${oneOver(NonZeroInt(0))}")

You’ll get the following output instead:

Exception in thread "main" java.lang.IllegalArgumentException: O is not a value for this type!

In both cases, as you’ll learn in the following chapters, this isn’t a very functional way to handle this problem. One more reason to keep reading this book! :]