Idiomatic Scala Generics

Question

I'm working on some Scala problems given here, specifically:

sealed abstract class Tree[+T]
case class Node[+T](value: T, left: Tree[T], right: Tree[T]) extends Tree[T] {
  override def toString = "T(" + value.toString + " " + left.toString + " " + right.toString + ")"
}
case object End extends Tree[Nothing] {
  override def toString = "."
}
object Node {
  def apply[T](value: T): Node[T] = Node(value, End, End)
}

While implementing an insert into a height balanced tree I have the following function:

def insert(node: Tree[Char], value: Char): Tree[Char] = {
    if(node.eq(End)){
      Node(value,End,End)
    }
    else{
      val internalNode = node.asInstanceOf[Node[Char]]
      if(internalNode.left.height == internalNode.right.height){

          if(Random.nextBoolean()){ //choose left
            internalNode.left = insert(internalNode.left,value)
          }else{
            internalNode.right = insert(internalNode.right,value)
          }

      }
      else if(internalNode.left.height > internalNode.right.height){ //insert into right
          internalNode.right = insert(internalNode.right,value)
      }
      else{ //insert into left
          internalNode.left = insert(internalNode.left,value)
      }
      internalNode
    }

  }

Could you please let me know how I could improve this code.

• Is there a way I can avoid doing the casting in asInstanceOf?

• How can I improve the if else checks?

General feedback is also much appreciated.

Answer 1

When you feel yourself going to use a cast, especially when combined with an if on the save variable, then you most likely want to use a match.

def insert(node: Tree[Char], value: Char): Tree[Char] = {
  node match {
    case End => // hand end case here
    case n: Node[Char] => // handle the node case here
    case _ => // throw an exception, or do nothing if this case can't happen
  }
}

Now the node case is complicated enough that you might extract a method for it. Otherwise, it looked fine to me.

Answer 2

To take full advantage of your generic class, change the insert method definition such that it is also generic:

    def insert[T](node: Tree[T], value: T): Tree[T] = {
        // implementation using pattern matching
    }

Answer 3

• As some other post pointed out, it's not clear why you are implementing insert only for Char.

• I don't like the name End. It's more of an empty slot.

• You did not show the implementation of height. It's better to post a fully running example. (See my code below.)

• Your code does not compile. You rightly made the Nodes immutable, but you can't reassign its members:

  internalNode.left = insert(internalNode.left, value)
  

  You can make the members of a case class mutable by declaring them case class Node(var value..., but you should try to stick to immutable data structures.

• You can also include conditions in the case matching to shorten the code even further.

Here is my implementation with all my suggestions:

  sealed abstract class Tree[+T] {
    def height: Int
  }
  case class Node[+T](value: T, left: Tree[T], right: Tree[T]) extends Tree[T] {
    override def height = 1 + math.max(left.height, right.height)
    override def toString = s"Node(${value}, [left=${left}, right=${right}]"
  }
  case object Empty extends Tree[Nothing] {
    override def height = 1
  }
  object Node {
    def apply[T](value: T): Node[T] = Node(value, Empty, Empty)
  }

  def insert[T](tree: Tree[T], value: T): Tree[T] = {
    val random = new Random(123)
    def insertLeft[T](node: Node[T], value: T) = Node(node.value, insert(node.left, value), node.right)
    def insertRight[T](node: Node[T], value: T) = Node(node.value, node.left, insert(node.right, value))
    tree match {
      case Empty => Node(value)
      case node @ Node(_, l, r) if (l.height > r.height) => insertRight(node, value)
      case node @ Node(_, l, r) if (l.height < r.height) => insertLeft(node, value)
      case node @ Node(_, _, _) => if (random.nextBoolean) insertRight(node, value) else insertLeft(node, value)
    }
  }

I also realized you don't even need algebraic data types: you can use Option instead of an Empty node.

  case class Node[+T](value: T, left: Option[Node[T]] = None, right: Option[Node[T]] = None) {
    def height: Int = 1 + math.max(left.map(n => n.height).getOrElse[Int](0), right.map(n => n.height).getOrElse[Int](0))
    override def toString = s"Node(${value}, [left=${left}, right=${right}]"
  }

  def insert[T](tree: Node[T], value: T): Node[T] = {
    val random = new Random(123)
    tree match {
      case Node(v, None, None) => if (random.nextBoolean) Node(v, Some(Node(value)), None) else Node(v, None, Some(Node(value)))
      case Node(v, None, Some(r)) => Node(v, Some(Node(value)), Some(r))
      case Node(v, Some(l), None) => Node(v, Some(l), Some(Node(value)))
      case Node(v, Some(l), Some(r)) => if (random.nextBoolean) Node(v, Some(insert(l, value)), Some(r)) else Node(v, Some(l), Some(insert(r, value)))
    }
  }