Does Kotlin have functional List data structure?

Question

Scala, for example, has functional List data structure that has O(1) for adding new item on head with Cons(::) operator.

But, + operator of List in Kotlin works in that it creates new list object bigger-sized by 1 and copies all original items to it, adds new item, and returns it. So addition operation takes O(N).

Is there any immutable List data structure with O(1) for append in Kotlin?

Answer 1

No, the kotlin standard library does not have that. You can write your own cons list though.

but I don't want to write all of the util functions for that by myself, for example reduce/fold/map/take/drop/max/sum....

You can get those functions for free just by implementing Iterable. For a cons list, this is easy to do:

sealed class ConsList<out T>: Iterable<T> {
    object Nil : ConsList<Nothing>() {
        override fun iterator() = object : Iterator<Nothing> {
            override fun hasNext() = false
            override fun next() = throw NoSuchElementException()
        }
    }

    data class Cons<out T>(val element: T, val rest: ConsList<T>): ConsList<T>() {
        override fun iterator() = iterator {
            yield(element)
            yieldAll(rest)
        }

    }
}

Note that implementing List involves quite a lot more code, especially the listIterator and sublist methods. You could use the some of the default AbstractList implementations, but it wouldn't be terribly efficient.