G. Appendix G: Chapter 7 Exercise & Challenge Solutions

Written by Massimo Carli

Exercise 7.1

Implement the extension function isEmpty(), which returns true if FList<T> is empty and false otherwise.

Exercise 7.1 solution

You can solve this exercise a few different ways. The first uses what you implemented in the chapter and the size function.

fun <T> FList<T>.isEmpty(): Boolean = size() == 0

Here, you just return true if the size is 0 and false otherwise.

Another solution uses the same size logic like this:

fun <T> FList<T>.isEmpty(): Boolean = match(
  whenNil = { true },
  whenCons = { _, _ -> false }
)

Here, you simply return:

1. true if the receiver is Nil.
2. false if the receiver is FCons<T>.

Verify the usage by running the following code:

fun main() {
  println(FList.empty<Int>().isEmpty())
  println(FList.of(1).isEmpty())
  println(FList.of(1, 2, 3).isEmpty())
}

And you get the following output:

true
false
false

Exercise 7.2

Implement the extension function tail(), which returns the tail of a given FList<T>.

Exercise 7.2 solution

You can easily implement the tail function like this:

fun <T> FList<T>.tail(): FList<T> = match(
  whenNil = { FList.empty() },
  whenCons = { _, tail -> tail }
)

In this case, you simply return:

1. The empty list List.empty() if the receiver is Nil.
2. The tail property if the receiver is FCons<T>.

Verify the usage by running the following code:

fun main() {
  println(FList.empty<Int>().tail())
  println(FList.of(1).tail())
  println(FList.of(1, 2, 3).tail())
}

You’ll get something similar to the following output:

com.raywenderlich.fp.Nil@27c170f0
com.raywenderlich.fp.Nil@27c170f0
FCons(head=2, tail=FCons(head=3, tail=com.raywenderlich.fp.Nil@27c170f0))

Exercise 7.3

Kotlin provides forEachIndexed for the Iterable<T> interface, which accepts as input a lambda of type (Int, T) -> Unit. The first Int parameter is the index of the item T in the collection. To test forEachIndexed, run the code:

listOf("a", "b", "c").forEachIndexed { index, item ->
  println("$index $item")
}

Getting the following output:

 0 a
 1 b
 2 c

Can you implement the same for FList<T>?

Exercise 7.3 solution

The solution, in this case, is a little more complicated because you need to keep track of the index for the current element. The following implementation is a possible option:

fun <T> FList<T>.forEachIndexed(fn: (Int, T) -> Unit) { // 1

  fun FList<T>.loop(i: Int = 0): Unit = match( // 2
    whenNil = {}, // 3
    whenCons = { head, tail ->
      fn(i, head) // 4
      tail.loop(i + 1) // 5
    }
  )

  loop() // 6
}

In this code, you:

1. Define forEachIndexed as an extension function for FList<T>, accepting a lambda of type (Int, T) -> Unit as input.
2. Implement loop as an internal extension function that takes the current element’s index as input. The default value for the index i is 0.
3. Do nothing if the receiver is Nil because you completed the iteration on the list.
4. Evaluate the input lambda fn, passing the current index and the current element otherwise.
5. Invoke the same forEachIndexed on tail, passing the next index value as input.
6. Invoke loop, using its default input parameter, 0, to start the iteration.

When you run this code:

fun main() {
  FList.of("a", "b", "c").forEachIndexed { index, item ->
    println("$index $item")
  }
}

You’ll get the following output:

0 a
1 b
2 c

Exercise 7.4

Another option to implement forEachIndexed is to make FList<T> an Iterable<T>. How would you do that? To make all the code coexist in the same codebase, call the Iterable<T> version IFList<T> with INil and ICons<T>.

Exercise 7.4 solution

As mentioned in the problem statement, start the exercise with the existing FList<T> definition in FList.kt and rename it in IFList<T> along with INil and ICons<T>. A possible solution could be:

sealed class IFList<out T> : Iterable<T> { // 1

  companion object {
    @JvmStatic
    fun <T> of(vararg items: T): IFList<T> {
      val tail = items.sliceArray(1 until items.size)
      return if (items.isEmpty()) {
        empty()
      } else {
        ICons(items[0], of(*tail))
      }
    }

    @JvmStatic
    fun <T> empty(): IFList<T> = INil
  }
}

private object INil : IFList<Nothing>() { // 2
  override fun iterator(): Iterator<Nothing> =
    object : Iterator<Nothing> {
      override fun hasNext(): Boolean = false
      override fun next(): Nothing =
        throw NoSuchElementException()
    }
}

private data class ICons<T>(
  val head: T,
  val tail: IFList<T> = INil
) : IFList<T>() {

  override fun iterator(): Iterator<T> =
    object : Iterator<T> { // 3
      var current: IFList<T> = this@ICons // 4
      override fun hasNext(): Boolean = current is ICons<T> // 5

      override fun next(): T {
        val asICons = current as? ICons<T> ?:
          throw NoSuchElementException() // 6
        current = asICons.tail // 7
        return asICons.head // 8
      }
    }
}

In this code, after copying the content of FList.kt and renaming FList<T> to IFList<T>, Nil to INil and FCons<T> to ICons<T>, you:

1. Make IFList<T> implement Iterable<T>. This requires you to implement iterator in both INil and IFList<T>.

2. Implement Iterable<Nothing> in INil. Here, the list is empty, so hasNext always returns false and next throws a NoSuchElementException.

3. Make ICons<T> implement Iterator<T>, which requires some state.

4. Define current as the current state of the iterator, pointing initially to the ICons<T> receiver itself.

5. Implement hasNext, checking whether the current element is an ICons<T>. In this case, it has something to iterate over. Otherwise, it’s Nil, so there’s nothing more.

6. Access the current element in next, casting it to ICons<T>. Usually, clients invoke next after hasNext, so you’re assuming the cast will be successful. If this isn’t true, you throw another NoSuchElementException. Save the value in the local constant asICons.

7. Move the cursor ahead, assigning the value of tail to current.

8. Return the value of asICons.

Now, test the code by running this:

fun main() {
  IFList.of(1, 2, 3).forEach {
    println(it)
  }
}

You then get the following output:

1
2
3

Exercise 7.5

Implement addHead, which adds a new element at the head of an existing FList<T>.

Exercise 7.5 solution

The addHead function is very simple:

fun <T> FList<T>.addHead(newItem: T): FList<T> =
  FCons(newItem, this)

You just create a new FCons<T> object by passing the new value as head and using the current receiver as the tail.

To test the previous code, run:

fun main() {
  val initialList = FList.of(1, 2)
  val addedList = initialList.addHead(0)
  initialList.forEach {
    print("$it ")
  }
  println()
  addedList.forEach {
    print("$it ")
  }
}

You’ll get the output:

1 2
0 1 2

Exercise 7.6

Kotlin defines the take function on Iterable<T> that allows you to keep a given number of elements.

For instance, running the following code:

 fun main() {
   listOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
     .take(3)
     .forEach { print("$it ") }

You’d get:

1 2 3

Can you implement the same take function for FList<T>?

Exercise 7.6 solution

A possible implementation of the take function for FList<T> is the following:

fun <T> FList<T>.take(n: Int): FList<T> = match( // 1
  whenNil = { FList.empty() }, // 2
  whenCons = { head, tail ->
    if (n > 0) {
      FCons(head, tail.take(n - 1)) // 3
    } else {
      FList.empty() // 4
    }
  }
)

In this code, you:

1. Define take using match.
2. Return the empty list if the receiver is Nil.
3. Check the parameter n that indicates how many elements you have to take. If this isn’t 0, you return a new FList<T> containing the head and, as the tail, what you get invoking take for n - 1 elements.
4. Return no more elements if n is 0.

Test the solution by running this code:

fun main() {
  FList.of(1, 2, 3, 4, 5)
    .take(0) // 1
    .forEach { print("$it ") }
  println()
  FList.of(1, 2, 3, 4, 5)
    .take(1) // 2
    .forEach { print("$it ") }
  println()
  FList.of(1, 2, 3, 4, 5)
    .take(5) // 3
    .forEach { print("$it ") }
  println()
  FList.of(1, 2, 3, 4, 5)
    .take(6) // 4
    .forEach { print("$it ") }
}

The output is:

             // 1
1            // 2
1 2 3 4 5    // 3
1 2 3 4 5    // 4

These are the values for:

1. take(0).
2. take(1).
3. Taking all the elements in FList<T>.
4. Taking more elements than the available ones.

Exercise 7.7

Kotlin defines the takeLast function on Iterable<T> that allows you to keep a given number of elements at the end of the collection. For instance, running the following code:

 fun main() {
   listOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
     .takeLast(3)
     .forEach { print("$it ") }

You’d get:

8 9 10

Can you implement the same takeLast function for FList<T>?

Exercise 7.7 solution

This exercise is a little more complicated than the previous one. A first implementation could be the following:

fun <T> FList<T>.takeLast(n: Int): FList<T> = match( // 1
  whenNil = { FList.empty() }, // 2
  whenCons = { head, tail ->
    if (tail.size() >= n) {
      tail.takeLast(n) // 3
    } else {
      FCons(head, tail) // 4
    }
  }
)

Here, you:

1. Define takeLast as an extension function of FList<T>, accepting an input parameter n of type Int representing the number of elements you want to take at the end of the list.
2. Return the empty list if the receiver is Nil.
3. Check the value of n. If it’s greater than the current size, you return the result of invoking takeLast on the tail. This is because it means you still have elements to skip at the beginning of the list.
4. Return a new FCons<T> using the current head and tail if the size is equal to or smaller than n.

Run this code to test the previous code:

fun main() {
  (0..6).forEach {
    println("takeLast $it")
    FList.of(1, 2, 3, 4, 5)
      .takeLast(it)
      .forEach { print("$it ") }
    println()
  }
}

It allows you to test takeLast with different values for the size of the input. You get:

takeLast 0

takeLast 1
5
takeLast 2
4 5
takeLast 3
3 4 5
takeLast 4
2 3 4 5
takeLast 5
1 2 3 4 5
takeLast 6
1 2 3 4 5

The previous code is simple, but it uses the function size you implemented in the chapter, which has complexity O(N). This makes the complexity of takeList O(N^2). The usual question is: Can you do better? Of course you can!

Look at takeLast as another way to say:

1. Your Flist<T> has length M.
2. You need to keep n elements.
3. So, just return what you have when you skip M-n elements.

Following this idea, you could implement the skip function like this:

fun <T> FList<T>.skip(n: Int): FList<T> = match( // 1
  whenNil = { FList.empty() }, // 2
  whenCons = { head, tail ->
    if (n > 0) {
      tail.skip(n - 1) // 3
    } else {
      FCons(head, tail) // 4
    }
  }
)

Here, you:

1. Define skip as an extension function of FList<T>, accepting an input parameter n of type Int representing the number of elements you want to skip at the beginning of the list.
2. Return the empty list if the current receiver is Nil.
3. Invoke skip on the tail, passing n - 1 as parameter value if there are other values to skip.
4. Return the current receiver if there’s nothing else to skip. This happens when n <=0.

Again, run the following code to test the behavior of skip:

fun main() {
  // ...
  (0..6).forEach {
    println("Skipping $it")
    FList.of(1, 2, 3, 4, 5)
      .skip(it)
      .forEach { print("$it ") }
    println()
  }
}

You get:

Skipping 0
1 2 3 4 5
Skipping 1
2 3 4 5
Skipping 2
3 4 5
Skipping 3
4 5
Skipping 4
5
Skipping 5

Skipping 6

Now, write takeLast2 as a second version of takeLast, like this:

fun <T> FList<T>.takeLast2(n: Int): FList<T> = // 1
  skip(size() - n) // 2

Here, you:

1. Define takeLast2 as an extension function of FList<T>, accepting an input parameter n of type Int representing the number of elements you want to take at the end of the list.
2. Invoke size to get the length of the receiver, and invoke skip to skip the values in excess.

Run this code to test how this works:

fun main() {
  (0..6).forEach {
    println("takeLast2 $it")
    FList.of(1, 2, 3, 4, 5)
      .takeLast2(it)
      .forEach { print("$it ") }
    println()
  }
}

Getting the following output:

takeLast2 0

takeLast2 1
5
takeLast2 2
4 5
takeLast2 3
3 4 5
takeLast2 4
2 3 4 5
takeLast2 5
1 2 3 4 5
takeLast2 6
1 2 3 4 5

Because you invoke size only once, the complexity of takeLast2 is O(N).

Challenge 7.1

Kotlin provides the functions first and last as extension functions of List<T>, providing, if available, the first and last elements. Can you implement the same for FList<T>?

Challenge 7.1 solution

The implementation of first for FList<T> is simple because it’s exactly the same as head, which you implemented in the chapter.

fun <T> FList<T>.first() = head()

The implementation of last is also simple if you use the functions skip and size that you implemented earlier.

fun <T> FList<T>.last() = skip(size() - 1).head()

Run the following code to get the value of first and last in some specific edge cases:

fun main() {
  println(FList.empty<Int>().first())
  println(FList.empty<Int>().last())
  println(FList.of(1).first())
  println(FList.of(1).last())
  println(FList.of(1, 2).first())
  println(FList.of(1, 2).last())
}

And you get:

null
null
1
1
1
2

Challenge 7.2

Kotlin provides an overload of first for Iterable<T> that provides the first element that evaluates a given Predicate<T> as true. It also provides an overload of last for List<T> that provides the last element that evaluates a given Predicate<T> as true. Can you implement firstWhen and lastWhen for FList<T> with the same behavior?

Challenge 7.2 solution

A very simple first implementation for firstWhen is:

fun <T> FList<T>.firstWhen(predicate: Predicate<T>): T? =
  filter(predicate).first()

Here, you just use filter to get the FList<T> of all the values for the given predicate, and then you take the first element.

You might notice that in this case filter creates a complete FList<T> of all the values that evaluate the predicate as true, but you just need the first. A possible better implementation is the following:

fun <T> FList<T>.fastFirstWhen(predicate: Predicate<T>): T? = match(
  whenNil = { null },
  whenCons = { head, tail ->
    if (predicate(head)) {
      head
    } else {
      tail.fastFirstWhen(predicate)
    }
  }
)

In this code, you search for the first element that evaluates the predicate to true. You do this by testing the head and continue to the tail if it evaluates to false.

Use the same approach as firstWhen with the following implementation of lastWhen:

fun <T> FList<T>.lastWhen(predicate: Predicate<T>): T? =
  filter(predicate).last()

Here, the only difference is that you take the last element of the one you got, invoking filter first.

Note how a fast version of lastWhen doesn’t make sense because you always need to evaluate all the elements in FList<T> to find the last one.

Run this code to test firstWhen and lastWhen:

fun main() {
  val isEven: Predicate<Int> = { a: Int -> a % 2 == 0 }
  println(FList.of(1, 2, 3, 4, 5, 6).firstWhen(isEven))
  println(FList.of(1, 2, 3, 4, 5, 6).lastWhen(isEven))
  println(FList.of(1, 2, 3, 4, 5, 6).fastFirstWhen(isEven))
}

You get:

2
6
2

Challenge 7.3

Implement the function get that returns the element at a given position i in FList<T>. For instance, with this code:

fun main() {
  println(FList.of(1,2,3,4,5).get(2))
}

You get:

3

Because 3 is the element at index 2. Consider 0 the index of the first element in FList<T>.

Challenge 7.3 solution

Creating a set of reusable functions is a very powerful tool and allows you to implement a complete library. A possible solution for the get function is the following:

fun <T> FList<T>.get(i: Int): T =
  skip(i).head() ?: throw ArrayIndexOutOfBoundsException()

You basically skip i values and take the head. If the head doesn’t exist, you throw an ArrayIndexOutOfBoundsException. This allows you to run the following code:

fun main() {
  val list = FList.of(1, 2, 3)
  println(list.get(0))
  println(list.get(1))
  println(list.get(2))
  println(list.get(3))
}

And get:

1
2
3
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException

Of course, accessing the value at index 3 throws an ArrayIndexOutOfBoundsException.

To make things fancier, just use the operator keyword like this:

operator fun <T> FList<T>.get(i: Int): T =
  skip(i).head() ?: throw ArrayIndexOutOfBoundsException()

Now, you can use the [] syntax:

fun main() {
  val list = FList.of(1, 2, 3)
  println(list[0])
  println(list[1])
  println(list[2])
  println(list[3])
}

And get the same output.