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

Question

我一直想着如何使用不可变的case类在Scala中实现双链接树或列表.对于大多数"更新"操作,我一直在使用复制和更新方法.例如,在设置父母的孩子时,我说

parent = parent.copy(child=child)

或者在设置孩子的父母时,我说

child = child.copy(parent=parent)

我意识到,如果我将父级设置为包含子级,然后创建并更新新子级以包含父级,则父级将包含对旧子级的引用.同样,如果我试图反过来做,那么孩子将包含对旧父母的引用.

我希望我的树能够双重联系,所以我可以双向爬行:从根到他的孩子,或者从叶子向上到父母.是否有可能以这种方式"同时"链接父节点和子节点,给我循环引用,然后我可以双向爬行？

我可以使用可变数据轻松地做到这一点,但在我的情况下,双重链接树将在创建后存在很长时间,并且如果可能的话我想保持它不变.

Answer 1

让我们一步一步地尝试.

根据经验,在创建不可变对象时,所有构造函数参数都应该在实例化时知道,但是让我们按名称欺骗并传递构造函数参数,然后使用延迟字段来延迟评估,这样我们就可以在元素之间创建双向链接:

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

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

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

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

Answer 2

你可以用懒惰来做,例如:

trait Link[A] {
  def value: A
  def get: Link[A]
}

class Circular[A](val value: A, getter: => Link[A]) extends Link[A] {
  lazy val get = getter
}

object circles {
  def create[A](as: (A, A)): Link[A] = {
    lazy val b: Link[A] = new Circular(as._1, new Circular(as._2, b))
    b
  }
}

话虽这么说,你可能想长时间地问自己为什么要这样的事情.