Kotlin prepend element

Question

I am searching for Kotlin alternative to:
(cons 1 '(2 3)) in lisp or
1 : [2, 3] in haskell or
1 :: List(2, 3) in scala,
(which all result in sth like [1, 2, 3])
so I can prepend an element to a List<T> (or any other list you can offer).

It will also be fine if one could provide O(1) head and tail Kotlin alternatives (I've found just first())

Echoism

Are lists linked? It can be an expensive operation to prepend if the structure isn't made for it. – Copolymer

@Copolymer They should be Kotlin Standart Library. – Echoism

@Echoism "They should be [linked lists]" - why do you think so? Kotlin's stdlib uses linked lists very rarely. The link you provided has no info on the issue. – Lipkin

check this for the mutable list: https://mcmap.net/q/409698/-what-is-the-best-way-to-add-an-element-to-the-beginning-of-a-list-in-kotlin – Interlace

Answer 1

Any class which implements Deque will suitable for you, for example LinkedList:

val linkedList = LinkedList(listOf(2, 3))
linkedList.push(1)
println(linkedList) // [1, 2, 3]

Creating lists throught constructor LinkedList(listOf(2, 3)) in many places can be annoying, so feel free to write factory method:

fun <T> linkedListOf(vararg elements: T): LinkedList<T> {
    return LinkedList<T>(elements.toList())
}

// Usage:
val list = linkedListOf(2, 3)
list.push(1)
println(list) // [1, 2, 3]

Lodmilla

Is there any method to actually return new List? push will change the list, I don't want that – Echoism

@Echoism For now you have to use third-party collection library to get efficient immutable collections – Lodmilla

Answer 2

I think the easiest would be to write:

var list = listOf(2,3)
println(list) // [2, 3]
list = listOf(1) + list
println(list) // [1, 2, 3]

There is no specific tail implementation, but you can call .drop(1) to get the same. You can make this head\tail more generic by writing these extension properties:

val <T> List<T>.tail: List<T>
  get() = drop(1)

val <T> List<T>.head: T
  get() = first()

Then:

val list = listOf(1, 2, 3)
val head = list.head
val tail = list.tail

Some more info: Kotlin List tail function

Ginter

Beware that performance would suffer as Kotlin lists are not optimized for such operations unlike Scala ones. – Convulsion

Answer 3

Simple, just wrap the element to prepend in a List and then use the + operator (or List.plus()) to concatenate the two Lists:

val list1 = listOf(2, 3)        // [2, 3]
val list2 = listOf(1) + list1   // [1, 2, 3]

For your second question, in Kotlin 1.2 there are:

List.first()
List.last()

Both are O(1)

Yclept

Answer 4

This could be done easily with extension functions as below

Prepending element

fun <T> MutableList<T>.prepend(element: T) {
    add(0, element)
}

Prepending list

fun <T> MutableList<T>.prependAll(elements: List<T>) {
    addAll(0, elements)
}

Sport

Answer 5

Inserts an element into the list at the specified index.

abstract fun add(index: Int, element: E)

Thus answer is

list.add(0,element)

Inactive

Answer 6

If you do that often in your code for some reason, consider adding an extension operator method such as:

operator fun <T> T.plus(tail: List<T>): List<T> {
    val list = ArrayList<T>(1 + tail.size)

    list.add(this)
    list.addAll(tail)

    return list
}

Then your code could work Scala-like: 1 + listOf(2, 3)

Another way to achieve the same behaviour, shorter but sacrifices some memory:

operator fun <T> T.plus(tail: List<T>): List<T> {
    return mutableListOf(this).apply {
        addAll(tail)
    }
}

Turenne

This is really nice and what I was expecting Kotlin to have since I also know Scala. It seems like a very natural way to write code being able to append / prepend a single item to a collection. – Rubescent

Answer 7

To be as close to Lisp as possible consider using immutable linked list.

You can use pcollections

val list = ConsPStack.from(listOf(2, 3))
val newList = list + 1
println(list)  // [2, 3]
println(newList) // [1, 2, 3]

Head:

list.first() // 1
list[0] // 1

(unfortunately this thing needs one allocation)

Tail:

list - 0 // [2, 3]
list.subList(1) // [2, 3]  

Looks rather ugly.

Hopefully we'll get better API when kotlinx.collections.immutable will be ready. It's an effort to create standard Kotlin immutable collections (not just read-only ones that we currently have). As of now this project is still at very early stage (I was unable to find structure that supports efficient prepend/head/tail there)

Blankly

Answer 8

I'm not entirely sure what you want to do, so please try one of the following.

Mutating list:

val list = mutableListOf(3, 2)
list.add(1)

Copping an immutable list:

var list = listOf(3, 2)
list = list + 1

Lipkin

prepend an element, not append – Echoism

Ya, this doesn't really answer the question. – Copolymer

In Haskell the most efficient operation is prepending, so that is what people do. In Kotlin appending is more efficient in most cases, that's why it is much more common. – Lipkin

I don't see a big philosophical difference between prepending and appending. If you use a list as a stack (as you do in Haskell), then you get the same result regardless of the end of the list you use. The order changes, but who cares. – Lipkin