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("{", ",", "}")