My favorite examples of functional programming in the Kotlin language

One of the great features of Kotlin is that it supports functional programming. Let's take a look and discuss some simple but expressive functions written in the Kotlin language.

Work with collections

Kotlin supports convenient work with collections. There are many different functions. Suppose we create some system for a university. We need to find the best students who are worthy of a scholarship. We have the following model Student:

classStudent(
    val name: String,
    val surname: String,
    val passing: Boolean,
    val averageGrade: Double
)

Now we can call the following function to get a list of the top ten students that meet all the criteria:

students.filter { it.passing && it.averageGrade > 4.0 } // 1
    .sortedBy { it.averageGrade } // 2
    .take(10) // 3
    .sortedWith(compareBy({ it.surname }, { it.name })) // 4

• We reserve only students who have passed the exam, whose average score is more than 4.0.
• Sort them by the average score.
• Leave the first ten students.
• Sort them alphabetically. The comparator first compares the names, and if they are equal, then it compares the names.

What if instead of alphabetical order, we need to preserve the original order of the students? We can do this using indexes:

students.filter { it.passing && it.averageGrade > 4.0 }
    .withIndex() // 1
    .sortedBy { (i, s) -> s.averageGrade } // 2
    .take(10)
    .sortedBy { (i, s) -> i } // 3
    .map { (i, s) -> s } // 4

• Bind the current iteration index to each item.
• We sort by the average score and leave the first ten students.
• Sort again, but now by index.
• Delete the indexes and leave only the students.

This example clearly shows how easy and intuitive to work with collections in Kotlin.

Superset (Boolean)

If you studied algebra at a university, you can remember what a superset is. For any set, its superset is the set of all its subsets, including the original set itself and the empty set. For example, if we have the following set:

{1,2,3}

That is his superset:

{{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}

In algebra, such a function is very useful. How do we implement it?

If you want to challenge yourself, then stop reading right now and try to solve this problem yourself.

Let's begin our analysis with a simple observation. If we take any element of the set (for example, 1), then the superset will have an equal number of sets with this element ({1}, {1,2}, {1,3}, {1,2,3}) and without it ({}, {2}, {3}, {2,3}).

Notice that the second set is the superset ({2,3}), and the first is the superset ({2,3}) with our added element (1) to each set. Thus, we can calculate the superset by taking the first element, calculating the superset for all others, and returning the sum of the result and the result with the addition of the first element to each set:

fun<T>powerset(set: Set<T>): Set<Set<T>> {
   val first = set.first()
   val powersetOfRest = powerset(set.drop(1))
   return powersetOfRest.map { it + first } + powersetOfRest
}

But this method will not work. The problem is the empty set: firstwill cause an error when the set is empty. Here the definition of a superset comes to the rescue - the superset of the empty set is the empty set: powerset ({}) = {{}}. Here is the corrected algorithm:

fun <T> powerset(set: Set<T>): Set<Set<T>> =
    if (set.isEmpty()) setOf(emptySet())
    else {
       val powersetOfRest = powerset(set.drop(1))
       powersetOfRest + powersetOfRest.map { it + set.first() }
    }

Let's see how it works. Suppose we need to calculate the powerset ({1,2,3}). The algorithm will act as follows:

powerset ({1,2,3}) = powerset ({2,3}) + powerset ({2,3}). map {it + 1}

powerset ({2,3}) = powerset ({3}) + powerset ({3}). map {it + 2}

powerset ({3}) = powerset ({}) + powerset ({}). map {it + 3}

powerset ({}) = {{}}

powerset ({3}) = {{}, {3}}

powerset ({2,3}) = {{}, {3}} + {{2}, {2, 3}} = {{}, {2}, {3}, {2, 3}}

powerset ({1,2,3}) = {{}, {2}, {3}, {2, 3}} + {{1}, {1, 2}, {1, 3}, {1, 2, 3}} = {{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}

But we can improve our function even more. Let's use the let function to make the notation shorter and more compact:

fun <T> powerset(set: Set<T>): Set<Set<T>> =
    if (set.isEmpty()) setOf(emptySet())
    else powerset(set.drop(1))
           .let { it+ it.map { it + set.first() }

We can also define this function as an extension function for Collection, so that we can use this function as if it were a method Set( setOf(1,2,3).powerset()instead of powerset(setOf(1,2,3))):

fun <T> Collection<T>.powerset(): Set<Set<T>> =
    if (isEmpty()) setOf(emptySet())
    elsedrop(1)
           .powerset()
           .let { it+ it.map { it + first() }

We can also reduce the negative effects of the created recursion. In the above implementation, the state of the superset grows with each iteration (with each recursive call), because the state of the previous iteration must be stored in memory.

Instead, we could use a normal loop or a function modifier tailrec. We will use the second option to keep the function readable. The modifier tailrecallows only one recursive call in the last executed function line. Here's how we can change our function to use it more efficiently:

fun <T> Collection<T>.powerset(): Set<Set<T>> = 
    powerset(this, setOf(emptySet()))
private tailrec fun <T> powerset(left: Collection<T>, acc: Set<Set<T>>): Set<Set<T>> =
    if (left.isEmpty()) acc
    else powerset(left.drop(1), acc + acc.map { it + left.first() })

This implementation is part of the KotlinDiscreteMathToolkit library , which defines many other functions used in discrete mathematics.

Quicksort

Time for the most interesting example. You will see how a complex problem can be simplified and made readable using the style and tools of functional programming.

We implement a quick sort algorithm. The algorithm is simple: we select some element (pivot (russ. Rod )) and distribute all the other elements into two lists: a list with elements greater than the rod, and less. Then we recursively sort these subarrays. Finally, we put together a sorted list of smaller elements, a pivot and a sorted list of larger elements. For simplicity, take the first element as a bar. Here is the full implementation:

fun<T : Comparable<T>> List<T>.quickSort(): List<T> = 
    if(size < 2) thiselse {
        val pivot = first()
        val (smaller, greater) = drop(1).partition { it <= pivot}
        smaller.quickSort() + pivot + greater.quickSort()
    }
// Usage
listOf(2,5,1).quickSort() // [1,2,5]

Looks great, right? This is the beauty of functional programming.

The first problem of such a function is its execution time. She is completely unoptimized. But it is short and easy to read.

If you need an optimized function, you can use the function from the standard Java library. It is based on various algorithms depending on certain conditions, and is written natively. This should be much more efficient. But how exactly? Let's compare these two functions. Let's sort a few different arrays with random elements and compare the execution time:

val r = Random()
listOf(100_000, 1_000_000, 10_000_000)
    .asSequence()
    .map { (1..it).map { r.nextInt(1000000000) } }
    .forEach { list: List<Int> ->
        println("Java stdlib sorting of ${list.size} elements took ${measureTimeMillis { list.sorted() }}")
        println("quickSort sorting of ${list.size} elements took ${measureTimeMillis { list.quickSort() }}")
    }

Here are the results we got:

Java stdlib sorting of 100,000 elements took 83
quickSort sorting of 100,000 elements took 163
java stdlib sorting of 1000000 elements took 558
quickSort sorting of 1000000 elements took 859
java stdlib sorting of 10,000,000
106,000

As you can see, the function is quickSortalmost 2 times slower. Even for huge listings. In normal cases, the difference will typically be from 0.1 ms to 0.2 ms. This explains why in some cases we can use a function that is slightly less optimized, but well readable and simple.