[SCALA] 스칼라 : 불변 데이터 유형의 순환 참조?

스칼라 : 불변 데이터 유형의 순환 참조?

나는 스칼라 그냥 불변의 경우 클래스를 사용에서 이중 연결 트리 또는 목록을 구현하는 방법에 대한 갈 것이라고 어떻게 잠시 동안 생각을 해 봤는데. 대부분의 "업데이트"작업의 경우, 나는 복사 및 업데이트 방법을 사용했습니다. 부모의 자식을 설정하는 경우 예를 들어, 내가 말

parent = parent.copy(child=child)

아이의 부모를 설정하는 경우 나, 내가 말할

child = child.copy(parent=parent)

난 내가 아이를 포함하고 생성 및 부모를 포함하는 새로운 아이를 업데이트 할 부모를 설정 한 경우, 부모가 기존의 아이에 대한 참조를 포함 할 것이라고 알고 있습니다. 내가 그것을 다른 방식으로 라운드를하려고 노력하면 마찬가지로, 아이는 기존의 부모에 대한 참조를 포함 할 것입니다.

그의 부모에 잎에서 위쪽으로 자신의 아이들에게 루트에서 아래쪽으로, 또는 : 나는 두 가지를 크롤링 할 수 있도록 내 나무는 이중 연결되어야합니다. 그것은 "동시에"이런 식으로 부모와 자식 노드를 연결하는 것이 가능하고, 그때 양방향으로 크롤링 할 수 있습니다 나에게 순환 참조를 제공하기 위해?

나는 쉽게 사용하는 가변 데이터를 할 수 있지만, 내 경우에는 이중 연결 트리 생성 후 오랜 시간 동안 존재하며, 나는 가능한 모든의 경우 불변을 유지하려는.

해결법

1. ==============================

   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 가리키는 대신 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에 e4_b 리드입니다 :

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

   하지만 지금 우리는 단지 E4에서 아직 포인트가 E3와 같은 원래의 문제가 있습니다. 당신은 추세가 신흥 볼 수 있을까요? 우리가 곧 문제를 해결하기 위해 요소를 복사 유지하면 우리가 끝낼 것입니다 :

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

   원래 목록은 (우리가 아무것도 "불변"전화하지 않은 것에 따라) 대신에 우리는 완전히 새로운 목록을 결국 같은 값을 유지이기는하지만 조금 변경되지 않았습니다. 그래서 우리는 우리가 값을 보존, 처음부터 전체 일을 다시 할 필요가 불변의 이중 연결 데이터 구조를 변경하려고 할 때마다.

   하자가 단독으로 대신 불변의리스트를 연결 스칼라 표준을 살펴 :

   E1 (1) E2 → (2) → (E3) (3) → E4 (4) → 닐

   우리는 알 우리는있는 거 예를 들어 우리가 단순히 처음의 복사본을 만들고 그것을 가리 키도록해야 할 것 번째 요소를 제거하기 위해, 처음부터 전체 데이터 구조를 재 구축 할 필요없이보다 쉽게 ​​새 목록을 도출 할 수 제삼:

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

   원래 목록이 불변이기 때문에, 물론, 정말 변경하지 않았다.

2. ==============================

   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. ==============================

   3.나는 당신의 문제에 대한 하나 개의 가능한 솔루션을 설명하는 블로그 게시물을 만들었습니다. http://akikhtenko.github.io/blog/2013/12/15/immutable-double-linked-tree-construction-in-scala/ 그것은 예를 들어 나무를 다룹니다하지만 다른 데이터 유형에 아이디어를 적용하는 문제가되지 않습니다.

   나는 당신의 문제에 대한 하나 개의 가능한 솔루션을 설명하는 블로그 게시물을 만들었습니다. http://akikhtenko.github.io/blog/2013/12/15/immutable-double-linked-tree-construction-in-scala/ 그것은 예를 들어 나무를 다룹니다하지만 다른 데이터 유형에 아이디어를 적용하는 문제가되지 않습니다.

4. ==============================

   4.우리가 객체를 구축 완료 후 변경되지 않도록 스칼라 수단에 불변. 그것이 개체의 건설 기간 동안 실제로 변경할 수 있습니다. 용액의 생성자 코드의 일부를 전달하는 것 필드 전에 필요한 값은 불변 오브젝트가 계산.

   우리가 객체를 구축 완료 후 변경되지 않도록 스칼라 수단에 불변. 그것이 개체의 건설 기간 동안 실제로 변경할 수 있습니다. 용액의 생성자 코드의 일부를 전달하는 것 필드 전에 필요한 값은 불변 오브젝트가 계산.

   {
     // 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. ==============================

   5.

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

from https://stackoverflow.com/questions/8374010/scala-circular-references-in-immutable-data-types by cc-by-sa and MIT license