How to call constructor for leaves of a tree algebraic data type in Scala?

Question

I'm creating some basic abstract data types and algorithms to brush up on my CS fundamentals, and learning Scala along the way. I'm running into trouble with my BinarySearchTree data type, which is an implementation of a more abstract BinaryTree:

abstract class BinaryTree[T](stored_value: T) { 
  var contents = stored_value
  var l: this.type = _
  var r: this.type = _
  ...
}

class BinarySearchTree[T <: Ordered[T]](stored_value: T) extends BinaryTree(stored_value) {  
  def insert(newval: T) {
    if (newval <= contents) {
      if (l == null) {
        throw new NotDefinedError("Still trying to work around type erasure.")
      } else {
        l.insert(newval)
      }
    } else {
      if (r == null) {
        throw new NotDefinedError("Still trying to work around type erasure.")
      } else {
        r.insert(newval)
      }
    }
  }

In the blocks that throw NotDefinedErrors, I've tried a few approaches like l = new this.type(newval), substituting this.type for BinarySearchTree[T] and anything else I can think of. Depending on how I try to express that type, I either get something like:

class type required but BinarySearchTree.this.type found

or:

type mismatch;  found   : trees.BinarySearchTree[T]  required: BinarySearchTree.this.type

Do I need to override l and r with a different type in the definition of BinarySearchTree? Or just call a different type of constructor when I'm attaching a new value to them? Or some other option?

Answer 1

I agree with @dhg's recommendation that you explore immutable tree data structures as an alternative to your current direction. However if a mutable tree is really what you need then read on ...

Your immediate problem is that this.type in the definition of BinaryTree[T] doesn't mean what you think it means. It's actually the singleton type of the enclosing instance, ie. the type which inhabited by this and nothing else. Here's an example illustrating that,

scala> class Foo { def self : this.type = this /* OK */ }
defined class Foo

scala> class Bar { def self : this.type = new Bar /* Does not compile */ }
<console>:7: error: type mismatch;
 found   : Bar
 required: Bar.this.type
       class Bar { def self : this.type = new Bar /* Does not compile */ }
                                          ^

This is obviously a much more specific type than the one you really want.

To fix the problem one option would be to weaken the types of l and r to BinaryTree[T], as in @dhg's answer. However, I think that what you were originally after when using this.type was for the tree nodes to be self-typed and so refined to BinarySearchTree[T] in the subclass. You can do this as you would in Java with a recursive type bound, or you can do it with an abstract type member like so,

abstract class BinaryTree[T] {
  type Self <: BinaryTree[T]
  var contents : T
  var l: Self = _
  var r: Self = _
}

class BinarySearchTree[T <: Ordered[T]](stored_value : T) extends BinaryTree[T] {
  type Self = BinarySearchTree[T]
    var contents = stored_value
    def insert(newval: T) {
      if (newval <= contents) {
        if (l == null) {
          new BinarySearchTree(newval)
        } else {
          l.insert(newval)
        }
      } else {
        if (r == null) {
          new BinarySearchTree(newval)
        } else {
          r.insert(newval)
        }
      }
  }
}

Answer 2

I would define it like this:

class BinaryTree[T](
  val item: T,
  val left: Option[BinaryTree[T]] = None,
  val right: Option[BinaryTree[T]] = None) {

  override def toString() = "Tree(%s,%s,%s)".format(item,left,right)
}

class BinarySearchTree[T: Ordering](
  override val item: T,
  override val left: Option[BinarySearchTree[T]] = None,
  override val right: Option[BinarySearchTree[T]] = None) extends BinaryTree[T](item, left, right) {

  def insert(newval: T): BinarySearchTree[T] = {
    val (newLeft, newRight) =
      if (implicitly[Ordering[T]].lteq(newval, item))
        (insertSubtree(newval, left), right)
      else
        (left, insertSubtree(newval, right))
    new BinarySearchTree(item, newLeft, newRight)
  }

  private def insertSubtree(newval: T, subtree: Option[BinarySearchTree[T]]) =
    Option(subtree
      .map(_.insert(newval))
      .getOrElse(new BinarySearchTree(newval, None, None)))
}

There are a few basic things that I have changed to be more Scala-like:

• Make the structure immutable by using all val fields. Have insert return a new, modified tree. Keep as much of the old (immutable) tree as possible to avoid wasting memory.
• Avoid using null by using Option instead. Thus, the left and right sub-trees are Option[Binary(Search)Tree[T]], indicating explicitly that they may or may not be present.
• Make use of map on the subtree since it is an Option. This code in insertSubtree basically says "If the subtree exists, insert into it. Or else, get a new tree."

Here's how it works:

scala> var t = new BinarySearchTree(5, None, None)
t: BinarySearchTree[Int] = Tree(5,None,None)

scala> t = t.insert(3)
t: BinarySearchTree[Int] = Tree(5,Some(Tree(3,None,None)),None)

scala> t = t.insert(4)
t: BinarySearchTree[Int] = Tree(5,Some(Tree(3,None,Some(Tree(4,None,None)))),None)

scala> t = t.insert(7)
t: BinarySearchTree[Int] = Tree(5,Some(Tree(3,None,Some(Tree(4,None,None)))),Some(Tree(7,None,None)))