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
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 wantTree
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 {})
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With