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)