斯卡拉递归树的联合
这是我在Martin Odersky关于Coursera第3周的视频讲座中看到的二叉树的实现：
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 =
((left union right) union other) incl elem
override def toString = "{" + left + elem + right + "}"
}
因此Empty和NonEmpty遵循IntSet概述的标准。 我感兴趣的是NonEmpty类中的联合方法。 我想了解它是如何工作的。
我在下面做了一个小小的描述来解释我的思维过程： 
对我来说，似乎在那里有一个无限循环。 但我更确定我在下面的某个地方犯了一个评估错误：
让我们看看我是否可以用你的图解析出来。
((left union right) union other) incl elem成为： ((L1 u R1) u OE1) incl 5
将内部括号展开为: ((L2 u R2) u R1) incl 3
L2和R2都是空的，所以这会折叠到： R1 incl 3 ，这是一个新的NonEmpty ，不在你的图中。
将其插入原始公式中： ((R1 incl 3) u OE1) incl 5
这在图中变得越来越难，但正如你所看到的，我们已经从计算中删除了L1 ，并用一个新的，稍大一点的NonEmpty代替了R1 。 以这种方式继续IntSet ，所有东西都会被缩减为一个新的IntSet ，它包含了前面的所有值。