i'm trying to write a binary tree in kotlin with `...

# announcements

[william]

i'm trying to write a binary tree in kotlin with

sealed class BinaryTree<T> {
    val root: BinaryTree<T> = Leaf
}

data class Node<T>(val data: T, val left: BinaryTree<T>, val right: BinaryTree<T>) : BinaryTree<T>()
object Leaf : BinaryTree<Nothing>()

can anyone help my understand why root: BinaryTree<T> = Leaf gives the error

Type mismatch.
Required:
BinaryTree<T>
Found:
Leaf

[william]

i'm guessing its any issue with Nothing ? but not really sure how to work around it

[ephemient]

try class BinaryTree<out T>

[ephemient]

by default, <T> is invariant: even if T : U, there is no relation between Binary<T> and Binary<U>

[ephemient]

with out, T : U implies Binary<T> : Binary<U>

[william]

that works 🙂 i still feel confused about in and out i've read through the kdocs a few times on it but it just hasn't sunk in

[ephemient]

interface Producer<out T> {
    fun produce(): T
}
var p: Producer<Number>
p = object : Producer<Int> // p.produce() is Number, OK
p = object : Producer<Any> // p.produce !is Number, NOT OK

interface Consumer<in T> {
    fun consume(t: T)
}
val t: Number = 0.toFloat()
var c: Consumer<Number>
c = object : Consumer<Any> // p.consume(t) OK
c = object : Consumer<Int> // p.consume(t) NOT OK

[Nir]

Making it out T has further implications here which you may or may not want, depends if your binary tree is read only (like List)

[william]

if i dont want that property what other options do i have?

[Nir]

All you really need to have a binary tree is change your Node definition to make left and right nullable Nodea

[Nir]

You don't need Leaf or BinaryTree

[Nir]

class Node<T>(val data: T, val left: Node<T>?, val right: Node<T>?)

[Nir]

Commonly for convenience you would have a BinaryTree class that has a Node as its member

[Nir]

But it's not necessary

[ephemient]

if you want a mutable tree, you can't use the same Leaf for every <T>.

[ephemient]

at least, you can't use the same type. you can use the same instance, if you do unchecked casts on it

[ephemient]

you can sort of imagine null as a singleton instance which is a T? for every possible T

[Nir]

I'm not sure if that's in reference to my solution or something previous

[Nir]

I guess the previous, nm

[ephemient]

well, it's sorta related. Node<T> : BinaryTree<T>, Leaf : BinaryTree<T> ≅ Node<T> : Node<T>?, null : Node<T>?

[ephemient]

the latter is what you recommended, it's definitely doable. the former only works if you give up on singleton-ness (e.g. Leaf<T>) or use unchecked casts