Home Android & Kotlin Books Functional Programming in Kotlin by Tutorials

F
Appendix F: Chapter 6 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 scrambled text.

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

Exercise 6.1

In this section, you learned it’s useful to avoid creating multiple instances of immutable classes because they represent the same value. Given the following immutable class Id:

 class Id(val id: Int)

How would you change it to prevent any client from creating multiple instances of Id for the same id?

When you run this code:

 fun main() {
   val id1 = // Create Id for id = 1
   val id2 = // Create Id for id = 1
   val id3 = // Create Id for id = 2
   val id4 = // Create Id for id = 2
   println("${id1 === id2}")
   println("${id1 === id2}")
   println("${id1 === id3}")
   println("${id3 === id4}")
}

You get:

true
true
false
true

Exercise 6.1 solution

In Effective Java — the book by Joshua Bloch mentioned earlier in the chapter — “Item 1” states: “Consider using static factory methods instead of constructors”. This is because they allow you to control the way an instance of a class is created. In this case, “controlling” means:

class Id private constructor(val id: Int) { // 1
  companion object { // 2
    private val ids = mutableMapOf<Int, Id>() // 3
    fun of(id: Int): Id { // 4
      var existingId = ids[id]
      if (existingId == null) { // 5
        existingId = Id(id)
        ids[id] = existingId
      }
      return existingId // 6
    }
  }
}
fun main() {
  val id1 = Id.of(1)
  val id2 = Id.of(1)
  val id3 = Id.of(2)
  val id4 = Id.of(2)
  println("${id1 === id2}")
  println("${id1 === id2}")
  println("${id1 === id3}")
  println("${id3 === id4}")
}
true
true
false
true

Exercise 6.2

What happens if the Id class in Exercise 6.1 is a data class?

Exercise 6.2 solution

To see what happens when Id is a data class, you just need to add data to the class declaration:

data class Id private constructor(val id: Int) {
  // ...
}
Figure 6a.1: Private primary constructor is exposed via the generated 'copy()' method of a 'data' class.
Naqani 6u.6: Skolecu kxeyoxf baqfqyevwuk ab ixkamuf rae pbi rayezosew 'tuwm()' qenrur ew e 'jihe' ygoym.

fun main() {
  val id1 = Id.of(1)
  val id2 = id1.copy()
  println("${id1 == id2}") // 1
  println("${id1 === id2}") // 2
}
true
false
public final class Id {
   // ...
   private Id(int id) { // 1
      this.id = id;
   }

   @NotNull
   public final Id copy(int id) { // 2
      return new Id(id);
   }

   // $FF: synthetic method
   public static Id copy$default(Id var0, int var1, int var2, Object var3) {
      if ((var2 & 1) != 0) {
         var1 = var0.id;
      }

      return var0.copy(var1);
   }
   // ...
}

Exercise 6.3

The Tower of Hanoi is a classic example of a recursive function. It is a famous game consisting of three rods and a set of n disks of different radii. At the beginning, all the disks are stacked on the first rod. You need to move all the disks from the first rod to the third, following some rules.

Kuzan 9 Kibuc 5 Nusij 5
Fuqodo 6o.3: Qoloa Zejebp

Exercise 6.3 solution

To solve this problem, remember that:

fun moveDisk(disks: Int, from: Int, to: Int, using: Int) {
  if (disks > 0) {
    moveDisk(disks - 1, from, using, to)
    println("Moving $disks from $from to $to")
    moveDisk(disks - 1, using, to, from)
  }
}
fun main() {
  moveDisk(disks = 4, from = 1, to = 3, using = 2)
}
Moving 1 from 1 to 2
Moving 2 from 1 to 3
Moving 1 from 2 to 3
Moving 3 from 1 to 2
Moving 1 from 3 to 1
Moving 2 from 3 to 2
Moving 1 from 1 to 2
Moving 4 from 1 to 3
Moving 1 from 2 to 3
Moving 2 from 2 to 1
Moving 1 from 3 to 1
Moving 3 from 2 to 3
Moving 1 from 1 to 2
Moving 2 from 1 to 3
Moving 1 from 2 to 3

Exercise 6.4

Tail-recursive functions usually provide better performance. Can you prove this using the chrono function in Util.kt?

/** Utility that measures the time for executing a lambda N times */
fun chrono(times: Int = 1, fn: () -> Unit): Long {
  val start = System.nanoTime()
  (1..times).forEach({ fn() })
  return System.nanoTime() - start
}

Exercise 6.4 solution

In the chapter, you encountered different recursive implementations for the factorial of a number n:

fun recursiveFactorial(n: Int): Int = when (n) { // 1
  1 -> 1
  else -> n * recursiveFactorial(n - 1)
}

tailrec fun tailRecFactorial(n: Int, fact: Int = 1): Int = when (n) { // 2
  1 -> fact
  else -> tailRecFactorial(n - 1, n * fact)
}
fun noTailRecFactorial(n: Int, fact: Int = 1): Int = when (n) { // 2
  1 -> fact
  else -> noTailRecFactorial(n - 1, n * fact)
}
fun main() {
  val times = 1000000
  println("recursiveFactorial ${chrono(times) {
    recursiveFactorial(50)
  }}") // 1
  println("tailRecFactorial   ${chrono(times) {
    tailRecFactorial(50)
  }}") // 2
  println("noTailRecFactorial ${chrono(times) {
    noTailRecFactorial(50)
  }}") // 3
}
recursiveFactorial 92446751
tailRecFactorial   8587841
noTailRecFactorial 50125777

Challenge 6.1: Immutability and recursion

In “Immutability and recursion”, you implemented recAddMulti5 as a recursive function. Is the loop internal function tail recursive?

Challenge 6.1 solution

Yes, you can write recAddMulti5 like this, adding tailrec to loop:

fun recAddMulti5(list: List<Int>): Int {
  tailrec fun loop(i: Int, sum: Int): Int = when { // HERE
    i == list.size -> sum
    list[i] % 5 == 0 -> loop(i + 1, sum + list[i])
    else -> loop(i + 1, sum)
  }
  return loop(0, 0)
}

fun main() {
  val list = listOf(1, 5, 10, 12, 34, 55, 80, 23, 35, 12, 80)
  println(recAddMulti5(list))
}

Challenge 6.2: Tail-recursive Fibonacci

Fibonacci is one of the most famous sequences you can implement using recursion. Remember, the nth Fibonacci number is the sum of the two previous Fibonacci numbers, starting with 0, 1, 1.... Can you implement it as a tail-recursive function? Can you prove the tail-recursive function has better performance than the non-tail-recursive companion?

Challenge 6.2 solution

You can implement a function that provides the nth value in the Fibonacci sequence with a tail-recursive function like this:

tailrec fun tailRecFib(n: Int, a: Int = 0, b: Int = 1): Int = when (n) {
  0 -> a
  1 -> b
  else -> tailRecFib(n - 1, b, a + b)
}
fun noTailRecFib(n: Int): Int = when (n) {
  0 -> 0
  1 -> 1
  else -> noTailRecFib(n - 1) + noTailRecFib(n - 2)
}
fun main() {
  println(chrono {
    noTailRecFib(40) // 1
  })
  println(chrono {
    tailRecFib(40) // 2
  })
}
527457813 // 1
12316 // 2

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.