Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Kata: Implementing a Functional List Datastructure in Kotlin

DZone's Guide to

Kata: Implementing a Functional List Datastructure in Kotlin

Check out this primer on defining functional datastructures in Kotlin. Here, we explore using lists and how the process compares to scala.

· Java Zone
Free Resource

Just released, a free O’Reilly book on Reactive Microsystems: The Evolution of Microservices at Scale. Brought to you in partnership with Lightbend.

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.

Basic

This is what a basic List representation in Kotlin looks like:

sealed class List<out A> {
 
    abstract val head: A
 
    abstract val tail: List<A>
}
 
data class Cons<out T>(override val head: T, override val tail: List<T>) : List<T>()
 
object Nil : List<Nothing>() {
    override val head: Nothing
        get() {
            throw NoSuchElementException("head of an empty list")
        }
 
    override val tail: List<Nothing>
        get() {
            throw NoSuchElementException("tail of an empty list")
        }
}


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:

  1. Cons: a non-empty list consisting of a head element and a tail List

  2. 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:

val l1:List<Int> = Cons(1, Cons(2, Cons(3, Cons(4, Nil))))
assertThat(l1.head).isEqualTo(1)
assertThat(l1.tail).isEqualTo(Cons(2, Cons(3, Cons(4, Nil))))
 
val l2:List<String> = Nil


Pattern Matching With "when" Expressions

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:

fun sum(l: List<Int>): Int {
    return when(l) {
        is Cons -> l.head + sum(l.tail)
        is Nil -> 0
    }
}
fun sum(l: List<Int>): Int {
    return when(l) {
        is Cons -> l.head + sum(l.tail)
        is Nil -> 0
    }
}

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:

fun drop(n: Int): List<A> {
    return if (n <= 0)
        this
    else when (this) {
        is Cons -> tail.drop(n - 1)
        is Nil -> Nil
    }
}
 
val l = list(4, 3, 2, 1)
assertThat(l.drop(2)).isEqualTo(list(2, 1))
 
fun dropWhile(p: (A) -> Boolean): List<A> {
    return when(this) {
        is Cons -> if (p(this.head)) this.tail.dropWhile(p) else this
        is Nil -> Nil
    }
}
 
val l = list(1, 2, 3, 5, 8, 13, 21, 34, 55, 89)
assertThat(l.dropWhile({e -> e < 20})).isEqualTo(list(21, 34, 55, 89))


These show off the power of pattern matching with the "when" expression in Kotlin.

Unsafe Variance!

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:

val l:List<Int> = Cons(1, Cons(2, Nil))
val lAny: List<Any> = l


Now, consider an "append" function, which appends another list:

fun append(l: List<@UnsafeVariance A>): List<A> {
    return when (this) {
        is Cons -> Cons(head, tail.append(l))
        is Nil -> l
    }
}


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

Folding operations allow the list to be "folded" into a result based on some aggregation on individual elements in it.

Consider foldLeft:

fun <B> foldLeft(z: B, f: (B, A) -> B): B {
    tailrec fun foldLeft(l: List<A>, z: B, f: (B, A) -> B): B {
        return when (l) {
            is Nil -> z
            is Cons -> foldLeft(l.tail, f(z, l.head), f)
        }
    }
 
    return foldLeft(this, z, f)
}


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:

val l = Cons(1, Cons(2, Cons(3, Cons(4, Nil))))
assertThat(l.foldLeft(0, {r, e -> r + e})).isEqualTo(10)


foldRight looks like the following in Kotlin:

fun <B> foldRight(z: B, f: (A, B) -> B): B {
    return when(this) {
        is Cons -> f(this.head, tail.foldRight(z, f))
        is Nil -> z
    }
}


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:

fun reverse(): List<A> {
    return foldLeft(Nil as List<A>, { b, a -> Cons(a, b) })
}
 
fun <B> foldRightViaFoldLeft(z: B, f: (A, B) -> B): B {
    return reverse().foldLeft(z, { b, a -> f(a, b) })
}


map and flatMap

map is a function that transforms the elements of this list:

fun <B> map(f: (A) -> B): List<B> {
    return when (this) {
        is Cons -> Cons(f(head), tail.map(f))
        is Nil -> Nil
    }
}


An example of using this function is the following:

val l = Cons(1, Cons(2, Cons(3, Nil)))
val l2 = l.map { e -> e.toString() }
assertThat(l2).isEqualTo(Cons("1", Cons("2", Cons("3", Nil))))


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:

fun <B> flatMap(f: (a: A) -> List<@UnsafeVariance B>): List<B> {
    return flatten(map { a -> f(a) })
}
 
companion object {
    fun <A> flatten(l: List<List<A>>): List<A> {
        return l.foldRight(Nil as List<A>, { a, b -> a.append(b) })
    }
}
 
 
val l = Cons(1, Cons(2, Cons(3, Nil)))
 
val l2 = l.flatMap { e -> list(e.toString(), e.toString()) }
 
assertThat(l2)
        .isEqualTo(
                Cons("1", Cons("1", Cons("2", Cons("2", Cons("3", Cons("3", Nil)))))))


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.

Strategies and techniques for building scalable and resilient microservices to refactor a monolithic application step-by-step, a free O'Reilly book. Brought to you in partnership with Lightbend.

Topics:
java ,functional programming ,datastructure ,list ,kotlin ,scala ,tutorial

Published at DZone with permission of Biju Kunjummen, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}