How to get objects in invariant generic sealed classes?

Support
1

Say we want to implement trees in the spirit of abstract data types. This works fine:

sealed class Tree() {
    data class Node(var value: Int,
                    var left: Tree = None,
                    var right: Tree = None): Tree()
    object None: Tree()
}

However, if we want to make Tree generic, we get into trouble:

sealed class Tree<T>() {
    data class Node<T>(var value: T,
                       var left: Tree<T> = None,
                       var right: Tree<T> = None): Tree<T>()
    object None: Tree<???>()
}

We can’t leave out the type parameter for None, so what to put there?

  • We can not make None generic.

  • Nothing only works if we declare Tree<out T> and make the tree immutable. That’s fine for some use cases, but not for others.

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

  • We can make None a (generic) class. That creates lots of instances that we would hope to avoid.

    sealed class Tree<T>() {
  data class Node<T>(var value: T,
                     var left: Tree<T> = None(),
                     var right: Tree<T> = None()): Tree<T>()
  class None<T>: Tree<T>()
}

Of course, we could in this case change the design and use optional left/right together with Leaf instead of None (or a larger list of “cases”). The general issue/question remains, though.

Is there a way, ideally idiomatic, to go about modelling singletons in invariant generic sealed classes?

PS: It seems ironic that the JVM would be perfectly happy with None having basic type Tree, if I’m not missing something.

PPS: I’m not sure what kind of questions would be more at home on SO. Please advise.

1 Like
2

It seems possible to hack together a type-wise-singleton class:

sealed class Tree<T: Any>() {
    data class Node<T: Any>(var value: T,
                       var left: Tree<T> = None(value),
                       var right: Tree<T> = None(value)): Tree<T>()

    class None<T: Any> private constructor (): Tree<T>() {
        internal companion object {
            private var instances: MutableMap<Any, Any> = mutableMapOf()

            operator fun <U: Any> invoke(witness: U): None<U> {
                return instances.getOrPut(witness::class, { None<U>() }) as None<U>
            }
        }
    }
}

While certainly not pretty, it gives me some hope that maybe generic objects could be provided as compiler sugar.

1 Like