Printing out a tree set using pattern matching in Scala

Question

I'm working on some exercises Scala by Example and I've implemented an excl() method on sets which removes an element from a set, and a toString method that converts a set to a string.

I'm practicing use pattern matching here. A bit concerned about shadowing my instance variables on the line

case NonEmptySet(elem, left, right)

Is there anything obvious that could be improved?

trait IntSet {
 def incl(x: Int): IntSet
 def excl(x: Int): IntSet
 def contains(x: Int): Boolean
}
case object EmptySet extends IntSet {
 def contains(x: Int): Boolean = false
 def incl(x: Int): IntSet = new NonEmptySet(x, EmptySet, EmptySet)
 def excl(x: Int) = this
 override def toString = "{}"
}
case class NonEmptySet(elem: Int, left: IntSet, right: IntSet) extends IntSet {
 def contains(x: Int): Boolean =
 if (x < elem) left contains x
 else if (x > elem) right contains x
 else true
 def incl(x: Int): IntSet =
 if (x < elem) NonEmptySet(elem, left incl x, right)
 else if (x > elem) NonEmptySet(elem, left, right incl x)
 else this
 def excl(x: Int): IntSet = {
 def combine(left: IntSet, right: IntSet): IntSet = {
 left match {
 case EmptySet => right
 case NonEmptySet(elem, ll, lr) => NonEmptySet(elem, combine(ll, lr), right)
 }
 }
 if (x < elem) new NonEmptySet(elem, left excl x, right)
 else if (x > elem) new NonEmptySet(elem, left, right excl x)
 else combine(left, right)
 }
 override def toString(): String = {
 def listElements(comma: Boolean, set: IntSet) : String = {
 set match {
 case EmptySet => ""
 case NonEmptySet(elem, left, right) => {
 val rightPart = elem + listElements(true, right)
 val list = left match {
 case EmptySet => rightPart
 case NonEmptySet(le, ll, lr) => listElements(false, left) + ", " + rightPart
 }
 (if (comma) ", " else "") + list
 }
 }
 }
 '{' + listElements(false, this) + '}'
 }
}
var subset = EmptySet incl 2
var set = subset incl 3 incl 4 incl 8 incl 9 incl 10 incl 11 excl 4
println(set contains 6)
println(set.contains(6))
println(set contains 2)
println(set incl 4 incl 6 excl 2)

Answer 1

Some ideas:

• Make the trait sealed.

• combine doesn't need to be a nested function, this only makes it harder to read and causes problems with shadowed variables. Instead you could move it to an accompanying object, or make it a separate method such as:

  sealed trait IntSet {
   ...
   private def combine(withRight: IntSet): IntSet;
  }
  

  for EmptySet it will just return withRight, for a NonEmptySet it will be

   def combine(withRight: IntSet): IntSet =
   NonEmptySet(elem, left.combine(right), withRight);
  

• toString is somewhat complicated, and can suffer from performance problems due to repeatedly concatenating strings together. Instead I'd suggest you to implement Traversable. Not only this will make your class much more useful, it's implementation will be cleaner, because it won't be cluttered by operating with strings. And then you'll already have mkString which you can use as

  override def toString: String = mkString("{", ",", "}")