Scala correct null value definition for abstract data type

Question

I have an 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 EmptyTree, the type system does not skip

  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) 

mostly in create(EmptyTree, currentDepth + 1)he complains that he expects Tree[A]and receivesEmptyTree.type

Answer 1

The compiler’s objection is justified. The compiler expects Tree[A], and you pass EmptyTree, whose super type Tree[Nothing]. A priori, there is no subtyping between the two types.

, Tree : if X <: Y then Tree[X] <: Tree[Y]. , Nothing <: A A, EmptyTree.type <: Tree[A], EmptyTree, Tree[A].

A Tree Tree[+A]; , .

Scala:

Tree , , Tree . , ( , ). op Node Seq[A], Node. :

Node? , Tree !

, Tree Node, . scalac , () ( ). , , , :

// 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 {})

2. :) Tree case EmptyTree[A](); , .

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 {})