set.scala

abstract class IntSet {
  def incl(x: Int): IntSet
  def contains(x: Int): Boolean
  def traverse(f: Int => Unit): Unit
  def union(other: IntSet): IntSet
  def intersection(other: IntSet): IntSet
}

class EmptySet extends IntSet {
  def contains(x: Int): Boolean = false
  def incl(x: Int): IntSet = new NonEmptySet(x, new EmptySet, new EmptySet)
  def traverse(f: Int => Unit): Unit = {}
  def union(other: IntSet): IntSet = other 
  def intersection(other: IntSet): IntSet = new EmptySet()
  override def toString = "Empty"
}

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) new NonEmptySet(elem, left  incl x, right)
    else if (x > elem) new NonEmptySet(elem, left, right incl x)
    else this
  def traverse(f: Int => Unit): Unit = {
    f(elem)
    left  traverse f
    right traverse f
  }
  def union(other :IntSet): IntSet = {
    var result: IntSet = new EmptySet()
    this traverse ( x => {
      result = (result incl x)
    })
    other traverse ( x => {
      result = (result incl x)
    })
    result
  }
  def intersection(other :IntSet): IntSet = {
    var result: IntSet = new EmptySet()
    this traverse ( x => {
      if (other contains x) {
        result = (result incl x)
      }
    })
    result
  }
  override def toString = {
    var result : List[Int] = List();
    this.traverse( x => result = result ::: List(x) )
    result.sort( (a,b) => {
      if (a < b) true 
      else       false
    }).toString
  }
}

val set1 :IntSet = (0 to 10).foldLeft[IntSet](new EmptySet())((set, x) => (set incl x))
val set2 :IntSet = (5 to 15).foldLeft[IntSet](new EmptySet())((set, x) => (set incl x))

println( set1 )
println( set2 )
println( set1 union set2 )
println( set1 intersection set2 )