A Scala worksheet that exhibits non-associative behaviour on line 38, in the definition of `union` in class `NonEmpty`. With the given expression, `((left union right) union other)`, `largeSet.union(Empty)` takes an inordinate amount of time to complete with sets with 100 elements or more. When that expression is changed to `(left union (right u…

gistfile1.scala

package week3

object intsets {
  util.Properties.versionString                   //> res0: String = version 2.10.2

  // 1..100, shuffled
  val largeSet = util.Random.shuffle((1 to 100).toList).foldLeft(Empty: IntSet)(_.incl(_))
  Empty.union(Empty)
  Empty.union(largeSet)
  largeSet.union(Empty)
}

abstract class IntSet {
  def incl(x: Int): IntSet
  def contains(x: Int): Boolean
  def union(other: IntSet): IntSet
}

object Empty extends IntSet {
  def contains(x: Int): Boolean = false
  def incl(x: Int): IntSet = new NonEmpty(x, Empty, Empty)
  override def toString = "."
  def union(other: IntSet): IntSet = other
}

class NonEmpty(val elem: Int, val left: IntSet, val 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 NonEmpty(elem, left incl x, right)
    else if (x > elem) new NonEmpty(elem, left, right incl x)
    else this
  override def toString = "{" + left + elem + right + "}"
  def union(other: IntSet): IntSet =
    // The following expression doesn't behave associatively
    ((left union right) union other) incl elem
}