CODEWITHSUNDEEP
scalabinary-treecovariance
user1639926
user1639926

Reputation: 862

scala binary tree, adding an element

I am trying to change my end nodes in my binary tree. How do I make the methods change_right_tree and change_left_tree?

The compiler is complaining that I am reassigning to val. But when I change things to var, I get covariant errors. 

sealed abstract class Tree[+T] {
}
case object End extends Tree[Nothing] {
  override def toString = "."
}

case class Node[+T](var question: String,  left: Tree[T] = End, right: Tree[T] = End) extends Tree[T] {
  override def toString = "T(" + question.toString + " " + left.toString + " " + right.toString + ")"

  def set_question(str : String) = {question = str}

  def get_answer(answer : Boolean) = {
    if (answer){
      left
    }else {
      right
    }
  }
  // unclear on what I need to do to make this work
  def change_left_tree( new_tree : Tree[T]) = {this.left = new_tree}
  def change_right_tree( new_tree : Tree[T]) = {this.right = new_tree}
}

Upvotes: 1

Views: 646

Answers (2)

rtruszk
rtruszk

Reputation: 3922

Solution: If you remove '+' from Node class declaration your code will compile.

Explanation:

When you declare class with covariant type [+T] then you can declare subclasses with narrower type. So Tree class has to be declared with covariant type to allow declaring case object End.

But declaring class Node with covariant type [+T] was incorrect when you wanted it to be mutable. To understand it better imagine for a moment that compiler didn't stop you and allowed you to compile following code (I removed other methods for simplicity of example):

case class Node[+T](var question: String, var left: Tree[T] = End, var right: Tree[T] = End)  extends Tree[T] {
    def change_left_tree( new_tree : Tree[T]) = {this.left = new_tree}
    def change_right_tree( new_tree : Tree[T]) = {this.right = new_tree}
}

Now you can do the following:

val stringNode:Node[String] = new Node("string node")
val intNode:Node[Int] = new Node("int node")
val anyNode:Node[Any] = stringNode
anyNode.change_left_tree(intNode)

And now Node[Int] is left node of Node[String]. So mixing covariance and mutability would break type safety.

Upvotes: 1

John Go-Soco
John Go-Soco

Reputation: 955

  1. In the definition of Node, the left and right properties are already defined as End.
  2. In the change_left_tree and change_right_tree methods, you're modifying the value of left and right instead of returning a new tree.
def change_left_tree( new_tree : Tree[T]): Tree = {
  new Tree (this.question, new_tree, this.right)

}

Upvotes: 0

Related Questions