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).
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 map
s 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):
Path
is not a directory; in which case the required information is extracted fromPath
and is added to the accumulator,acc
, byf
.Path
is a symbolic link, that is a shortcut to another directory; in which case the current value ofacc
is returned with no further action.Path
is an actual directory; in which casetraverse
calls itself recursively to process the new root directory, with the current value ofacc
passed in as the newinit
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 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).
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.