Defining a Generic Method in a Trait When Using Algebraic Data Type in Scala

Question

I have defined an abstract data type, and i wanted to make it fairly general and scalable.

However, scala type system is giving me a nightmare.

sealed trait Tree[+A] {
  def evaluateTree(): A = this match {
    case Leaf(value) => value
    case Branch_A1(op, left) => op(evaluateTree(left))
    case Branch_A2(op, left, right) => op(evaluateTree(left),evaluateTree(right))
  }
}
case object EmptyTree extends Tree[Nothing]
case class Leaf[A](value: A) extends Tree[A]
case class Branch_A1[A](op: A => A, left: Tree[A]) extends Tree[A]
case class Branch_A2[A](op: (A,A) => A, left: Tree[A], right: Tree[A]) extends Tree[A]

A would be e.g. Double. So in this case i have a tree which has branches that represent functions of one and two arguments (Branch_A1, Branch_A2)

However it does not compile. In op(evaluateTree(left)) it says that "it cannot resolve ... with such reference".

I could take the function away from the class into a more functional pattern but i want to do it following an object design. The only way i can get it into compiling is to do:

sealed trait Tree[+A] {
  def evaluateTree(t: Tree[A]): A = this match {
    case Leaf(value) => value
    case Branch_A1(op, left) => op(evaluateTree(left))
    case Branch_A2(op, left, right) => op(evaluateTree(left),evaluateTree(right))
  }
}
case object EmptyTree extends Tree[Nothing]
case class Leaf[A](value: A) extends Tree[A]
case class Branch_A1[A](op: A => A, left: Tree[A]) extends Tree[A]
case class Branch_A2[A](op: (A,A) => A, left: Tree[A], right: Tree[A]) extends Tree[A]

which is stupid since i need to pass it the instance of the object.

I need to tell the compiler that this is an Tree[A]. So i have tried:

sealed trait Tree[+A] {

  this: Tree[A] =>

  def evaluateTree(): A = this match {
    case Leaf(value) => value
    case Branch_A1(op, left) => op(evaluateTree(left))
    case Branch_A2(op, left, right) => op(evaluateTree(left),evaluateTree(right))
  }
}

Still the compiler does not let me go, the error is the same actually. How can i solve this??

Answer 1

It looks like your receivers are screwed up. evaluateTree does not take arguments. I'm assuming you want to evaluate the subtree, as in op(evaluateTree(left)) should instead be op(left.evaluateTree())

def evaluateTree(): A = this match {
  case Leaf(value) => value
  case Branch_A1(op, left) => op(left.evaluateTree())
  case Branch_A2(op, left, right) => op(left.evaluateTree(),right.evaluateTree())
}