title: Understanding purely functional persistent binary trees
body: <p>I'm scanning this code, and I want to understand how it works.</p>
  
  <p>There are two possible trees: a tree for an empty set, and a tree consisting of an integer and two subtrees. The invariant: For each node, the node on the right hand side contains integer values higher than the parent, while the left side node contains integer values lower than the parent. </p>
  
  <p>Here is the code:</p>
  
  <pre><code>abstract class IntSet{
    def incl(x: Int): IntSet         // include element x in the IntSet
    def contains(x: Int): Boolean    // is x an element of the set?
    def union(other: IntSet): IntSet // union of this and other set
  }
  
  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(elem: Int, left: IntSet, right: IntSet) extends IntSet{
  
    def contains(x: Int): Boolean =
      if      (x &lt; elem) left contains x
      else if (x &gt; elem) right contains x
      else true
  
    def incl(x: Int): IntSet =
      if      (x &lt; elem) new NonEmpty(elem, left incl x, right)
      else if (x &gt; elem) new NonEmpty(elem, left, right incl x)
      else this
  
    override def toString = "{" + left + elem + right + "}"
  
    def union(other:IntSet): IntSet =
      ((left union right) union other) incl elem
  
  }
  </code></pre>
  
  <p>How is this data structure used? How does it achieves persistence? How does it work?</p>