scala – 了解纯函数式持久二叉树

让我们举一个简单的例子来演示用法：首先是一个空集,比如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包含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

因此,包含任何集合的方法接受一个元素并返回一个新集合 – 它不会
更改集合(调用include方法的原始对象ob).

我们有两种类型的树集; empty和non-empty各有一个包含的实现：

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

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

非空集具有构造函数参数elem,它表示树的根,并且对于NonEmpty中的所有方法都是可见的.

// Non-Empty
def incl(x: Int): IntSet =
   if      (x < elem) new NonEmpty(elem,right)
   else if (x > elem) new NonEmpty(elem,right incl x)
   else this

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

>将元素x添加到非空集,其根元素也是x
给你相同的集(这个)
>将元素x添加到根元素小于x的非空集
给你另一套,其中：

>根元素与原始集合相同
>左子树不变 – 与原始集相同
>新的右子树成为原始右子树
x添加到它“：正确包括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从其他集合中派生集合(树),而不更改原始集合.这是因为在非常阶段,我们要么 –

>返回基于现有数据结构而不是修改的新数据结构
?现有结构,OR,
>按原样返回现有结构.

包含的工作方式相同：Empty有一个实现,对任何输入都返回false.如果给定元素与它的根相同,或者左边或右边的子树包含它,则NonEmpty会快速返回true！