G.
Appendix G: Chapter 7 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 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
fun <T> FList<T>.isEmpty(): Boolean = match(
whenNil = { true },
whenCons = { _, _ -> false }
)
fun main() {
println(FList.empty<Int>().isEmpty())
println(FList.of(1).isEmpty())
println(FList.of(1, 2, 3).isEmpty())
}
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 }
)
fun main() {
println(FList.empty<Int>().tail())
println(FList.of(1).tail())
println(FList.of(1, 2, 3).tail())
}
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")
}
0 a
1 b
2 c
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
}
fun main() {
FList.of("a", "b", "c").forEachIndexed { index, item ->
println("$index $item")
}
}
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
}
}
}
fun main() {
IFList.of(1, 2, 3).forEach {
println(it)
}
}
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)
fun main() {
val initialList = FList.of(1, 2)
val addedList = initialList.addHead(0)
initialList.forEach {
print("$it ")
}
println()
addedList.forEach {
print("$it ")
}
}
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.
fun main() {
listOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
.take(3)
.forEach { print("$it ") }
1 2 3
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
}
}
)
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 ") }
}
// 1
1 // 2
1 2 3 4 5 // 3
1 2 3 4 5 // 4
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 ") }
8 9 10
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
}
}
)
fun main() {
(0..6).forEach {
println("takeLast $it")
FList.of(1, 2, 3, 4, 5)
.takeLast(it)
.forEach { print("$it ") }
println()
}
}
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
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
}
}
)
fun main() {
// ...
(0..6).forEach {
println("Skipping $it")
FList.of(1, 2, 3, 4, 5)
.skip(it)
.forEach { print("$it ") }
println()
}
}
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
fun <T> FList<T>.takeLast2(n: Int): FList<T> = // 1
skip(size() - n) // 2
fun main() {
(0..6).forEach {
println("takeLast2 $it")
FList.of(1, 2, 3, 4, 5)
.takeLast2(it)
.forEach { print("$it ") }
println()
}
}
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
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()
fun <T> FList<T>.last() = skip(size() - 1).head()
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())
}
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()
fun <T> FList<T>.fastFirstWhen(predicate: Predicate<T>): T? = match(
whenNil = { null },
whenCons = { head, tail ->
if (predicate(head)) {
head
} else {
tail.fastFirstWhen(predicate)
}
}
)
fun <T> FList<T>.lastWhen(predicate: Predicate<T>): T? =
filter(predicate).last()
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))
}
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))
}
3
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()
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))
}
1
2
3
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException
operator fun <T> FList<T>.get(i: Int): T =
skip(i).head() ?: throw ArrayIndexOutOfBoundsException()
fun main() {
val list = FList.of(1, 2, 3)
println(list[0])
println(list[1])
println(list[2])
println(list[3])
}