Algebraic data types in Kotlin

Question

I am trying to figure out how to use algebraic data types in Kotlin, so I'm trying to implement a basic BinaryTree type the following way.

sealed class Tree<T>{
  class Node<T>(val left: Tree<T>, val right: Tree<T>): Tree<T>()
  class Leaf<T>(val value: T): Tree<T>()
}

This is all fine, and lets me construct the following tree:

val myTree1: Tree<Int> = Node(Leaf(4), Leaf(2))

However I would like to have an "Empty" type as well, so I can express the following:

val myTree1: Tree<Int> = Node(Node(Leaf(4), Leaf(3)), Empty)

I tried the following:

sealed class Tree<T>{
  class Node<T>(val left: Tree<T>, val right: Tree<T>): Tree<T>()
  class Leaf<T>(val value: T): Tree<T>()
  object Empty: Tree()
}

Though I get the error that Type argument is expected at object Empty: Tree(), which is actually quite logical.

I tried

object Empty: Tree<T>()

But it resulted in "Unresolved reference: T". As a last resort, I tried writing

object Empty<T>: Tree<T>()

But the compiler says "Type parameters are not allowed for objects"

Is there a way to express this in Kotlin? Empty should be a singleton, this is why it should be an object. By making it a class, it solves the compiler problems, but then I have to put parentheses after it like that => Empty(). Also, it creates unnecessary objects, while it really should be a singleton value.

I'd appreciate any help on this issue. :)

Answer 1

First you need to make T an out parameter. Then you can use Nothing as a type argument for Empty.

sealed class Tree<out T>{
  class Node<T>(val left: Tree<T>, val right: Tree<T>): Tree<T>()
  class Leaf<T>(val value: T): Tree<T>()
  object Empty: Tree<Nothing>()
}

Nothing is a special type in Kotlin, which cannot have an instance and is a subtype of all other types. So I would say it's opposite to Any in Kotlin type hierarchy.