스칼라 DAG 여러 부모 업데이트

Question

불변의 데이터 구조가 스칼라에서 순환을 가질 수 없다는 것을 이미 알고 있습니다.

그러나 여러 부모가있는 하위 업데이트를 어떻게 처리합니까?

val child = Child("Tom") 
val mother = Parent("Susi", child) 
val father = Parent("Chuck", child) 
val renamedChild = child.copy(name = "Tommy") 
// how to update both references? 

나는 많은 지퍼로 그 못 봤어하지만 나는 그들이 단순한 나무하지 DAG의 권리를 위해 일할 것 같아?

Answer 1

불변/영구 데이터 구조에서는 구조 공유가 있으므로 업데이트를 수행 할 때 전체 구조의 일부를 업데이트해야합니다. 트리와 같은 계층 적 구조의 경우 (예를 들어 제시 한 바와 같이) 루트에서 자녀까지의 경로를 위에서 아래로 업데이트해야 함을 의미합니다. 이것은 차례로 부모님에 대한 지식이 있어야합니다. 당신은 데이터 구조를 중첩 한 경우

val mother1 = mother.copy(child = renamedChild) 
val father1 = father.copy(child = renamedChild) 

을 당신은 부기를하고 피하려고 :

mother 및 father 루트없이 주위에 "자유롭게 떠"한다면, 당신은뿐만 아니라 그들을 업데이트 할 것 수동으로 (실수로 쉽게 발생할 수 있음) Lenses과 같은 접근 방식을 사용할 수 있습니다.

구조체가 direct-acyclic-graph 인 경우 변경 불가능한 구현을 찾는 것이 어려울 수 있습니다. 영구적 인 DAG 구조는 인식하지 못합니다. 아마도 DAG를 트리 집합으로 분해 할 수는 있지만 그런 구현을 가로 질러 오지 않았다).

---

당연히 당신은 순진한 (성능이 좋지 않은) 버전을 가질 수 있습니다.

// set of vertices and map that points from children to parents! 
type Graph[A] = (Set[A], Map[A, Set[A]]) 

def update[A](graph: Graph[A], before: A, now: A): Graph[A] = { 
    val (vertices, edges) = graph 
    val newV = vertices - before + now 
    val parents = edges.getOrElse(before, Set.empty) 
    val newE = if (parents.isEmpty) edges else edges - before + (now -> parents) 
    (newV, newE) 
} 

val g1 = Set("Tom", "Susi", "Chuck") -> Map("Tom" -> Set("Susi", "Chuck")) 
val g2 = update(g1, "Tom", "Tommy")