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.You can unlock the rest of this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.
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])
}