How to correctly implement a polymorphic functional Tree data structure in Scala?

Question

I am trying to figure out the best way to implement a polymorphic tree:

trait Tree[A]

case object Void extends Tree[A]  // does not compile
case class Node[A](left: Tree[A], key: A, right: Tree[A]) extends Tree[A]

Surely I can change Void from an object to a class, or I can have it extend Tree[Any], but I was wondering what would be the textbook implementation of this Tree in Scala. Thank you!

Answer 1

• Either you make Tree covariant

trait Tree[+A]
case object Void extends Tree[Nothing]

(then Void is a subtype of Tree[A] for any A)

• or you keep Tree invariant and then make Void a class

trait Tree[A]
case class Void[A]() extends Tree[A]

Objects (and values generally) can't be polymorphic in Scala (and JVM).

Making Void extend Tree[Any] is incorrect. Then Void isn't a subtype of Tree[A].

In principle, if you can perform all calculations at compile time, then you can lift your algebraic data type to the type level making Tree a type class

trait Tree[A, T]

case object Void
type Void = Void.type
case class Node[A, L, R](left: L, key: A, right: R)

implicit def voidTree[A]: Tree[A, Void] = new Tree[A, Void] {}
implicit def nodeTree[A, L, R](implicit
  leftTree: Tree[A, L],
  rightTree: Tree[A, R]
): Tree[A, Node[A, L, R]] = new Tree[A, Node[A, L, R]] {}