Implementing a Binary Tree in Scala

Question

I'm having difficulty setting up a Binary Tree in Scala. It will have to be covariant of it's type parameters (to allow a null-tree type), and its type for its key will need to be a sub class of Ordered, to allow for comparisons against other keys. This is what I have so far:

package tutorial

class AbTree[+K <: Ordered[K],+V] {
    def throwTreeException(msg:String) = throw new
            Exception("TreeException: " + msg)

    def replaceL[L >: K, W >: V](nTree:AbTree[L,W]): AbTree[L,W] = this match {
        case ETree => throwTreeException("replaceL called on an ETree")
        case tree:Tree[L,W] => tree.copy(lTree = nTree)
    }

    def replaceR[L >: K, W >: V](nTree:AbTree[L,W]): AbTree[L,W] = this match {
        case ETree          => throwTreeException("replaceR called on an ETree")
        case tree:Tree[L,W] => tree.copy(rTree = nTree)
    }

    def insert[L >: K, W >: V](nK:L,nV:W): AbTree[L,W] = this match {
        case ETree => Tree(nK,nV)                                           //Line 18
        case Tree(k,v,lT,rT) =>
            if (nK < k) replaceL(lT.insert(nK,nV))
            else if (nK > k) replaceR(rT.insert(nK,nV))                     //Line 21
            else Tree(k,v,lT,rT)
    }
}

case class Tree[+K <: Ordered[K],+V]
    (key:K,value:V,lTree:AbTree[K,V] = ETree,rTree:AbTree[K,V] = ETree)
    extends AbTree[K,V]

case object ETree
    extends AbTree[Nothing,Nothing]

which gives me 6 errors across insert:

- Line 18: inferred type arguments [L,W] do not conform to method apply's type parameter bounds [K <: Ordered[K],V] Error occurred in an application involving default arguments.
- Line 18: type mismatch;  found   : L  required: K Error occurred in an application involving default arguments
- Line 18: type mismatch;  found   : tutorial.Tree[K,V]  required: tutorial.AbTree[L,W] Error occurred in an application involving default arguments.
- Line 18: type mismatch;  found   : W  required: V Error occurred in an application involving default arguments.
- Line 20: value < is not a member of type parameter L
- Line 21: value > is not a member of type parameter L

This is only one combination of type bounds that I tried. I've gotten so many errors pushing through this that I don't know which ones are the real problem, and which are caused by other issues; so I don't know where to begin.

I'm guessing there's a huge hole in my understanding somewhere. Can someone please point out what's the primary problem with what I have above?

I may be saying something very stupid as I haven't played with type bounds in a long time, but shouldn't your replace/insert methods have type signature: insert[L <: K, W <: V]? I mean, if your tree has keys of type "animal" you can insert a "dog" (subtype) key, but if you have a key of "dogs" you don't want to insert any supertype of it such as "mammal". — Diego Martinoia
– Diego Martinoia, Commented Dec 15, 2014 at 18:07
Ya, in retrospect, this wasn't the best attempt to show. I tried that, and got a different more cryptic error, so I decided to just show generally what I'm trying to achieve, and see if anyone can help. I'll try changing those back and see what I get. — Carcigenicate
– Carcigenicate, Commented Dec 15, 2014 at 18:10
I might need to solidify my knowledge type bounds first. I'm starting to second-guess what I "know" :/ — Carcigenicate
– Carcigenicate, Commented Dec 15, 2014 at 18:59
For the immediate problems: L is not necessarily Ordered because you only required L >: K, i.e. any supertype of K. And I'm not sure the < syntax works for general comparisons (though maybe it's pimped on by something to do with Ordered?) — lmm
– lmm, Commented Dec 15, 2014 at 19:58
@lmm < and > are part of Ordered. They just aren't working now because, as you pointed out, the signature is wonky. — Carcigenicate
– Carcigenicate, Commented Dec 15, 2014 at 20:31

Rado Buransky · Accepted Answer · 2014-12-15 20:43:11Z

1

Take this as an inspiration. Take a look at the implementation of the Map in Scala. Key type is not covariant, value type is. Perhaps it makes more sense to define isEmpty method rather than pattern matching an object.

class AbTree[K, +V](implicit ordering: Ordering[K]) {
  def throwTreeException(msg:String) = throw new
      Exception("TreeException: " + msg)

  def replaceL[W >: V](nTree:AbTree[K, W]): AbTree[K, W] = {
    val empty = AbTree.empty[K, V]
    this match {
      case `empty` => throwTreeException("replaceL called on an ETree")
      case tree:Tree[K, W] => tree.copy(lTree = nTree)
    }
  }

  def replaceR[W >: V](nTree:AbTree[K, W]): AbTree[K, W] = {
    val empty = AbTree.empty[K, V]
    this match {
      case `empty`          => throwTreeException("replaceR called on an ETree")
      case tree:Tree[K, W] => tree.copy(rTree = nTree)
    }
  }

  def insert[W >: V](nK:K,nV:W): AbTree[K,W] = {
    val empty = AbTree.empty[K, V]
    this match {
      case `empty` => Tree(nK, nV) //Line 18
      case Tree(k, v, lT, rT) =>
        if (ordering.compare(nK, k) < 0) replaceL(lT.insert(nK, nV))
        else if (ordering.compare(nK, k) > 0) replaceR(rT.insert(nK, nV)) //Line 21
        else Tree(k, v, lT, rT)
    }
  }

}

object AbTree {
  implicit private object NothingOrdering extends Ordering[Any] {
    override def compare(x: Any, y: Any): Int = 0
  }
  private object ETree extends AbTree[Any, Nothing]

  def empty[K, V]: AbTree[K, V] = ETree.asInstanceOf[AbTree[K, V]]
}

case class Tree[K, +V](key:K,
                       value:V,
                       lTree:AbTree[K,V] = AbTree.empty[K, V],
                       rTree:AbTree[K,V] = AbTree.empty[K, V])
                      (implicit ordering: Ordering[K]) extends AbTree[K,V]

answered Dec 15, 2014 at 20:43

Rado Buransky

3,29420 silver badges27 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Carcigenicate Over a year ago

Thanks. I'm confused by a couple parts though. What does the explicit in the class declaration do? Why did you create a empty method instead of using a case object? Is it to get around both parameters needing to be covariant? I also have never seen asInstanceOf before, so I'll have to look into that. Doesn't this seem a little overly complicated? I could have written an entire tree implementation in Haskell in the amount of space needed above for the class definitions and insert method.

Rado Buransky Over a year ago

implict is a complicated thing, but in this case it means that Scala compiler will try to find an ordering in the current scope suitable for the type and it will provided that argument for you. asInstanceOf is just an explicit type casting to fool the compiler. The empty method is just a "copy&paste" of how Scala's Map deals with this issue. I know it's not an answer, but maybe you get some ideas. Good luck.

Carcigenicate Over a year ago

Thank you. I didn't mean to sound unappreciative.

Carcigenicate Over a year ago

Sorry, hopefully over last thing, where will it find the "ordering"? I looked up implicit, and have a basic understanding of it, but don't understand where it will find the instance. I doubt the user of the Map would be required to supply it, so is it supplied through some auto-import?

Collectives™ on Stack Overflow

Implementing a Binary Tree in Scala

1 Answer 1

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related