Kotlin lists

Motivation

As we know, the builtin immutable list in Kotlin (listOf) is just a wrapper for a mutable array list, so any modification (cons, snoc) needs to copy the whole list. This is demonstrated by the following:

import kotlin.time.measureTime

fun buildBuiltinImmutableList(): List<Int> {
    var xs = listOf<Int>();
    for (i in 0..10000) {
        xs += i
    }
    return xs
}

fun buildBuiltinMutableList(): List<Int> {
    val xs = mutableListOf<Int>();
    for (i in 0..10000) {
        xs.add(i)
    }
    return xs
}


fun main() {
    val timeToBuildBuiltinImmutableList = measureTime {
        buildBuiltinImmutableList()
    }
    val timeToBuildBuiltinMutableList = measureTime {
        buildBuiltinMutableList()
    }
    println("Building builtin immutable list takes $timeToBuildBuiltinImmutableList")
    println("Building builtin mutable list takes $timeToBuildBuiltinMutableList")

    val builtinImmutableList = buildBuiltinImmutableList()
    val builtinMutableList = buildBuiltinMutableList()

    val timeToQueryBuiltinImmutableList = measureTime {
        builtinImmutableList.find { it == 99999 }
    }
    val timeToQueryBuiltinMutableList = measureTime {
        builtinMutableList.find { it == 99999 }
    }
    println("Traversing builtin immutable list takes $timeToQueryBuiltinImmutableList")
    println("Traversing a builtin mutable list takes $timeToQueryBuiltinMutableList")
}

On my machine:

Building builtin immutable list takes 144.462443ms
Building builtin mutable list takes 573.612us
Traversing builtin immutable list takes 873.863us
Traversing a builtin mutable list takes 741.721us

Ok, this is quite bad, we know that Haskell linked lists are quite fast when you do cons, so let's make one of that.

sealed interface LinkedList
data class Cons(val head: Int, val tail: LinkedList) : LinkedList
object Nil : LinkedList
// Equiv to data LinkedList = Nil | Cons Int LinkedList

infix fun Int.cons(xs: LinkedList) = Cons(this, xs)

fun buildImmutableList(): LinkedList {
    var xs: LinkedList = Nil
    for (i in 0..10000) {
        xs = i cons xs
    }
    return xs
}

Building builtin immutable list takes 110.702514ms
Building builtin mutable list takes 1.272172ms
Building immutable list takes 1.932318ms

We can see it's comparable to a mutable list, nice!

Is it good for traversal?

// Stackoverflow
fun LinkedList.find(pred: (Int) -> Boolean): Int? = when (this) {
    is Nil -> null
    is Cons -> if (pred(this.head)) head else tail.find(pred)
}

fun LinkedList.find(pred: (Int) -> Boolean): Int? = when (this) { 
tailrec fun LinkedList.find(pred: (Int) -> Boolean): Int? = when (this) { 

A bit worse, but comparable.

Traversing builtin immutable list takes 1.191294ms
Traversing a builtin mutable list takes 739.765us
Traversing immutable list takes 2.041619ms

But we remember that snoc is very expensive for linked lists, let's benchmark that.

infix fun Int.snoc(xs: LinkedList): LinkedList = when (xs) {
    is Nil -> Cons(this, Nil)
    is Cons -> Cons(xs.head, this snoc xs.tail)
}
fun buildImmutableListSnoc(): LinkedList {
    var xs: LinkedList = Nil
    for (i in 0..10000) {
        xs = i snoc xs
    }
    return xs
}

Oh no! It's 3 times slower than actually copying!

Building builtin immutable list takes 104.879966ms
Building builtin mutable list takes 710.013us
Building immutable list takes 911.997us
Building immutable list (snoc) takes 323.870489ms

Can we build an immutable list that has fast cons and snoc?

DList

Yes, and it's called a difference list

fun compose(
    f: (LinkedList) -> LinkedList,
    g: (LinkedList) -> LinkedList
): (LinkedList) -> LinkedList = { xs -> f(g(xs)) }

data class DList(val f: (LinkedList) -> LinkedList)
val DNil = DList({ it })

infix fun Int.cons(xs: DList) = DList(compose({ this cons it}, xs.f))
infix fun DList.append(other: DList): DList = DList(compose(f, other.f))
infix fun DList.snoc(x: Int): DList = this append (x cons DNil)

fun buildDList(): DList {
    var xs: DList = DNil
    for (i in 0..10000) {
        xs = i cons xs
    }
    return xs
}

fun buildDListSnoc(): DList {
    var xs: DList = DNil
    for (i in 0..10000) {
        xs = xs snoc i
    }
    return xs
}

Building builtin immutable list takes 103.096761ms
Building builtin mutable list takes 873.373us
Building immutable list takes 1.102246ms
Building immutable list (snoc) takes 339.708615ms
Building dlist takes 3.623470ms
Building dlist (snoc) takes 2.568577m

That's quite nice, but how do we actually inspect the data?

We turn it into a linked list and traverse that instead

fun DList.find(pred: (Int) -> Boolean): Int? = f(Nil).find(pred)

However:

Exception in thread "main" java.lang.StackOverflowError
	at org.example.ListsKt.compose$lambda$0(Lists.kt:55)
	at org.example.ListsKt.compose$lambda$0(Lists.kt:55)
	at org.example.ListsKt.compose$lambda$0(Lists.kt:55)

That's because on JVM, explicit stack calls are used, which causes stackoverflow. Haskell avoids this because Haskell doesn't really have a conventional stack (architecturally), there's a lot of heap allocation and jumping around pointers.

Curiously, this works on the JS backend.

Building builtin immutable list takes 578ms
Building builtin mutable list takes 0s
Building immutable list takes 0s
Building immutable list (snoc) takes 974ms
Building dlist takes 2ms
Building dlist (snoc) takes 1ms
Traversing builtin immutable list takes 0s
Traversing a builtin mutable list takes 0s
Traversing immutable list takes 1ms
Traversing dlist takes 3ms

Not great (JS probably doesn't optimize compose very well), but hey it works.

To do make it work on JVM, we essentially have to roll our own evaluation engine that can flatten lambdas. Like in scalaz.DList.