Non-Empty Lists in Kotlin

MARCH 29, 2021 | BALAZS TOTH

“What’s your favorite birthday present?” – This question only makes sense if you received at least one present. Otherwise, you might even perceive it as offensive. So before asking this question, we should better make sure that your list of received presents is non-empty! But let’s start from the beginning…

Surprises aren’t always nice… 🎁

As a Kotlin developer, you probably know this situation: You write a function that accepts an input parameter, but for some specific parameter values, the function cannot return a valid result. For example, the function

cannot return a valid result for x = 0.

As a concrete example in Kotlin, let’s have a look at the following average function, where we divide the sum of all elements in a list by the list’s size.

fun List<Int>.average() = sum() / size

Everything works perfectly well until someone calls this function on an empty list. Then suddenly, oh wonder, an arithmetic exception is thrown, and the execution of the program stops. It’s not the end of the world, but still pretty annoying. Especially when it’s not as obvious as in our example which input values are valid and which ones aren’t.

For example, would you be able to tell how valid input arguments look like for this weird looking signature?

fun request(
    codes: List<Int>, 
    identifier: List<String>, 
    options: List<String>
)

We have a few different options to avoid such unpleasant surprises:

1️⃣ Documentation

The first and probably easiest way would be to write a comment which specifies the valid inputs. But as we all know, consulting the documentation is not always the developer’s first approach. There might be too much to read or the documentation is unclear or even worse: out of date. So this is apparently not the best approach.

2️⃣ Construct a Result Type

Another way would be to construct a valid result for the invalid inputs. If our average example would operate on lists of Floats or Doubles instead of Ints, this would be the case automatically: The average of an empty list of Doubles would be NaN (not a number) – a built-in result value intended for such operations that cannot work on all inputs.

But there are two drawbacks to this solution: The first is that we still need to check how the result looks like. We need to handle situations where the result is irregular, like NaN. Secondly, most types, like the Ints in our example, don’t have such built-in values. So in most scenarios, we would need to construct a new result type, which contains the original one. This usually makes the API more difficult to use – especially when you expect a valid result in most cases. One way to implement such a result type is to make use of the generic Either type, which we explained in this article.

3️⃣ Restrict the Input

The best option usually is to restrict the input, so that no-one can call the function with values that would produce an invalid result. In order to achieve this, we can sometimes make use of Kotlin’s strong type system. For our list example, we could construct a new type NonEmptyList (a list which is guaranteed to never be empty) and then only define the average function on this new type as follows:

fun NonEmptyList<Int>.average() = sum() / size

Type safety for the win!🏆

With this mysterious NonEmptyList type, we make sure that there is always at least one element in the list. This way, there will always be a well-defined average. In other words: It’s impossible to compile a program where an invalid input is passed to our function.

nonEmptyListOf<Int>().average()    // ❌ Does not compile!
nonEmptyListOf(1, 2, 3).average()  // ✅ This does!

It’s also possible to first take the square of all values and then calculate the average of the resulting list. The squared list would still be a NonEmptyList – the non-emptiness invariant remains.

nonEmptyListOf(1, 2, 3)
    .map { value -> value * value }
    .average()

Now let’s imagine an online shop where you can put articles into a virtual shopping cart. When you have some articles in your cart, you should be able to share the articles with your friends, save them for later on a wish list or buy them directly. But these features only make sense when your shopping cart isn’t empty, right?

So what if we could prevent anyone from accessing these features with an empty shopping cart at compile-time? Turns out we can! This is how the code could look like:

sealed class ShoppingCart {
    object Empty : ShoppingCart()

    data class Filled(
        val articles: NonEmptyList<Article>
    ) : ShoppingCart() {

        fun buy(paymentType: PaymentType) = articles.buy(paymentType)
        fun share() = articles.share()
        fun saveTo(wishList: WishList) = articles.saveTo(wishList)
    }
}

fun NonEmptyList<Article>.buy(paymentType: PaymentType) { 💸 }
fun NonEmptyList<Article>.share() { 💬 }
fun NonEmptyList<Article>.saveTo(wishList: WishList) { 💾 }

ℹ️ If you want to learn more about sealed classes and interfaces, check out our article Kotlin’s Sealed Interfaces & The Hole in The Sealing.

Developers who implement buy, share and saveTo don’t have to handle the empty case. The consumers of these APIs don’t have to think of exception handling, because they are forced by the compiler to provide valid input. We would say, that’s a win-win situation! 🏆 Other collection types like sets or maps can have a non-empty implementation as well and be used in the same fashion as the non-empty lists.

If you like what you see and want to start making the world a little more type-safe right now, start experimenting right now with our Kotlin NonEmptyCollections repository. We already implemented all the basic non-empty collection types and wrapped the standard operators on them for you! If you’re excited to learn how we implemented non-empty collections under the hood, just bear with us and read on! 😉

NonEmptyCollections on GitHub

ℹ️ The concept of non-empty collections is widely known in many functional programming languages like Haskell. This is not surprising, since increased type-safety is one of the main arguments to choose a functional language. If you want to go all-in on functional programming in Kotlin, there is the Arrow library, which already contains non-empty collections as well. However, if you don’t want to change the whole architecture of your project and directly benefit from non-empty collections, our repository is most likely a good choice.

How does this work? 🔍

interface NonEmptyCollection<T> : Collection<T>

First, we define an interface NonEmptyCollection, which inherits the standard Kotlin Collection interface. We can directly deprecate some of the original interface’s functions which are no longer needed in case of non-empty collections. Like this, they won’t be shown in the auto-completion. For example, firstOrNull won’t ever be null because a non-empty collection always has a first element by definition.

interface NonEmptyCollection<T> : Collection<T> {

    @Deprecated(
        level = DeprecationLevel.ERROR,
        message = "Is never null!",
        replaceWith = ReplaceWith("first()")
    )
    fun firstOrNull(): T? = throw NotImplementedError()

    @Deprecated(
        level = DeprecationLevel.ERROR,
        message = "Alternative is never used!",
        replaceWith = ReplaceWith("first()")
    )
    fun firstOr(alternative: () -> T): T = throw NotImplementedError()

    @Deprecated(
        level = DeprecationLevel.ERROR,
        message = "Alternative is never used!",
        replaceWith = ReplaceWith("")
    )
    fun <R> ifEmpty(defaultValue: () -> R): R = throw NotImplementedError()
}

Non-Empty Lists 📝

So far, so good. But how can we implement the actual collection types? Let’s begin with the NonEmptyList! We can simply define a data class that has two internal properties: head and tail.

data class NonEmptyList<T> internal constructor(
    internal val head: T,
    internal val tail: List<T>
) :  NonEmptyCollection<T>, List<T>

The head is the first element of the list, enforcing that the list is never empty. The tail is a standard list that contains an arbitrary number of values (possibly zero). The class needs to implement two different interfaces: our NonEmptyCollection interface and the Kotlin List interface.

data class NonEmptyList<T> internal constructor(
    internal val head: T,
    internal val tail: List<T>
) :  NonEmptyCollection<T>, List<T> by listOf(head) as Collection<T> + tail

The little by-keyword allows us to use another instance that already implements a given interface in order to make our new class also implement it. All calls to the members of the interface will be delegated to the other instance.

How to create a NonEmptyList? 🛠️

We made the NonEmptyList‘s constructor internal, because we will implement similar factory functions as there are for normal lists. Instead of listOf, we’ll have nonEmptyListOf.

fun <T> nonEmptyListOf(value: T, vararg values: T) 
    = NonEmptyList(value, values)

This factory function works exactly the same as the original one. The only difference is that our implementation requires at least one element, followed by an arbitrary number of elements. For the latter one, we use the vararg keyword (just like the original function does). Similarly, we define also a nonEmptyListOfNotNull as an equivalent for listOfNotNull.

fun <T : Any> nonEmptyListOfNotNull(
    value: T,
    vararg values: T?
) = NonEmptyList(value, values.filterNotNull())

Plus, plus, plus ➕➕➕

It would be pretty inconvenient to always use the factory functions to convert a normal list to a non-empty list. Our helpers in need are a bunch of plus operator functions, which automatically provide us with a non-empty list if we add a value or another non-empty list to a normal list:

operator fun <T> NonEmptyList<T>.plus(other: List<T>) = copy(
    tail = tail as Collection<T> + other
)

operator fun <T> List<T>.plus(
    other: NonEmptyList<T>
): NonEmptyList<T> = other.copy(
    head = this.firstOrNull() ?: other.head,
    tail = (this as Collection<T> + other).drop(1)
)

The two operations to add a normal list to a non-empty list are used as the base functions. They work as expected, except that we have to explicitly tell the compiler that we want to use the standard Kotlin Collection addition and not one of our newly created additions for creating the tail of the non-empty list. This can be achieved through a simple cast to Collection.
Based on these two operations, we can also mimic all the other list plus operations from the standard library, while keeping the non-empty invariant.

Look at all my fancy operators! 👸

List operators like map or scan let us write more concise code. It would be a pity if we couldn’t use them for our non-empty lists, too. At the current stage, we would need to create new non-empty lists after any of the operators, manually. That sounds like a lot of unnecessary work, doesn’t it?
For that reason, we create a bunch of wrapOperator functions. They might look a bit scary at first sight due to all the generics. But worry not! It’s not as complicated as it looks! 😉

inline fun <InputType, OutputType> 
    NonEmptyCollection<InputType>.wrapOperator(
        operator: Iterable<InputType>.() -> List<OutputType>,
    ): NonEmptyList<OutputType> 
    = wrapOperator(Unit, operator.addUnitParameter())

inline fun <InputType, Parameter, OutputType> 
    NonEmptyCollection<InputType>.wrapOperator(
        parameter: Parameter,
        operator: Iterable<InputType>.(Parameter) -> List<OutputType>
    ): NonEmptyList<OutputType> 
    = wrapOperator(parameter, Unit, operator.addUnitParameter())

inline fun <InputType, FirstParameter, SecondParameter, OutputType>
    NonEmptyCollection<InputType>.wrapOperator(
        firstParameter: FirstParameter,
        secondParameter: SecondParameter,
        operator: Iterable<InputType>.(FirstParameter, SecondParameter)
            -> List<OutputType>
    ): NonEmptyList<OutputType> 
    = operator(firstParameter, secondParameter).toNonEmptyList()

These functions all have generics for the input and output type of the operation, and for its parameters. We have three different wrap operators for zero, one or two parameters, because all list operators of the standard library have zero, one or two parameters.

The functions accept the parameters and the operator which should be wrapped and return the same operation for non-empty lists. The actual implementation lies in the function with the two parameters, where we execute the operation with the specified parameters and then create a non-empty list from the result. The other two functions simply add an extra unit parameter to the operation, which does nothing and propagates it to the next-bigger function.

Attention! You enter an unsafe area! ⚠️ ☠️

One problem arises from generic operators: We don’t know if the operator will really keep our non-empty invariant. map for example will always keep this invariant, since it is just applying a function to every element of the list. filter, on the other hand, could return an empty list when all elements are filtered out. At this point, we have to trust the user of the function that they passed a correct operator and forcefully convert the list to a non-empty list:

fun <T> Iterable<T>.toNonEmptyList(): NonEmptyList<T> 
    = nonEmptyListOf(first(), drop(1))

Sounds a bit dangerous? Agreed! That’s why we create an annotation UnsafeNonEmptyCollectionApi which signalizes the user that they enter an unsafe area and need to think carefully about what they do:

@RequiresOptIn
annotation class UnsafeNonEmptyCollectionApi

We specify that the annotation requires an opt-in, meaning that the user of the API needs to explicitly mark their code and thereby acknowledge that they read the warning sign. We then mark all our unsafe APIs with this annotation:

@UnsafeNonEmptyCollectionApi
inline fun <InputType, OutputType>
    NonEmptyCollection<InputType>.wrapOperator(
        operator: Iterable<InputType>.() -> List<OutputType>,
    ): NonEmptyList<OutputType> 
    = wrapOperator(Unit, operator.addUnitParameter())

...

@UnsafeNonEmptyCollectionApi
fun <T> Iterable<T>.toNonEmptyList(): NonEmptyList<T> 
    = nonEmptyListOf(first(), drop(1))

With this setup, we can now go and carefully wrap all the invariant-keeping operators of the standard library. Here’s the map-operator, for example:

@OptIn(UnsafeNonEmptyCollectionApi::class)
fun <T, R> NonEmptyCollection<T>.map(
    transform: (T) -> R
) = wrapOperator(transform, Iterable<T>::map)

The same concept can also be applied to user-defined operators, of course:

@OptIn(UnsafeNonEmptyCollectionApi::class)
fun <T, R> NonEmptyCollection<T>.someFancyOperator(
    myParameter: (T) -> R
) = wrapOperator(myParameter, Iterable<T>::someFancyOperator)

And what about sets and maps? 🤔

The procedure we described above for lists can be applied to sets and maps with little variations. We’ll skip that part in this article to not repeat ourselves and give you the opportunity to try implementing it by yourself if you want to. However, we have all the functions you need ready for you in our NonEmptyCollections repository. Just have a look at the code inside that repo for more details.