Scala:不可变数据类型中的循环引用？

Question

我一直在考虑如何仅使用不可变的案例类在 Scala 中实现双向链接树或列表。对于大多数“更新”操作，我一直在使用复制和更新方法。例如，在设置 parent 的 child 时，我说

parent = parent.copy(child=child)

或者在设置 child 的 parent 时，我说

child = child.copy(parent=parent)

我意识到，如果我将父级设置为包含一个子级，然后创建和更新一个新的子级以包含父级，则父级将包含对旧子级的引用。同样，如果我尝试反过来做， child 将包含对旧 parent 的引用。

我希望我的树是双重连接的，这样我就可以双向爬行:从树根向下爬到他的 child ，或者从叶子向上爬到他的 parent 。是否可以以这种方式“同时”链接父节点和子节点，给我循环引用，然后我可以双向爬行？

我可以使用可变数据轻松地做到这一点，但在我的情况下，双链接树将在创建后存在很长时间，我希望尽可能保持它不可变。

Answer 1

让我们尝试一步一步地解决它。

作为一个经验法则，当创建一个不可变对象(immutable对象)时，所有的构造函数参数在实例化的时候都应该是已知的，但是让我们作弊并通过名称传递构造函数参数，然后使用惰性字段来延迟评估，这样我们就可以在元素之间创建一个双向链接:

// p and n are passed by name 
// and won't be evaluated until prev and next are accessed
// for the first time
class Element [T] (val value: T, p : => Element[T], n : => Element [T]) {
  lazy val prev = p
  lazy val next = n
}

val e1:Element[Int] = new Element [Int] (1,null,e2)
val e2:Element[Int] = new Element [Int] (2,e1,e3)
val e3:Element[Int] = new Element [Int] (3,e2,e4)
val e4:Element[Int] = new Element [Int] (4,e3,null)

一旦我们运行代码，我们将收到一个不可变的双向链表:

空 ← e1(1) ↔ e2(2) ↔ e3(3) ↔ e4(4) → 空

并且将能够来回遍历它:

println(e1.next.next.next.value)
println(e4.prev.prev.prev.value)

4
1

现在，假设我们想在列表末尾添加第五个元素，它看起来像这样:

空 ← e1(1) ↔ e2(2) ↔ e3(3) ↔ e4(4) ↔ e5(5) → 空值

val e5:Element[Int] = new Element [Int] (5,e4,null)

此时我们得到:

null ← e1(1) ↔ e2(2) ↔ e3(3) ↔ e4(4) → null 
                                     ↖  ↑
                                       e5(5)

等一下，看起来不太对劲! e4 应该指向 e5 而不是 null，但 e4 是不可变的，我们不能更改元素本身，所以看起来唯一的选择是制作副本并将其指向 e3 和 e5。让我们尝试将这种新方法应用于初始列表:

空 ← e1(1) ↔ e2(2) ↔ e3(3) ↔ e4(4) → 空

val e4_b: Element[Int] = new Element [Int] (e4.value, // keeping original value 
                                            e3,e5)

val e5  : Element[Int] = new Element [Int] (5,e4_b,null)

更好的是，e4_b 通向 e5，而 e5 又通向 e4_b:

null ← e1(1) ↔ e2(2) ↔ e3(3) ↔ e4(4) → null 
                           ↖           ↑
                             e4_b(4) ↔ e5(5)

但是现在我们有同样的原始问题，只是 e3 仍然指向 e4。你能看到正在出现的趋势吗？如果我们继续复制元素以很快解决问题，我们最终会得到:

null ← e1(1) ↔ e2(2) ↔ e3(3) ↔ e4(4) → null 
  ↑                                      ↑
e1_b(1) ↔ e2_b(2) ↔ e3_b(3) ↔ e4_b(4) ↔ e5(5)

原始列表没有任何改变(事实证明我们并没有无缘无故地称其为“不可变”)，相反，我们最终得到了一个全新的列表，尽管它具有相同的值。因此，每当我们尝试对不可变的双向链接数据结构进行更改时，我们都需要从头开始重建整个事物，并保留这些值。

让我们看一下 Scala 标准的单链不可变列表:

e1(1) → e2(2) → e3(3) → e4(4) → 无

我们会注意到，我们能够更轻松地派生新列表，而无需从头开始重建整个数据结构，例如要删除第二个元素，我们只需复制第一个元素并将其指向第三:

e1(1) → e2(2) → e3(3) → e4(4) → Nil
                 ↗
         e1_b(1) 

而且，当然，因为原始列表是不可变的，所以它并没有真正改变。