Kotlin lists inspired by haskell

10 min readOct 8, 2018

Haskell is an entirely functional and extremely concise language. Anyone who has ever tried to write code in Haskell will notice how much more concise and elegant it is than writing the same thing in an imperative language. In my view you cannot achieve the same results in Java, but Kotlin allows you to make progress in this direction and to try out an entirely functional style for yourself.

You can produce more complex ideas and features, by implementing to your basic function the 3 best-known functions; the ones that people get to know right at the start of studying any functional language: map, filter, and reduce.
And last but not least, I have create a repo. You can clone and check the tests to see how it works. Feel free to play with it by adding more interesting stuff.

Before we start, I want you to know that the article is very much of a research nature and no one is being asked to write code in this style. What’s more, code written in this sort of style will be critically slow and should not be used in production apps. No doubt there are ways of improving it, however the aim of this article is not to discover these ways, but rather to consider an alternative approach to writing code. This approach can be useful while working with recursive data structures. In addition, it is often easier to understand code written in a functional style than in an imperative one.

Key functions

Lists have a very important role to play in the language and lots of useful functions are realised for lists. Let’s consider some of these and how they can be realised in Kotlin.

head (x:_) = x
head [] = badHead

If the list contains elements, then we return the first element, otherwise we return an error.
We are not in a position to write code of this kind, but overall, upon examination, it is very similar to the when template. And we also use the extension function, so that we have the option later on of using this method on lists and in order to have a slightly more concise way of obtaining a value without brackets at the end, as is the case with call method.

val <T> List<T>.head: T
  get() = when (this.isEmpty()) {
    true -> throw NoSuchElementException("List is empty.")
    false -> this[0]
  }

In order to use recursion conveniently, we would like to divide the list up into first element + all the others. With this end in mind let’s try to realise the tail function.
This is what it looks like in Haskell:

tail (_:xs) =  xs
tail [] =  errorEmptyList "tail"

Unfortunately, Kotlin does not offer a level of pattern matching which would allow you to describe it in the same style, so here we have to write some code.

val <T> List<T>.tail: List<T>
  get() = drop(1)

Yes, it is sort of cheating to use a function from the language library, but, on the other hand, we would in any case have had to write code for this method, so it is better to use methods which we already know will definitely work.

Now that we know how to divide the list into the first element + the rest of the list. We will also need a function to concatenate the list and one element, which later on will actively be used for the transformation of other operations on the list.

operator fun <T> List<T>.plus(x: T): List<T> =
             ArrayList(this).also { it.add(x) }

We are now able to add the element at the end of the list, and our implementation of the map function becomes operational and ready-to-use. Unfortunately, once again, we aren’t in a position to add an object to the list in any other, more convenient way, so we use the add method.

At the present time we have almost everything we need. The only thing we need now is to have the option of describing the boundary condition for exiting the recursion. For this we shall use the standard isEmpty() method. Let’s stop and see what we have so far:

isEmpty() // do we have elements in list
head // first element of list
tail // list without first element
list + element // sum of list and element

In fact, this is all that we need to produce all the methods will be needed later.
To my taste, it would be more convenient to use a comparison of list size in the when operators. Kotlin already offers us size in order to obtain the size of the list, however, let’s say we want to realise it ourselves. Using your functionality, very simply, it will be:

Applying key functions

Let’s consider the most common example. Let’s say we have a list of whole numbers and we want to add them up, leaving aside the existence (or otherwise) of series. All that we have is the methods which we derived above and the recursion. We shall use the same approach for this as when calculating the sum of the list:

The idea is very simple: if there are no elements in the list, then the sum is equal to 0, otherwise it is the sum of the first element and the recursive call of the sum for the tail.

Irrespective of the fact that, in the case of this code, we are not concerned about speed of execution and optimisations, you cannot help but remember the capabilities of the language in terms of using tail recursion. Tail recursion is an individual case of recursion whereby a recursive call is the final operation before function return. A mark of this kind of recursion is that it guarantees you the possibility of restructuring code for integration. As you know, the main problem with recursion is that, while the function is running, you have to store the stack of calls, so that, when the boundary condition is reached, you can go back and count the final result.

It might seem that the function of the sum which we described is indeed that, since the last call is sum(xs.tail). However, generally speaking, this is not correct. If you describe the code a little differently, it will be easy to see:

Now you can see that, in fact, the sum of the first element and the remainder of the tail consitutes the last call.

The good news is that, if you add the modifier tailrec to the function, Kotlin tells you that the function isn’t that. However, it is not very complicated to correct. A common method for correcting the function is to use an auxiliary variable as an auxiliary variable for storing results. It looks like this:

In order to calculate the sum of the elements, all you have to do is specify 0 as the second parameter. And in order to do so idiomatically, without giving outsiders access to the parameter (which they don’t need to have), we restructure the function somewhat, concealing the calculations performed inside the function.

With this knowledge you can see that the size function, which we realised above, does not satisfy the necessary conditions for tail recursion.

And now, let’s try to create map, filter and reduce in Kotlin. Later on, we will see that it would have been enough to realise only the last of these, and the others are generally being derivative from the last one. But let’s do things in order.

Fundamental functions

MAP

The iterative realisation of this function assumes moving down the list in order, applying the transformation function and adding all the elements obtained to the new collection. We will be using recursive calls, where an empty list is the boundary condition. Thus, realisation will look like this:

If there are no elements in the initial list, then we return an empty list, otherwise we apply transformation to the first element and add recursive call to the end for the remainder of the list.

However, we don’t have a function for concatenating element and list. But we are already able to realise it. For a start, we derive a more general case for concatenating a pair of lists and, after that, we use it to add to the element of another list.

FILTER

Realisation will be similar to map, the only difference being to understand whether or not we need to add the current element to the result. For this we need to call the lambda which we obtained as a parameter. Realisation will look like this:

If the current element fulfills the condition of the filter, we add it recursively to the tail of the list, otherwise we continue working with only the tail of the list.

REDUCE

This is the most complicated function to understand and, at the same time, the most powerful. Most often, this is used to collapse a list down to a single element. We have a starting value s0, a list of elements a[] and the function f. For a start value and the following element in the list function f returns the new element. f(s0, a[0]) = s1. And, thus, we work our way through the whole list of elements in order, obtaining a single output value. A quite common example is adding up the elements in an array. In this case 0 is the starting value, and the function returns the sum of two elements: f(s, a[i]) = s + a[i].
Let’s consider how we can create this function.

In principle the realisation in this case is absolutely the same as we described above. If there are no elements in the list, we return the current value, otherwise we calculate a new first element and we again call the reduce function for it and the tail of the lists.

We note that we can likewise create modifications to this function. For example, not specifying the starting value, but using the first element in the list for this purpose. In order to understand that this does not exhaust the capabilities of reduce, let’s imagine using another list as the starting value. In this case each time we will save not one value, but the list — thanks to which our capabilities will increase significantly at iteration. For example, we will try to apply the reducе function in such a way as to obtain the source list at output:

As I imagine you have now guessed, we were able to use reduce for an alternative realisation of map and filter. Since we have learnt, with the help of reduce, to return exactly the same list, you only need to make very few changes to obtain the capability for transforming each element. In the case of filter everything is very similar.

Besides this, it is often forgotten that reduce can also be applied not from the start of the list, but from the end. No doubt we could simply turn the list round and, once that has already been done, apply reduce — but that isn’t what we want. Let’s try to write something and understand how reduce works for collapsing the list down in the reverse order.

If the list is not empty, we apply function f to the result of collapsing the tail of the list and to the head of the list. This way the first element will be the last to be processed, the last-but-one the second to be processed and so on. In this case modifications also need to be added, using the last element in the list as a starting value and so on.
Almost always, when working with lists, you can use a combination of these 3 functions to obtain the result you want.

Let’s also realise the zip function which will allow us to combine 2 lists.
At input we obtain 2 lists and want to return a list of pairs from the elements in the source lists with a length equal to the minimum length of the lists obtained at input.
As usual, you have to think about exiting the recursion and writing a function.

You can add your modifications, which will allow you, instead of returning a pair of elements, to apply a given function to two elements. In Haskell this function is called zipWith. And it is realised using the functionality which we were able to write very simply:

fun <T, R, C> zipWith(xs: List<T>, ys: List<R>, f: (T, R) -> C): List<C> = zip(xs, ys).map { f(it.first, it.second) }

Very often, when using functionality, problems occur when you need to perform operations based not on objects in lists, but on indices. Let’s say we need to add up all the even elements in a list. You can try to do this using reduce, supporting Pair<Int, Boolean> as the current value, adding a value if flag == true, and, each time, getting a false flag at the next step. However, this doesn’t look very elegant and the person reading the code will have to work out what you wanted to express using this code. Kotlin has infinite sequences and they are wonderfully suited to solving this task. In terms of stating explicitly what we want to achieve, our aim is to filter out all the elements with odd indices and to add up the remaining elements. And, in order to be able to obtain indices, all you have to do is call zip for the list and sequence [0,1,2..]

You can find the zip function for 2 sequence in the standard Kotlin library.

And now let’s consider the simple task which inspired me to write this guide. And let’s see what its realisation looks like in an imperative language, in Kotlin and, finally, in Haskell.

We have to calculate the maximum sum from all the pairs of numbers next to one another in an array of whole numbers. The size of the array is greater than 1, and you don’t need to worry about overflow when adding up the elements.

The functional approach in Kotlin using written functions (I propose using the max function for practice with a view to performing the realisation yourself):

Realisation in Haskell:

As we can see, what is realised in Kotlin (by the way, we could have used reduce for solving this task) is very similar to what you can write in Haskell.

Conclusion

No doubt this is not worth using in development, as everything was realised far from optimally, solely for the purposes of demonstrating a functional approach. Also, almost everything which has been written is contained in the standard Kotlin library, so possibly in future, instead of writing yet another for cycle, you could use the functional style Kotlin provides.

Probably the most complicated thing about functional style is that a given task can be solved in different ways. The most obvious ways may be cumbersome and complicated to understand in the future, while writing the most easy-to-understand ways may require time and serious mental effort. The only thing which can help you get the hang of it is constant practice and training.

P.S: As mentioned before, here’s the repository with more detail of the examples given in the article. Enjoy running tests and playing around with it!

P.P.S: You can find alternative approach for implementing same functionality here: kata-implementing-functional-list-data-structure-kotlin.html.
Also you can check arrow for binding Kotlin with Functional Programming it includes the most popular data types, type classes and abstractions.