Lists in Kotlin. Haskell approach
Haskell is a fully functional and extremely concise language. Anyone who has ever tried to write code in Haskell, notices how it turns out more concise and elegant, than to write the same thing in an imperative language. In my opinion, it is impossible to achieve the same in Java, but Kotlin allows you to move in this direction and try on a fully functional style. We can derive all the complex functions that we may need from the starting basis of the 3 most well-known functions: map, filter, reduce. In addition, I created a repository , which you can study and see the tests.
Before starting, I would like to note that this is not the way to implement a functional approach, because the code will be critically slow and not be used in production applications. Undoubtedly, there are options for how it can be improved, but the purpose of the article is not to disclose these options, but to consider an alternative approach to writing code. In any case, an understanding of this approach will help you in working with recursive data structures, and you may appreciate the beauty and elegance of how the code is read and how much easier it is to understand.
Lists play a very important role in the language, and many useful functions have been implemented for them. Consider some of them and how they can be implemented on Kotlin.
If there are elements in the list, we will return the first one, otherwise we will return an error.
We have no opportunity to write such a code, but, in general, if you look closely, it is very similar to when a template. We also use the extension function to later be able to use this method on lists and have a slightly more concise way of getting the value, without parentheses at the end, like with a method call.
')
In order to conveniently use recursion, we would also like to divide the list into the first element + all others. Let's try to implement the tail function for this.
Here is how it looks on haskell:
Unfortunately, Kotlin does not provide such a level of pattern matching, so that developers can describe in the same style, so here we have to write a little when.
It is a little dishonest to use a function from a language library, but, on the other hand, we would in any case have to write code for this method, so it would be better to use already exactly working methods.
Now we can divide the list into the first element + the rest of the list. We also need the concatenation function of the list and one element, which will later be actively used for conversion and other operations on the list.
Now we are able to add to the element at the end of the list, and our implementation of the map function becomes working and ready to use. Unfortunately, it is again not possible to add an object to the list in any more convenient way, so we use the add method.
We at the moment have almost everything we need. The only thing we need now is to be able to describe the boundary condition for exit from recursion. For this we will use the standard isEmpty () method. Let's stop and see what we have at the moment:
In fact, this is all we need to derive all the methods we need.
For my taste, it would be more convenient in the when operators to use the list length comparison. Kotlin already provides us with size in order to get this list length. However, suppose that we want to implement it ourselves. With our functionality it will be quite simple:
Consider the most common example. Suppose we have a list of integers, and we want to sum them, forgetting about the existence of cycles. All that we have is the methods that we derived above, and recursion. To do this, we use the same approach as when calculating the size of the list:
The idea is very simple: if there are no elements in the list, then the sum is 0; otherwise, it is the sum of the first element and the recursive sum call for the tail.
Despite the fact that we don’t care about execution speed and optimizations in this code, it’s impossible not to recall the possibilities of the language in using tail recursion. Tail recursion is a special case of recursion in which a recursive call is the last operation before returning from a function. This type of recursion is noteworthy because it allows you to rebuild the code by iteration. As you know, the main problem of recursion is that during the execution of the function, it is necessary to store the call stack so that when the boundary condition is reached, you can go back and recalculate the final result.
It may seem that the function of the sum that we have described is just that, because the last call is sum (xs.tail) . However, this is not true. If you describe the code a little differently, it will become obvious:
Now you can see that in fact the last call is the sum of the first element and the rest of the tail.
The good news is that if you add a tailrec modifier to a function, the IDE will tell you that the function is not. However, it is pretty easy to fix. A common technique by which a function is corrected is to use an auxiliary variable to store the results. It looks like this:
In order to calculate the sum of the elements, it suffices to pass 0 as the 2nd parameter. And to make it completely idiomatic, we redo the function a little more by hiding the main calculations into the inner function without the outside world having access to the not needed.
Having this knowledge, you can see that the size function, which we implemented above, does not satisfy the necessary conditions for tail recursion.
Now we are ready to implement map, filter, reduce using Kotlin. Later we will see that it was enough to implement only the latter, and the rest, generally speaking, are derived from it. But first things first.
The iterative implementation of this function assumes a sequential movement through the list, applying the conversion function and adding all the received elements to the new collection. We will use recursive calls, where the boundary condition is an empty list. Then the implementation will look like this:
If there are no elements in the original list, then we return an empty list, otherwise, apply the transformation to the first element and add a recursive call to the end for the rest of the list.
However, we still do not have a function for concatenating an element and a list. But we can already implement it. To begin with, we will derive a more general case by concatenating a pair of lists and after that we use it to add another element to the item.
The implementation will be very similar to the map. The only difference is that you need to understand whether you need to add the current element to the result. To do this, we will call the lambda, which is received as a parameter. The implementation will look like this:
If the current element satisfies the filter condition, we add it recursively to the tail of the list, otherwise we continue working only with the tail of the list.
The most difficult to understand and, at the same time, the most powerful function (in the functional world is known as fold ). Most often it is used to collapse the list to a single item. You have a certain starting value s0 , and also there is a list of elements a [] and the function f , which returns a new one for the starting value and the next element of the list. f (s0, a [0]) = s1 . And, thus, we consistently go through the entire list of elements, at the output getting some kind of single value. A fairly common example is the summation of array elements. In this case, the starting value is 0, and the function returns the sum of two elements: f (s, a [i]) = s + a [i] . Consider how we can recursively implement this function.
In principle, the implementation is absolutely the same as we considered above. If there are no elements in the list, we return the current value, otherwise we calculate the new first element, and for it and the tail of the list, we call the reduce function again.
Note that we can also create modifications of this function. For example, do not pass the starting value, but use the first element of the list for this. To understand that the reduce capabilities do not end there, imagine that we use another list as the starting value. In this case, at each iteration, we will store not one value, but a list, thanks to which our capabilities greatly increase. For example, let's try to apply the reducation function in such a way that the output will get the original list:
Now, I think, you guess that we could use reduce, for alternative implementation of map, filter. Since we learned to return exactly the same list with reduce, we need to make quite a few changes in order to be able to transform each element. For filter, everything is very similar.
In addition, it is often forgotten that we can also use reduce not from the beginning of the list, but from the end. Undoubtedly, we can simply expand the list, and then apply reduce, but this is not interesting. Let's try to write and understand how reduce works to minimize the list in reverse order.
If the list is not empty, then we apply the function f to the result of folding the tail of the list and the head of the list. Thus, the first element will be processed last; the last but one is 2nd and so on. For this variant, it is also possible to add modifications that will use the last element of the list as the starting value, etc.
Almost always, working with lists, you can use some combination of these 3 functions to get the result of interest.
Let's also implement the zip function, which will allow us to combine 2 lists.
At the entrance we get 2 lists. And we want to return a list of pairs whose length equals the minimum of the original lists.
As usual, you need to think about quitting recursion and write a function.
You can add your own modifications, which allow you, instead of returning a pair of elements, to apply a certain function to two elements. In Haskell, this function is called zipWith . And it is implemented with the functionality that we managed to write very simply:
Very often, when using a functional approach, problems arise when it is necessary to perform manipulations based not on objects in lists, but on the basis of indices. For example, we need to sum all the even elements of the list. You can try to achieve this using reduce, maintaining the Current value of Pair <Int, Boolean> and adding a value if flag == true, and taking the negation of the flag for the next step each time. However, it looks like something is not too beautiful, and the reader of the code will have to figure out what you wanted to express with this code. In Kotlin there are infinite sequences, and they are great for solving this problem. If we analyze what we want to do it turns out that we want to filter all the elements with odd indices, and the remaining ones - to sum up. And in order to be able to get indexes, just call the zip for the list and the sequence [0,1,2 ..]
In the standard Kotlin library, you can find the zip function for a pair of sequences.
And now let's look at a simple puzzle that inspired me to write this guide, and how its implementation looks in imperative language on Kotlin and at the very end in Haskell.
It is necessary to calculate the maximum amount among pairs of adjacent numbers in an array of integers. The length of the array is greater than 1, and you can not care about overflow when summing elements.
Java imperative approach:
The functional approach to Kotlin using the written functions (I propose to implement the max function as an exercise yourself):
Haskell implementation:
As we can see, what we implemented on Kotlin (by the way, we could use reduce to solve this problem) is very similar to what you can write in Haskell.
Undoubtedly, this should not be used in the development, because everything was implemented suboptimally only in order to demonstrate the functional approach. Also, almost everything that was written is in the standard Kotlin library, so perhaps in the future, instead of writing the next for loop, you use the functional style that Kotlin provides us with.
Probably the most difficult in the functional style is that the task can be solved in different ways. The most obvious can be cumbersome and difficult to understand in the future, and writing the most understandable can take time and serious mental effort. The only thing that can help in mastering is constant practice and training.
PS: As mentioned above, you can see the repository with all the examples that are in the article. Run tests and see how it works!
PPS: You can also see an alternative approach that implements similar functionality .
And be sure to look later https://arrow-kt.io/ . In my opinion, it’s not worth looking at once, because everything looks pretty scary, but later, when functors and monads do not scare you, be sure to learn.
Before starting, I would like to note that this is not the way to implement a functional approach, because the code will be critically slow and not be used in production applications. Undoubtedly, there are options for how it can be improved, but the purpose of the article is not to disclose these options, but to consider an alternative approach to writing code. In any case, an understanding of this approach will help you in working with recursive data structures, and you may appreciate the beauty and elegance of how the code is read and how much easier it is to understand.
Basic functions
Lists play a very important role in the language, and many useful functions have been implemented for them. Consider some of them and how they can be implemented on Kotlin.
head (x:_) = x head [] = badHead If there are elements in the list, we will return the first one, otherwise we will return an error.
We have no opportunity to write such a code, but, in general, if you look closely, it is very similar to when a template. We also use the extension function to later be able to use this method on lists and have a slightly more concise way of getting the value, without parentheses at the end, like with a method call.
')
val <T> List<T>.head: T get() = when (this.isEmpty()) { true -> throw NoSuchElementException("List is empty.") false -> this[0] }
In order to conveniently use recursion, we would also like to divide the list into the first element + all others. Let's try to implement the tail function for this.
Here is how it looks on haskell:
tail (_:xs) = xs tail [] = errorEmptyList "tail"
Unfortunately, Kotlin does not provide such a level of pattern matching, so that developers can describe in the same style, so here we have to write a little when.
val <T> List<T>.tail: List<T> get() = drop(1)
It is a little dishonest to use a function from a language library, but, on the other hand, we would in any case have to write code for this method, so it would be better to use already exactly working methods.
Now we can divide the list into the first element + the rest of the list. We also need the concatenation function of the list and one element, which will later be actively used for conversion and other operations on the list.
operator fun <T> List<T>.plus(x: T): List<T> = ArrayList(this).also { it.add(x) }
Now we are able to add to the element at the end of the list, and our implementation of the map function becomes working and ready to use. Unfortunately, it is again not possible to add an object to the list in any more convenient way, so we use the add method.
We at the moment have almost everything we need. The only thing we need now is to be able to describe the boundary condition for exit from recursion. For this we will use the standard isEmpty () method. Let's stop and see what we have at the moment:
- isEmpty () - are there any items in the list
- head - the first element of the list
- tail - the list without the first element
- list + element - we can concatenate the list with the object
In fact, this is all we need to derive all the methods we need.
For my taste, it would be more convenient in the when operators to use the list length comparison. Kotlin already provides us with size in order to get this list length. However, suppose that we want to implement it ourselves. With our functionality it will be quite simple:
val <T> List<T>.size: Int get() = when (this.isEmpty()) { true -> 0 false -> 1 + this.tail.size }
Application of basic functions
Consider the most common example. Suppose we have a list of integers, and we want to sum them, forgetting about the existence of cycles. All that we have is the methods that we derived above, and recursion. To do this, we use the same approach as when calculating the size of the list:
fun sum(xs: List<Int>): Int = when (xs.size) { 0 -> 0 else -> xs.head + sum(xs.tail) }
The idea is very simple: if there are no elements in the list, then the sum is 0; otherwise, it is the sum of the first element and the recursive sum call for the tail.
Despite the fact that we don’t care about execution speed and optimizations in this code, it’s impossible not to recall the possibilities of the language in using tail recursion. Tail recursion is a special case of recursion in which a recursive call is the last operation before returning from a function. This type of recursion is noteworthy because it allows you to rebuild the code by iteration. As you know, the main problem of recursion is that during the execution of the function, it is necessary to store the call stack so that when the boundary condition is reached, you can go back and recalculate the final result.
It may seem that the function of the sum that we have described is just that, because the last call is sum (xs.tail) . However, this is not true. If you describe the code a little differently, it will become obvious:
fun sum(xs: List<Int>): Int = when (xs.size) { 0 -> 0 else -> { val head = xs.head val tailSum = sum(xs.tail) head + tailSum } }
Now you can see that in fact the last call is the sum of the first element and the rest of the tail.
The good news is that if you add a tailrec modifier to a function, the IDE will tell you that the function is not. However, it is pretty easy to fix. A common technique by which a function is corrected is to use an auxiliary variable to store the results. It looks like this:
tailrec fun sum(xs: List<Int>, acum: Int): Int = when (xs.size) { 0 -> acum else -> sum(xs.tail, xs.head + acum) }
In order to calculate the sum of the elements, it suffices to pass 0 as the 2nd parameter. And to make it completely idiomatic, we redo the function a little more by hiding the main calculations into the inner function without the outside world having access to the not needed.
fun sum(xs: List<Int>):Int { tailrec fun sumInner(xs: List<Int>, acum: Int): Int = when (xs.size) { 0 -> acum else -> sumInner(xs.tail, xs.head + acum) } return sumInner(xs, 0) }
Having this knowledge, you can see that the size function, which we implemented above, does not satisfy the necessary conditions for tail recursion.
Now we are ready to implement map, filter, reduce using Kotlin. Later we will see that it was enough to implement only the latter, and the rest, generally speaking, are derived from it. But first things first.
Main functions
MAP
The iterative implementation of this function assumes a sequential movement through the list, applying the conversion function and adding all the received elements to the new collection. We will use recursive calls, where the boundary condition is an empty list. Then the implementation will look like this:
fun <T, R> List<T>.map(f: (T) -> R): List<R> = when (this.size) { 0 -> listOf() else -> f(head) + tail.map(f) }
If there are no elements in the original list, then we return an empty list, otherwise, apply the transformation to the first element and add a recursive call to the end for the rest of the list.
However, we still do not have a function for concatenating an element and a list. But we can already implement it. To begin with, we will derive a more general case by concatenating a pair of lists and after that we use it to add another element to the item.
operator fun <T> List<T>.plus(xs: List<T>): List<T> = when (xs.size) { 0 -> ArrayList(this) else -> (this + xs.head) + xs.tail } operator fun <T> T.plus(xs: List<T>): List<T> = listOf(this) + xs
Filter
The implementation will be very similar to the map. The only difference is that you need to understand whether you need to add the current element to the result. To do this, we will call the lambda, which is received as a parameter. The implementation will look like this:
fun <T> List<T>.filter(f: (T) -> Boolean): List<T> = when (this.size) { 0 -> listOf() else -> if (f(head)) head + tail.filter(f) else tail.filter(f) }
If the current element satisfies the filter condition, we add it recursively to the tail of the list, otherwise we continue working only with the tail of the list.
REDUCE
The most difficult to understand and, at the same time, the most powerful function (in the functional world is known as fold ). Most often it is used to collapse the list to a single item. You have a certain starting value s0 , and also there is a list of elements a [] and the function f , which returns a new one for the starting value and the next element of the list. f (s0, a [0]) = s1 . And, thus, we consistently go through the entire list of elements, at the output getting some kind of single value. A fairly common example is the summation of array elements. In this case, the starting value is 0, and the function returns the sum of two elements: f (s, a [i]) = s + a [i] . Consider how we can recursively implement this function.
fun <T, R> reduce(s: T, xs: List<R>, f: (T, R) -> T): T = when (xs.size) { 0 -> s else -> reduce(f(s, xs.head), xs.tail, f) }
In principle, the implementation is absolutely the same as we considered above. If there are no elements in the list, we return the current value, otherwise we calculate the new first element, and for it and the tail of the list, we call the reduce function again.
Note that we can also create modifications of this function. For example, do not pass the starting value, but use the first element of the list for this. To understand that the reduce capabilities do not end there, imagine that we use another list as the starting value. In this case, at each iteration, we will store not one value, but a list, thanks to which our capabilities greatly increase. For example, let's try to apply the reducation function in such a way that the output will get the original list:
fun <T> reduceSame(xs: List<T>) = reduce(listOf<T>(), xs) { ys, s -> ys + s }
Now, I think, you guess that we could use reduce, for alternative implementation of map, filter. Since we learned to return exactly the same list with reduce, we need to make quite a few changes in order to be able to transform each element. For filter, everything is very similar.
fun <T, R> List<T>.map2(f: (T) -> R): List<R> = reduce(mutableListOf(), this) { xs, s -> (xs + f(s)).toMutableList() } fun <T> List<T>.filter2(f: (T) -> Boolean): List<T> = reduce(mutableListOf(), this) { ys, s -> if (f(s)) return@reduce (ys + s).toMutableList() else ys }
In addition, it is often forgotten that we can also use reduce not from the beginning of the list, but from the end. Undoubtedly, we can simply expand the list, and then apply reduce, but this is not interesting. Let's try to write and understand how reduce works to minimize the list in reverse order.
fun <T, R> reduceRight(s: T, xs: List<R>, f: (T, R) -> T): T = when (xs.size) { 0 -> s else -> f(reduceRight(s, xs.tail, f), xs.head) }
If the list is not empty, then we apply the function f to the result of folding the tail of the list and the head of the list. Thus, the first element will be processed last; the last but one is 2nd and so on. For this variant, it is also possible to add modifications that will use the last element of the list as the starting value, etc.
Almost always, working with lists, you can use some combination of these 3 functions to get the result of interest.
Let's also implement the zip function, which will allow us to combine 2 lists.
At the entrance we get 2 lists. And we want to return a list of pairs whose length equals the minimum of the original lists.
As usual, you need to think about quitting recursion and write a function.
fun <T, R> zip(xs: List<T>, ys: List<R>): List<Pair<T, R>> { return when (xs.isEmpty() || ys.isEmpty()) { true -> listOf() false -> Pair(xs.head, ys.head) + zip(xs.tail, ys.tail) } }
You can add your own modifications, which allow you, instead of returning a pair of elements, to apply a certain function to two elements. In Haskell, this function is called zipWith . And it is implemented with the functionality that we managed 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 a functional approach, problems arise when it is necessary to perform manipulations based not on objects in lists, but on the basis of indices. For example, we need to sum all the even elements of the list. You can try to achieve this using reduce, maintaining the Current value of Pair <Int, Boolean> and adding a value if flag == true, and taking the negation of the flag for the next step each time. However, it looks like something is not too beautiful, and the reader of the code will have to figure out what you wanted to express with this code. In Kotlin there are infinite sequences, and they are great for solving this problem. If we analyze what we want to do it turns out that we want to filter all the elements with odd indices, and the remaining ones - to sum up. And in order to be able to get indexes, just call the zip for the list and the sequence [0,1,2 ..]
fun sumWithEvenIndexes(xs: List<Int>) = zip(xs, generateSequence(0) { it + 1 }.take(xs.size).toList()) .filter { it.second % 2 == 0 } .map { it.first } .sum()
In the standard Kotlin library, you can find the zip function for a pair of sequences.
And now let's look at a simple puzzle that inspired me to write this guide, and how its implementation looks in imperative language on Kotlin and at the very end in Haskell.
It is necessary to calculate the maximum amount among pairs of adjacent numbers in an array of integers. The length of the array is greater than 1, and you can not care about overflow when summing elements.
Java imperative approach:
public Integer maxSum(List<Integer> array) { Integer max = array.get(0) + array.get(1); for (int i = 2; i < array.size(); i++) if (array.get(i) + array.get(i-1) > max) max = array.get(i) + array.get(i-1); return max; }
The functional approach to Kotlin using the written functions (I propose to implement the max function as an exercise yourself):
fun maxSum(xs: List<Int>) = zipWith(xs, xs.tail, {a, b -> a + b}).max()
Haskell implementation:
maxSum xs = maximum $ zipWith (+) xs (tail xs)
As we can see, what we implemented on Kotlin (by the way, we could use reduce to solve this problem) is very similar to what you can write in Haskell.
Conclusion
Undoubtedly, this should not be used in the development, because everything was implemented suboptimally only in order to demonstrate the functional approach. Also, almost everything that was written is in the standard Kotlin library, so perhaps in the future, instead of writing the next for loop, you use the functional style that Kotlin provides us with.
Probably the most difficult in the functional style is that the task can be solved in different ways. The most obvious can be cumbersome and difficult to understand in the future, and writing the most understandable can take time and serious mental effort. The only thing that can help in mastering is constant practice and training.
PS: As mentioned above, you can see the repository with all the examples that are in the article. Run tests and see how it works!
PPS: You can also see an alternative approach that implements similar functionality .
And be sure to look later https://arrow-kt.io/ . In my opinion, it’s not worth looking at once, because everything looks pretty scary, but later, when functors and monads do not scare you, be sure to learn.
Source: https://habr.com/ru/post/425527/
All Articles