Scala by Example — Chapter 06

/**
 * Exercise 6.0.1 Write methods union and intersection to form the union and
 * intersection between two sets.
 */

trait IntSet {
  def incl(x: Int): IntSet
  def contains(x: Int): Boolean
  def union(other: IntSet): IntSet
  def intersect(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 union(other: IntSet): IntSet = other
  def intersect(other: IntSet): IntSet = this
}

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 + (other: Intset): IntSet = {
    val newSet = left + right + other
    newSet incl elem
  }

  def union(other: IntSet): IntSet = this + other

  def intersect(other: IntSet): IntSet = {
    val rght = right intersect other
    val lft = left intersect other
    val newSet = lft union rght

    if (other contains elem)
      s incl elem
    else
      s
  }
}

 

 

/**
 * Exercise 6.0.2 Add a method
 *    def excl(x: Int)
 * to return the given set without the element x. To accomplish this, it is
 * useful to also implement a test method
 *    def isEmpty: Boolean
 * for sets.
 */

trait IntSet {
  def incl(x: Int): IntSet
  def contains(x: Int): Boolean
  def excl(x: Int): IntSet
  def isEmpty: Boolean
}

class EmptySet extends IntSet {
  def contains(x: Int): Boolean = false
  def incl(x: Int): IntSet = new NonEmptySet(x, new EmptySet, new EmptySet)
  def excl(x: Int): IntSet = this
  def isEmpty: Boolean = true
}

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 + (other: Intset): IntSet = {
    val newSet = left + right + other
    newSet incl elem
  }

  def isEmpty: Boolean = false

  def excl(x: Int): IntSet = 
    if (x < elem)
      new NonEmptySet(elem, left excl x, right)
    else if (x > elem)
      new NonEmptySet(elem, left, right excl x)
    else
      left append right
}

 

 

/**
 * Exercise 6.0.3 Write an implementation Integer of integer numbers The
 * implementation should support all operations of class Nat while adding two
 * methods.
 *
 *      def isPositive: Boolean
 *      def negate: Integer
 *
 * The first method should return true if the number is positive. The second
 * method should negate the number. Do not use any of Scala’s standard numeric
 * classes in your implementation. (Hint: There are two possible ways to
 * implement Integer. One can either make use the existing implementation of
 * Nat, representing an integer as a natural number and a sign. Or one can
 * generalize the given implementation of Nat to Integer, using the three
 * subclasses Zero for 0, Succ for positive numbers and Pred for negative 
 * numbers.)
 */

// APENAS REESCREVE AS FUNÇÕES, SEGUINDO O PADRÃO DE NAT
abstract class Nat {
  def isZero: Boolean
  def predecessor: Nat
  def successor: Nat
  def + (that: Nat): Nat
  def - (that: Nat): Nat
}

abstract class Integer extends Nat {
  protected val sign: Boolean = true
  def isPositive = sign
  def negate = !sign
}

// exemplo de uso da definição
class Succ(x: Nat) extends Nat {
  def isZero: Boolean = false
  def predecessor: Nat = x
  def successor: Nat = new Succ(this)
  def + (that: Nat): Nat = x + that.successor
  def - (that: Nat): Nat = if (that.isZero) this
                           else x - that.predecessor
}

object ZeroInteger extends Integer {
  override def isZero: Boolean = true
  override def predecessor: Nat = (new Succ(this)).negate
  override def successor: Nat = new Succ(this)
  override def +(that: Nat): Nat = that
  override def -(that: Nat): Nat = that.negate
  override def isPositive: Boolean = true
  override def negate: Nat = this
}