A Taste of Functional Programming in Kotlin

We are witnessing a programming paradigm shift towards Functional Programming (FP). The shift was triggered by a hardware crises. The major chip manufactures had hit a physical limit and had given up trying to make processors run faster. Instead, they started shipping multi-core chips where multi processors (so-called cores) share the same chip. The new chips are designed to provide increasingly more concurrency rather than faster clocks. As a result, the software industry was faced with the challenge of developing programs which can be parallelized easily.

Traditional imperative programming relies on mutating a shared program state to produce outputs. Different parts of a program, usually, have access to shared state which makes concurrency a nightmare. In contrast, functional programming encourages a programming style where all values are immutable and no program state is shared. As a result, functional programs are much more suitable for modeling concurrency and for running on parallel hardware. In addition, functional programming emphasizes constructing programs from pure functions, function which produce the same output given the same set of inputs without introducing any side effects beyond computing their outputs. These side-effect free functions enable composing programs that are clearer, shorter, easier to test, and above all, easier to reason about.

Traditional and modern programming languages, alike, are including tools and libraries that make them more functional; and Kotlin is no exception. At the time of this writing, Kotlin is one of the fastest growing languages in terms of developers’ adoption. Kotlin enjoys the unique position of being the language of choice for Android development in addition to be, arguably, the best candidate to replace Java on the JVM. Taking advantage of Kotlin’s functional goodies makes the language even more appealing.

From Imperative to Functional

Let’s start by writing a simple program to filter odd numbers in a collection of integers. Let’s assume that we have no library that does the job for us. The imperative mindset suggests a solution similar to the following:

As it can be seen in the above code, function filterOddsImperative declares a mutable list, output, then it iterates over all elements of the input collection. If the element is an even integer, it gets added to output. Finally, filterOddsImperative returns output. The assert statements in main show that the filterOddsImperative works correctly for the given input (don’t forget to enable the JVM assertion option, though). Despite that filterOddsImperative doesn’t produces side effects to its outside world, it is still written in a low-level imperative style that will quickly become difficult to read as the program grows in size. For one thing, the test whether a number is odd or even, is entangled within filterOddsImperative itself, making the function less reusable and harder to test. For another, the for loop forces the programmer to think about the low-level details of how the computation is done, rather than what should be computed.

The following code shows our first attempt at a functional solution.

In the code above, function filterOdds checks if the input collection is empty, in which case it returns an empty list. If the collection has elements, it checks the first element, head, if it is even, filterOdds wraps it in a list in which it accumulates the result of calling itself recursively (line 4) on the rest of the collection elements (apart from the first element). If head is not even, filterOdds calls itself on the rest of the collection elements (line 6). Note that take(n) produces a list consisting of the first n elements in the collection, whereas, drop(n) produces a list of the elements in the collection minus the first n elements.

In functional programming, we tend to find general solutions through which a wide range of the problem instances is solved. For example, nothing stops us from writing some function filterRecursive with which any collection of objects of any arbitrary type can be filtered according to some predicate. All what we need to do is to replace the type parameter, Int, in the previous code with some generic type, T, and pass a filtering predicate as input to the new function, filterRecursive. Have a look at the code below.

Function filterRecursive takes two arguments: a collection of objects of generic type, T, and another function, p, which is a predicate. Function p takes an object of type T and returns a Boolean. Suddenly, we have a more useful function that can be used to filter odd numbers in a collection of integers (line 10), very short strings in a collection of strings (line 11), as well as filtering any collection of objects of any type using any predicate that one can imagine!

Function filterRecursive is said to be a higher-order function (HOF). A higher-order function is a function that takes (an)other function(s) as input(s) and/or return a function as output.

Note how we passed the predicate to filterRecursive as an anonymous function or closure (Lines 10 and 11). Within the closure, it is an implicit parameter representing the object being currently passed to the predicate. The syntax {it % 2 == 0} is short for {x -> x % 2 == 0}. Note also the convention that when a closure is the last argument to a function, it is taken outside the function’s parentheses.

Great! We have an amazing pure and generic filterRecursive function that can be used on any collection of objects of arbitrary type.

Our satisfaction with the above definition of filterRecursive couldn’t be more, if it were not for the less-than-efficient recursive call listOf(head) + filterRecursive(ts.drop(1), p) (line 4). The problem with this call and how we can work around it, is discussed, next.

Tail Call Optimization (TCO)

Despite being powerful and elegant, recursive functions can be tricky when it comes to efficiency. For the compiler to be able to optimize recursive calls, recursive functions must be written in a way such that after a function calls itself, nothing is kept on the call stack. In other words, the function must call itself as that last thing it does; nothing further can be done by the function after it calls itself. This way, the compiler can transform recursive calls into efficient iteration. A function that calls itself as the last thing it does is said to be written in a tail call recursive style; and the compiler is said to be doing tail call optimization (TCO) to the function.

Let’s go back to our filterRecursive function. In the call listOf(head) + filterRecursive(ts.drop(1), p), after calling itself, filterRecursive adds the result of the call to the first element of the collection. This means that, with every call to itself, filterRecursive leaves some value on the stack to be used later. Sooner or later, with large enough number of collection elements, the stack will explode with overflow error. The way to work around this is to introduce some sort of accumulator to accumulate intermediate results. Have a look at the code below.

Function filterTCO employs an inner function, inner, to do the heavy lifting. Function inner is essentially similar to function filterRecursive that we saw earlier with few differences. First, it takes an additional parameter which is the accumulator, acc. The accumulator is a list of objects of the same type as the objects in the input collection. Secondly, inner returns the accumulator when the input collection is empty; and thirdly, inner calls itself as the last thing it does supplying either the same accumulator that was passed to it, when the current element of the input collection does not pass the predicate test (line 7), or the accumulator that was passed to it updated with the current element of the input collection, when the element passes the predicate test (line 5). Thus inner is a tail call recursive function. All that is left for filterTCO to do, is to call inner passing an empty list as the initial value of the accumulator and to return the result computed by inner.

Note that we have annotated inner with the modifier tailrec. This modifier tells the compiler to generate a warning if the function is not tail recursive (i.e if the function does something in tail position beyond calling itself).

As you can see, we managed to write an efficient recursive version of our filtering function, but the inner function plus accumulator technique that we used required quite a bit of low-level work. Let us see how we can eliminate the low-level stuff once and for all.

Eliminating Low-Level Recursion

Let’s try to generalize what function inner as implemented within function filterTCO does. Function inner receives as inputs a collection of objects of generic type, T, and an accumulator, which is a list of objects of the same type T. The list is intended to be used as a store to gradually build the output, which is also a collection of objects of type T. The function builds its output with the help of a predicate function (a function that accepts a T and returns a Boolean). The predicate can only tell which elements of the input collection will be used to build the output. It has no idea, whatsoever, how the output is built. That particular logic is hard-coded within inner.

To generalize inner, we need to replace the predicate function with a function that ‘knows’ how to add an element from the input collection to the accumulator, thus we need a function which has the type f:(A, List<A>) -> A. In fact, the accumulator needs not be a list. It’s just the initial value that the function starts with to build the output. Moreover, the output needs not be of type A, it could be of any other generic type, B, as long as function f ‘knows’ how to update the initial value (which is now of type B) with a value of type A. Thus, function inner can be generalized to the following function:

Function fold goes over the elements of an input collection, col, one by one, updating the initial value passed to it, init, using a function, f. Function f combines init with the first element in col. The result is , then, combined with the second element in col to produce a value which is combined with the third element in col, and so on (see the figure below).

The fold Operation.

Now, let’s define our filtering function in terms of fold.

Function filter defines our filtering function in terms of fold. Here, type A from the definition of fold is represented by the type of the objects in the input collection to filter, namely T; and type B from the definition of fold is represented by the type of the initial value passed to fold, namely List<T>. To do the actual filtering, fold is given an initial value for the output, which is an empty list and a function, which uses the predicate given to filter to decide which elements of the input collection will show up in the output collection. Function fold, then, goes over the elements of the input collection one by one and does the low-level stuff for us.

Not only that, we managed to define our filtering function in a succinct, elegant, and high-level form, but also, we ended-up having a powerful tool, fold, that will prove very handy in different situations. Let us see some examples.

A function that computes the length of a collection can be defined in terms of fold as:

In the above code, 0 is passed to fold as the initial value for length. As fold traverses the collection, it adds 1 to the initial value with each element it encounters. Note that in the closure above, 1 is added to the acc, no matter the value of the element. This is why we use the underscore. It indicates that we don’t care about the specific value of the element.

A function that reverses a collection can be defined in terms of fold as:

Function reverse passes an empty list as the initial value to fold, which traverses the input collection adding every element it encounters to the beginning of the list, thus producing the reverse of the input collection.

A function that maps each element in an input collection to a corresponding element in an output collection, can be defined in terms of fold as:

Along with the input collection, map passes to fold a function, f, that converts an X to a Y . Function fold applies f to every element in the input collection, producing the output collection.

As a final example of the fold pattern, we’ll develop a small utility to traverse a file system tree. We’ll call our utility function: traverse.

Example: Traversing File System Trees

A file system tree is a data structure that is typically used by an operating system to store information about; and track changes on files and directories. A file system tree consists of a root directory, in which there are usually many files and subdirectories. A subdirectory may contain other files and subdirectories, and so on.

In the above code, Java APIs for processing files are used. Function traverse expects three inputs: the Path to the root directory of the sub file system tree to be traversed, an initial value of the required output, init, and a function, f, to update the initial value with information extracted from files and directories. Function traverse uses fold to go over the files and subdirectories. With each Path encountered by fold, a list of all contained files and directories is generated using using the call Files.list(root).toList(). Every child Path is one of three possibilities (line 8):

1. Path is not a directory; in which case the required information is extracted from Path and is added to the accumulator, acc, by f.
2. Path is a symbolic link, that is a shortcut to another directory; in which case the current value of acc is returned with no further action.
3. Path is an actual directory; in which case traverse calls itself recursively to process the new root directory, with the current value of acc passed in as the new init value.

Now, we have a generic utility to traverse a file system tree and generate whatever output we may think of. For instance, a function, f, (line 11) maybe passed to traverse in order to generate one big String consisting of absolute paths to all the files in the file system tree. Similarly, a function, g, may be defined (line 12) to be used by traverse to compute the total size, in bytes, of all the files in the file system tree. As the parametrizing type of traverse in the former example is String, and isLong in the latter, “” and 0 are passed as initial values (lines 13 and 14), respectively.

Function Composition

The composition of two functions f: A -> B and g: B -> C is a third function h: A -> C, which feeds the output of f to the input of g to produce its output (see the figure below).

Function Composition

Function composition is central to functional programming. Often, a functional program can be represented as some mutable data fed into one big function, which is constructed by chaining a series of pure functions. To see this in action, we’ll carry on with our file system tree traversing example. This time, we’ll use the traverse function to implement a simple index of file names.

We’ll represent our simple file name index with a map where we can fetch a file path using a key consisting of any number of contiguous characters from the file name. Thus, the index will be of type Map<String, Collection<Path>>. A key may be part of any number of file names; and that is why the type of the values in the map is Collection<Path>, instead of just Path. Our goal is to define a function, compIndex to compute the actual index.

First, we need a function to calculate all the n-character substrings of an input string (the so-called n-grams of a string):

Function nGrams uses a sliding window of size n to scan the input string, str. It advances through the string one character at a time, adding the characters within the window to the accumulator, acc. Finally, it returns the accumulator when the number of remaining characters in the string is less than the window size.

Obviously, for function compIndex’s purpose, we’ll need to generate all n-grams from the file name for 1≤n≤ (file name’s length). Next, we define a function to do exactly that:

Function allGrams uses fold to go over a range of integers (1..str.length), where str is the input string. For each integer in the range, allGrams uses nGrams to generate the required substrings.

Now, we can feed file names to allGrams to generate keys to our index. However, before we process the file name with allGrams, we need to normalize the file name by converting it to lower-case and removing spaces and some unwanted characters. Instead of hard-coding the unwanted characters, we pass a collection of characters to a function that does the normalization:

Function normalize uses fold to go over the characters of the input string one by one; if the character is on the stop list, it doesn’t make it to the output; otherwise it gets converted to lower-case and added to the output string.

As mentioned earlier, function allGrams generates a collection of keys from a given file name. What is needed, however, is a collection of pairs of keys and the Path to the file from which name the keys were extracted. For this purpose, we may use a generic function, pairWithValue, that pairs a value of generic type B with each element in a collection of objects of generic type A. Function pairWithValue is defined as:

Note that, function pairWithValue is a simple example of using map that we defined earlier.

Now, we need a way to update the index with the generated collection of pairs. Function updateIndex does exactly that:

Function updateIndex uses fold to go over all the elements in the input collection, pairs. If the key (pair.first) is already in the index, the value (pair.second) gets added to the collection of values associated with the same key. If the key is not in the index, the pair is added to the index as a new entry. The new entry consists of pair in which the first element is the key and the second element is the value wrapped in a list.

Finally, let’s look at compIndex, the function that computes the index.

Under the hood, compIndex traverses the file system tree using traverse. For each file it encounters, the file name is extracted using the Java files APIs. The file name, then gets normalized using normalize, then substring keys get generated from the file name using allGrams. The generated keys, then, are paired with the file’s path using pairWithValue. Finally, the generated pairs are used by updateIndex to update the current value of the index being built. Notice how function composition, along with the concept of higher-order functions, is used to compute the index (see the figure below).

Function composition and HOFs within compIndex()

Now, we are ready to lookup paths to files which names contain, say, the string “ds”, like this:

Conclusion

In this article, we managed to only dip our toes in the functional waters. Nevertheless, we covered quite a bit of ground. We touched upon some important functional programming concepts, techniques and big ideas. We have seen the importance of immutable data and pure functions in constructing programs that are clearer and easier to reason about. We have seen how recursion can be a powerful technique to solve problems elegantly and we learned to work around its performance issues. We have seen few examples of far-reaching ideas and patterns which help solve problems at a higher abstraction level, like higher-order functions, fold and function composition.

**The code in this article can be found on github.