CODEWITHSUNDEEP
scala
Renz
Renz

Reputation: 37

Classes and Substitutions in Scala

Can someone explain to me how the method union exactly works in this code? I can see that it's calling itself in the function but other than that I don't get what it does. Printing t2 union t3 yields {{{.-1.}2.}3{{.4.}5{.7.}}}.

object Mp6 {  
  def main(args: Array[String]): Unit = {
    val t1 = Empty
    val t2 = t1 incl 3 incl 5 incl 4 incl 7
    val t3 = t2 incl 2 incl 4 incl -1

    println(t1)
    println(t2)
    println(t1 contains 5)
    println(t2 contains 5)
    println(t2 contains 5)

    println(t2 union t3)
  }
}

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)  
  def union(other: IntSet): IntSet = other
  override def toString = "."
}

class NonEmpty(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 NonEmpty(elem, left incl x, right)
    else if (x > elem) new NonEmpty(elem, left, right incl x)
    else this

  def union(other: IntSet): IntSet = {
    val set = left.union(right.union(other))
    set.incl(elem)
  }

  override def toString = "{" + left + elem + right + "}"
}

Upvotes: 1

Views: 446

Answers (2)

user1277337
user1277337

Reputation:

Well, you're basically asking for an explanation of how the substitution model of evaluation works. As stated in the comments above, your code snippet closely resembles an implementation of IntSets written by Martin Odersky (the creator of Scala), so I'll use the notation from his course notes. I assume you've already taken a quick read through the substitution model rules. If not, Functional Programming Principles in Scala and Scala by Example are good places to start.

I'll give you a hint: Suppose, for the sake of convenience, that val t1 = new NonEmpty(1, Empty, Empty) and val t2 = new NonEmpty(2, Empty, new NonEmpty(3, Empty, Empty)). This means that t1: NonEmpty = {.1.} and t2: NonEmpty = {.2{.3.}}. Now let's evaluate the expression t1 union t2. 

t1 union t2 = new NonEmpty(1, Empty, Empty) union new NonEmpty(2, Empty, new NonEmpty(3, Empty, Empty))
            → [1/elem, Empty/left, Empty/right] [new NonEmpty(2, Empty, new NonEmpty(3, Empty, Empty))/other] [new NonEmpty(1, Empty, Empty)/this] (left union (right union other)) incl elem 
            = (Empty union (Empty union new NonEmpty(2, Empty, new NonEmpty(3, Empty, Empty)))) incl 1
            ...

Can you complete the evaluation now?

Upvotes: 2

samthebest
samthebest

Reputation: 31543

It's an implementation of a sorted integer set that works by backing with a binary sorted tree that does not add duplicates. Therefore union just performs a set theoretic union where the order of the integers is preserved.

Upvotes: 0

Related Questions