Scala: круговые ссылки в неизменяемых типах данных?

Ответ 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 вместо указания на нуль, но 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) 

И, конечно, потому что исходный список неизменен, он действительно не изменился.

Ответ 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
  }
}

Это, как говорится, вы, вероятно, хотите спросить себя долго и упорно о том, почему вы хотите такую ​​вещь.

Ответ 3

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

Ответ 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);
}

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

Ответ 5

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