Kotlin List tail function

Question

I am trying to find a tail function in List<T> but I couldn't find any. I ended up doing this.

fun <T> List<T>.tail() = this.takeLast(this.size -1)

Is there a better way to do this?

Heart

Answer 1

Kotlin doesn't have a built-in List<T>.tail() function, so implementing your own extension function is the only way. Although your implementation is perfectly fine, it can be simplified a bit:

fun <T> List<T>.tail() = drop(1)

Or, instead of extension function, you can define an extension property:

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

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

And then use it like:

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

Ardent

If you have a case where you do not want to copy the list (which is fine in many cases, CPU cache and smaller lists are fine) then look at Java standard sublist for a variation of the extension docs.oracle.com/javase/7/docs/api/java/util/… (as per @hotkey in a comment below) – Dzoba

If you want to emulate val head :: tail = List(1,2,3), you could write following extension function: fun <T> List<T>.headTail() = first() to drop(1) => val (head, tail) = listOf(1,2,3).headTail() – Hoenack

Answer 2

Yours and @Vladimir Mironov 's solutions will work, but they automatically create eager copies of the original list (sans the first element), which can take a very long time for larger lists. I would define it with a wrapper List class that delegates its methods to the wrapped one, ignoring the first element using index adjustments:

private class TailList<T> (private val list: List<T>) : List<T> {
    override val size: Int
        get() = list.size -1

    override fun isEmpty(): Boolean = size == 0

    override fun iterator(): Iterator<T> = listIterator()
    override fun listIterator(): ListIterator<T> = list.listIterator(1)
    override fun listIterator(index: Int): ListIterator<T> = list.listIterator(index + 1)
    override fun subList(fromIndex: Int, toIndex: Int): List<T> = list.subList(fromIndex + 1, toIndex + 1)
    override fun lastIndexOf(element: T): Int = list.lastIndexOf(element) - 1
    override operator fun get(index: Int): T = list[index + 1]

    // The following member functions require the copy of a new list
    override fun containsAll(elements: Collection<T>): Boolean = tailList.containsAll(elements)
    override fun contains(element: T): Boolean = tailList.contains(element)
    override fun indexOf(element: T): Int = tailList.indexOf(element)

    private val tailList by lazy { ArrayList(this) }  // makes a proper copy the elements this list represents
}

You may notice the functions in the section after the comment still end up making an eager copy. I only did this for simplicity's sake. For memory's sake, I made a lazy tailList property

They could all be implemented by iterating over the collection manually, rather than doing some sort of delegating. If that's what you'd prefer, I'm sure you can figure it out.

With that, the head and tail properties become this:

val <T> List<T>.tail: List<T> 
    get() =
        if(this.isEmpty())
            throw IllegalStateException("Cannot get the tail of an empty List")
        else
            TailList(this)

val <T> List<T>.head: T
    get() = this[0]  // or first()

If you really need it, I can add an update to make the last three member functions so that they don't make eager copies.

EDIT: Note: If you followed the conventions that Kotlin has followed so far, you wouldn't make the List's tail be lazy, like this, since all of their functions on List make eager copies. Instead, especially if you're using head and tail to recursively iterate over a list, I would see if you could attempt this wrapper idea on Sequence somehow. Sequence's whole point of existence is for lazy work on collections.

EDIT 2: Apparently sublist() creates a view, and is therefore already lazy. Essentially, I've just taught you how to create the implementation for sublist, except I narrowed it to only the tail.

So, in that case just use sublist() for your tail function.

Extemporize

Why not just use Java's sublist? It does exactly the same, it creates a view of the original list. docs.oracle.com/javase/7/docs/api/java/util/… – Headachy

Isn't this what Sequences are for? – Sarre

@Headachy I didn't realize sublists were views. Good to know. – Extemporize

@Krill Rakhman Yes, hence the edit note. But just because Sequences are specifically for lazy operations, it doesn't mean you can't be lazy elsewhere. – Extemporize

Answer 3

If working with non mutable lists, it is perfectly safe, and less memory consuming, to use simply :

fun <T> List<T>.tail(): List<T> =
    if (isEmpty()) throw IllegalArgumentException("tail called on empty list")
    else subList(1, count())

Kokanee

Seems a bit embarrassing that this isn't a built-in part of the API in Kotlin... hard to take a functional language seriously without car/cdr head/tail... – Lizzielizzy

Answer 4

If you need both head and tail (which is a basic sequence operation) and don't eagerly consumed stream, you might want to have a sequence.

fun <T> Sequence<T>.headTail() =
    HeadTailSequence(this)
        .let { it.head to it.iterator.asSequence() }

private class HeadTailSequence<T>(parent: Sequence<T>) : Sequence<T> {
    val iterator = parent.iterator()
    val head: T? = iterator.next()

    override fun iterator(): Iterator<T> {
        return object : Iterator<T> {
            override fun hasNext(): Boolean = iterator.hasNext()
            override fun next(): T = if (iterator.hasNext()) throw NoSuchElementException() else iterator.next()
        }
    }
}

An extention for Iterable can be done in a similar manner.

Backfire