scala properly defining a empty value for a abstract data type

Question

I have a ADT as follows:

sealed trait Tree[A]
case object EmptyTree extends Tree[Nothing]
case class Leaf[A](value: A) extends Tree[A]
case class Node[A](op: Seq[A] => A, branches: Tree[A]*) extends Tree[A]

When i try to build a function to randomly create Trees i get a problem with the EmptyTree, the type system does not let go through

  def create(acc: Tree[A], currentDepth: Int): Tree[A] = currentDepth match {
    case maxDepth => Leaf(terminalSet(r.nextInt(terminalSet.length)))
    case 0 => {
      val op_pos = r.nextInt(fSetLength)
      val branches: Seq[Tree[A]] = for (i <- 0 to r.nextInt(fSetLength)) yield create(EmptyTree, currentDepth+1)
      Node(functionSet(op_pos)._1, branches:_*)
    }
    case _ => {
      if (r.nextFloat() <= probF) {
        val op_pos = r.nextInt(fSetLength)
        val branches = for (i <- 0 to r.nextInt(fSetLength)) yield create(EmptyTree, currentDepth + 1)
        Node(functionSet(op_pos)._1, branches:_*)
      }
      else
        Leaf(terminalSet(r.nextInt(terminalSet.length)))
    }
  }
  create(EmptyTree, 0) 

basically in create(EmptyTree, currentDepth + 1) it complains that it is expecting a Tree[A] and is receiving a EmptyTree.type

Answer 1

The compiler objections are justified. The compiler expects Tree[A] and you are passing EmptyTree, whose super type is Tree[Nothing]. A priori, there's no subtyping relationship between these two types.

What you want is Tree to be covariant: if X <: Y then Tree[X] <: Tree[Y]. Then, as Nothing <: A for any A you get EmptyTree.type <: Tree[A] and you can always pass EmptyTree whenever you need a Tree[A].

The syntax for declaring the A parameter in Tree covariant is Tree[+A]; change that and your code should compile.

This is a good post on covariance and contravariance in Scala: Be friend with covariance and contravariance

UPDATE After your questioning answer I have actually looked at your constructors for Tree and, as defined, you cannot make Tree covariant. Sadly, the compiler won't complain (you see, it should actually complain more). Your op in Node is contravariant on Seq[A], and thus you cannot make Node covariant. At this point you might be thinking:

Who cares about Node? I just want Tree to be covariant!

Well, through making its supertype Tree covariant Node becomes so in practice. scalac should actually check that all sub type constructors of a covariant one are (or could be made) covariant. Anyway, code showing this follows:

// you need a value for EmptyTree! thus default
def evaluateTree[Z](tree: Tree[Z], default: Z): Z =
  tree match {
    case EmptyTree    => default
    case Leaf(value)  => value
    // note how you need to essentially cast here
    case Node(op: (Seq[Z] => Z), args @ _*) =>
      op(args map { branches => evaluateTree(branches, default) })
  }

trait A
trait B extends A

val notNice: Tree[A] = Node[B]({ bs: Seq[B] => bs.head }, EmptyTree)
// ClassCastException!
val uhoh = evaluateTree(notNice, new A {})

UPDATE 2 Back to your original question :) I'd leave your Tree type invariant, and have an EmptyTree[A]() case class; it is a pity that there are no parameterless value classes.

sealed trait Tree[A]
case class EmptyTree[A]() extends Tree[A]
case class Leaf[A](value: A) extends Tree[A]
// I wouldn't use varargs here, make a method for that if you want
case class Node[A](op: Seq[A] => A, branches: Tree[A]*) extends Tree[A]
// for convenience, it could be inside `Tree` companion
def emptyTree[A]: EmptyTree[A] = EmptyTree()

def evaluateTree[Z](tree: Tree[Z], default: Z): Z =
  tree match {
    case EmptyTree() =>
      default
    case Leaf(value) =>
      value
    // no need to match generic types or anything here
    case Node(op, args @ _*) =>
      op(args map { branches => evaluateTree(branches, default) })
  }

trait A
trait B extends A

// doesn't work now
// val notNice: Tree[A] = Node[B]({ bs: Seq[B] => bs.head }, emptyTree)
val notNice: Tree[B] = Node[B]({ bs: Seq[B] => bs.head }, emptyTree)

// doesn't compile, no class cast exception
// val uhoh = evaluateTree(notNice, new A {})