Applying sequences to solve algorithmic problems

In this recipe, we are going to get familiar with the generateSequence() function, which provides an easy way to define the various types of sequences. We will use it to implement an algorithm for generating Fibonacci numbers.

Getting ready

The basic variant of the generateSequence() function is declared as follows:

fun <T : Any> generateSequence(nextFunction: () -> T?): Sequence<T>

It takes one parameter called nextFunction, which is a function that returns the next elements of the sequence. Under the hood, it is being invoked by the Iterator.next() function, inside the Sequence class' internal implementation, and allows instantiation of the next object to be returned while consuming the sequence values.

In the following example, we are going to implement a finite sequence that emits integers from 10 to 0:

var counter = 10
val sequence: Sequence<Int> = generateSequence {
    counter--.takeIf { value: Int -> value >= 0 }
}
print(sequence.toList())

The takeIf() function applied to the current counter value checks whether its value is greater or equal to 0. If the condition is fulfilled, it returns the counter value; otherwise, it returns null. Whenever null is returned by the generateSequence() function, the sequence stops. After the takeIf function returns the value, the counter value is post-decremented. The preceding code will result in the following numbers being printed to the console:

[10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

The subsequent values of the Fibonacci sequence are generated by summing up their two preceding ones. Additionally, the two first values are equal to 0 and 1. In order to implement such a sequence, we are going to use an extended variant of the generateSequence() function with an additional seed parameter, declared as follows:

fun <T : Any> generateSequence(seed: T?, nextFunction: (T) -> T?): Sequence<T>

How to do it...

1. Declare a function called fibonacci() and use the generateSequence() function to define a formula for the next elements of the sequence:

fun fibonacci(): Sequence<Int> {
    return generateSequence(Pair(0, 1)) { Pair(it.second, it.first + it.second) }
            .map { it.first }
}

2. Use the fibonacci() function to print the next Fibonacci numbers to the console:

println(fibonacci().take(20).toList())

How it works...

As a result, we are going to get the next 20 Fibonacci numbers printed to the console:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]

The additional seed parameter in the generateSequence() provides a starting value. The nextFunction() function is applied to the seed while computing the second value. Later on, it is generating each following element using its preceding value. However, in the case of the Fibonacci sequence, we have two initial values and we need a pair of preceding values in order to compute the next value. For this reason, we wrapped them in Pair type instances. Basically, we are defining a sequence of Pair<Int, Int> type elements, and in each nextFunction() call, we are returning a new pair that holds the values updated accordingly. At the end, we just need to use the map() function to replace each Pair element with the value of its first property. As a result, we are getting an infinite sequence of integer types returning the subsequent Fibonacci numbers.