Scala: циклические ссылки в неизменяемых типах данных?

Question

Некоторое время я думал о том, как бы реализовать реализацию двусвязного дерева или списка в 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)

Как только мы запустим код, мы получим неизменный двусвязный список:

ноль ← 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 вместо того, чтобы указывать на ноль, но 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, что приводит к 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
  }
}

При этом, вы, вероятно, хотите долго и усердно спрашивать себя, зачем вам такая вещь.

Answer 3

Я создал пост в блоге, который описывает одно из возможных решений вашей проблемы. http://akikhtenko.github.io/blog/2013/12/15/immutable-double-linked-tree-construction-in-scala/ В качестве примера рассматривается дерево, но применять идею не должно быть проблемой к другим типам данных.

Answer 4

Неизменяемость в scala означает, что после того, как мы закончили создание объекта, он не должен меняться. Во время строительства объекта он действительно изменчив. Решение состоит в том, чтобы передать фрагмент кода в конструктор объекта, который вычисляет необходимые значения, прежде чем поля станут неизменяемыми.

{
  // Create a with the creation of b as a parameter.
  val a=new A( (uncomplete:A)=>new B(uncomplete) )
}

class A( bFactory:A=>B){
  //Call the bFactory then assign the result to b.
  val b=bFactory(this);
}

class B(val a:A){
}

Поскольку вопрос касается деревьев, я также включу генерацию базового дерева, используя ту же технику.

 class MakeTree {
  val tree = new Node(None, createSubTree _, createSubTree _);

  def createSubTree(parent: Node): Option[Node] = {
    if (parent.depth < 3)
      Some(new Node(None, createSubNode _, createSubNode _))
    else
      None
  }
}

class Node(val parent: Option[Node], leftFactory: (Node) => Option[Node], rightFactory: (Node) => Option[Node]) {
  val left = leftFactory(this);
  val right = rightFactory(this);

  def depth(): Int = parent.map(_.depth + 1).getOrElse(0);
}

Выполнение такой конструкции оставляет чистую неизменную структуру без дополнительных затрат на доступ к ленивым значениям.

Answer 5

class A(val b: B)
abstract class B {
  val a: A
}
new B {
  val a = new A(this)
}