article banner (priority)

A birds-eye view of Arrow: working with function with Arrow Core

This is a chapter from the book Functional Kotlin. You can find it on LeanPub or Amazon.

This part was written by Alejandro Serrano Mena, with support from Simon Vergauwen and Raúl Raja Martínez.

Let’s begin with the Core library, which focuses on making functional programming shine in Kotlin. To use it, you need to add io.arrow-kt:arrow-core as a dependency in your project. At the time of writing, the library is in the 1.1.x series, with 2.0 being planned and worked on.

Being a library that targets functional programming, Arrow Core includes several extensions for function types, in the arrow.core package. The first one is compose, which creates a new function by executing two functions, one after another:

val squaredPlusOne: (Int) -> Int = { x: Int -> x * 2 } compose { it + 1 }

The function above is equivalent to { x: Int -> (x + 1) * 2 }. The composition of functions works from right to left. This is often surprising at first because we read code from left to right. However, this can simplify complex chains of functions, especially when using function references, whereas the corresponding version with explicit parameters requires nesting.

people.filter( Boolean::not compose ::goodString compose Person::name ) // instead of people.filter { !goodString(it.name) }

This way of writing functions only works when they take exactly one parameter. But let's say that we want to replace our reference to goodString with a different check. In particular, we want to check whether the string starts with a given prefix. To do so, we want to use the isPrefixOf function, which takes such a prefix as an argument.

fun String.isPrefixOf(s: String) = s.startsWith(this)

If we replace ::goodString with String::isPrefixOf, the compiler rightly complains. It's expecting a function with a single argument, but isPrefixOf has two (the receiver and the argument s). We could create a lambda that gives the first argument, but another solution is to use one of the helper functions in Arrow Core.

(String::isPrefixOf).partially1("FP")

This is an example of partial application, i.e., creating a function by providing fewer arguments than required to another function. Here we are providing one fewer argument to isPrefixOf. You may have noticed the 1 at the end of partially1. Arrow Core includes functions to partially apply not only one but up to 22 arguments at once.

Memoization

There's a function that is typically discussed when introducing recursive functions: Fibonacci numbers. These numbers form a sequence, 0, 1, 1, 2, 3, 5, 8, …, in which a given element is the sum of the two elements that precede it (except for the initial values 0 and 1). This is an example of a function whose stack may grow wildly, even for small arguments, so Kotlin recommends using the DeepRecursiveFunction constructor to define it:

val fibonacci = DeepRecursiveFunction<Int, Int> { x -> when { x < 0 -> 0 x == 1 -> 1 else -> callRecursive(x - 1) + callRecursive(x - 2) } }

This way, we prevent the stack from overflowing. However, notice that Fibonacci is not defined as a fun but as a val, so we prefer to have an actual bridge function that starts the recursive computation.

fun fib(x: Int) = fibonacci(x)

Now the function no longer causes a stack overflow, but we have another problem: we are wasting loads of time computing the same values over and over. Imagine, for example, we want fib(4), which requires both fib(3) and fib(2). But the computation of fib(3) also requires fib(2)! Since this function is pure, we know that both calls to fib(2) return the same value. For these scenarios, we can apply the technique of memoization, i.e., caching intermediate values to avoid recomputations. Arrow Core contains a specific function called memoize, which takes care of creating and updating this cache, so all we need to do is:

fun fibM(x: Int) = ::fib.memoize()(x)

In this case, by the time we get to the second call to fib(2), the entire sequence at that point has been computed and cached. We go from an exponential blowup to a linear function.

Testing higher-order functions

The last piece of functionality we describe in this section relates not to using functions but to testing them. Many people in the FP community use property-based testing instead of bare unit testing: the idea is that instead of checking particular input/output pairs, you execute a function with random inputs and check that the output satisfies some properties. For example, if you test an ordering function, you need to check that the elements in the output are equal to the elements of the input. One important part of a property-based testing framework like Kotest, is the set of generators. Generators are responsible for creating random values, and we want these generated values to have a nice distribution across the entire domain and to provide common corner cases. Think about a generator for Int: values close to zero and close to the overflow and underflow points tend to break functions that don't account for these corner cases. Kotest comes with a big battery of generators in the Arb object, but there's no support for generating functions. This means you cannot test higher-order functions, so you generally need to resort to good ol' unit testing in these cases; however, if you bring the kotest-property-arrow library into your project, this limitation is gone.

val gen = Arb.functionAToB<Int, Int>(Arb.int())

Now you can use this generator to test the behavior of functions like map.