See how to define and use functional datastructures (lists in this case) in Kotlin, how the process is different from Scala, and how to avoid pitfalls.
I saw an exercise in chapter 3 of the excellent Functional Programming in Scala book that deals with defining functional datastructures and uses the linked list as an example of how to go about developing such a datastructure. I wanted to try this sample using Kotlin to see to what extent I could replicate the sample.
A Scala skeleton of the sample is available in the companion code to the book here, and my attempt in Kotlin is heavily inspired (copied!) by the answer key in the repository.
This is what a basic List representation in Kotlin looks like:
The List has been defined as a sealed class. This means that all subclasses of the sealed class will be defined in the same file. This is useful for pattern matching on the type of an instance and will come up repeatedly in most of the functions.
There are two implementations of this List:
Cons: a non-empty list consisting of a head element and a tail List
Nil: an empty List
This is already very useful in its current form. Consider the following, which constructs a List and retrieves elements from it:
Now to jump onto implementing some methods of List. Since List is a sealed class, it allows for some good pattern matching, say to get the sum of elements in the List:
The compiler understands that Cons and Nil are the only two paths to take for the match on a list instance.
For a little more complex operation, „drop“ some number of elements from the beginning of the list and „dropWhile“, which takes in a predicate and drops elements from the beginning matching the predicate:
These show off the power of pattern matching with the „when“ expression in Kotlin .
To touch on a wrinkle, see how the List is defined with a type parameter that is declared as „out T“, this is called the „declaration site variance“ which, in this instance, makes List a co-variant of type T. Declaration site variance is explained beautifully with the Kotlin documentation. With the way List is declared, it allows me to do something like this:
Now, consider an „append“ function, which appends another list:
Here, a second list is taken as a parameter to the append function, but Kotlin would flag the parameter — this is because it is okay to return a co-variant type, but not to take it as a parameter. However, since we know the List in its current form is immutable, I can get by this by marking the type parameter with „@UnsafeVariance“ annotation.
Folding operations allow the list to be „folded“ into a result based on some aggregation on individual elements in it.
Consider foldLeft:
If a list were to consist of elements (2,3,5,8) then foldLeft is equivalent to „f(f(f(f(z, 2), 3),5),8)“
With this higher order function in place, the sum function can be expressed this way:
foldRight looks like the following in Kotlin:
If a list were to consist of elements (2,3,5,8) then foldRight is equivalent to „f(2, f(3, f(5, f(8, z))))“
This version of the foldRight, though cooler looking, is not tail recursive. A more stack friendly version can be implemented using the previously defined tail recursive foldLeft by simply reversing the List and calling foldLeft internally the following way:
An example of using this function is the following:
For a variation of map where the transforming function returns another list, and the final result flattens everything, that is best demoed using an example after the implementation:
This covers the basics involved in implementing a functional list datastructure using Kotlin. There were a few rough edges when compared to the Scala version, but I think it mostly works. Admittedly, the sample can likely be improved drastically. If you have any observations on how to improve the code, please do send me a PR to my GitHub repo for this sample or comment on this post.
