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

在创建不可变对象时，经验法则是所有的构造函数参数都应该在实例化的时候被知道，但是我们通过名称来欺骗和传递构造函数参数，然后使用延迟字段来延迟评估，所以我们可以在元素之间创建一个双向链接：

// 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)

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

null←e1(1)?e2(2)?e3(3)?e4(4)→null

并能够来回遍历：

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

4
1

现在，我们假设我们要添加第五个元素到列表的末尾，这样它就像这样：

null←e1(1)?e2(2)?e3(3)?e4(4)?e5(5)→null

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。我们尝试将这种新方法应用于初始列表：

null←e1(1)?e2(2)?e3(3)?e4(4)→null

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，导致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)→Nil

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

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

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