scala - 理解纯功能性持久二叉树

Question

我正在扫描此代码，我想了解它是如何工作的。

有两种可能的树:一种是空集树，另一种是由一个整数和两个子树组成的树。不变量:对于每个节点，右侧节点包含高于父级的整数值，而左侧节点包含低于父级的整数值。

这是代码:

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 < 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 =
    ((left union right) union other) incl elem

}

这个数据结构是如何使用的？它如何实现持久性？它是如何工作的？

Answer 1

代码直接映射到您提供的描述。

让我们举一个简单的例子来演示用法:您首先有一个空集，例如 e然后向其中添加一个元素以获得另一个集合，例如 s1。然后你将拥有2 套，e 和 s1:

val e = Empty
e contains 42        // will be false
// create s1 from e
val s1 = e incl 1    // e does not change; it remains a reference to the Empty set.
// Now we have s1, a set that should contain (1) and nothing else.
s1 contains 1        // will be true
s1 contains 42       // will be false

我猜您熟悉可让您输入的 Scala 速记法s1 incl 1 而不是 s1.incl(1)

请注意，只能有一个空集，因此这也很好:

val s1 = Empty incl 1

然后假设您想要添加 2 来获取另一个集合 s2 ，其元素必须同时包含 {1, 2}。

val s2 = s1 incl 2
s2 contains 1       // true
s2 contains 2       // true
s2 contains 3       // false

因此，任何集合上的方法 incl 都会接受一个元素并返回一个新集合 - 它不会更改集合(调用 include 方法的原始对象 ob)。

我们有两种类型的树集；空和非空，每个都有一个 incl 的实现:

// Empty
def incl(x:Int): IntSet = new NonEmpty(x, Empty, Empty)

读取:“向空(树)集合添加一个元素会产生另一个集合，该集合是一个非空树，只有一个值为 1 的根节点以及空的左子树和右子树.”

非空集合有一个构造函数参数 elem，它代表树的根，并且对 NonEmpty 中的所有方法都可见。

// Non-Empty
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

读取:(与上述 if-else 的顺序相反):

• 将元素 x 添加到其 root 元素也是 x 的非空集合中给你相同的集合(this)
• 将元素x添加到一个非空集合，其根元素小于x为您提供另一组，其中:
  • 根元素与原始集合相同
  • 左子树未更改 - 与原始集合中的相同
  • 新右子树成为原始右子树x 添加到其中”:right incl x
• 将元素x添加到一个非空集合，其根元素大于x为您提供另一组，其中:
  • 根元素与原始集合相同
  • 右子树未更改 - 与原始集合中的相同
  • 新左子树成为原始左子树x 添加到其中”:left incl x

“持久性”是通过以下事实实现的:没有任何树或子树曾经发生过变化。在示例中

val s1 = Empty incl 1      // s1 is a tree with only a root(1) an no branches.
val s2 = s1 incl 2         // s2 is another tree with - 
                           //  - the same root(1),
                           //  - the same left-subtree as s1, (happens to be Empty)
                           //  - a new subtree which in turn is a tree with - 
                           //    - the root element (2)
                           //    - no left or right brances.
s1 contains 1 // true
s1 contains 2 // false
s2 contains 1 // true
s2 contains 2 // true

val s3 = s2 incl -3        // s2.incl(-3)
                           // from s2 we get s3, which does not change s2's structure
                           // in any way.
                           // s3 is the new set returned by incl, whose
                           //  - root element remains (1)
                           //  - left subtree is a new tree that contains 
                           //    just (-3) and has empty left, right subtrees
                           //  - right subtree is the same as s2's right subtree!

s3.contains(-3) // true; -3 is contained by s3's left subtree
s3.contains(1)  // true; 1 is s3's root.
s3.contains(2)  // true; 2 is contained by s3's right subtree
s3.contains(5)  // false

我们仅使用incl从其他集合派生集合(树)，而不改变原始集合。这是因为在某个阶段，我们要么 -

1. 基于现有数据结构返回新的数据结构，而不是修改 现有结构，或，
2. 按原样返回现有结构。

contains 的工作方式相同:Empty 具有针对任何输入返回 false 的实现。如果给定元素与其根元素相同，或者它的左子树或右子树包含该元素，NonEmpty 会快速返回 true!