Scala DAG更新了几个parents

Question

我已经知道不可变 data-structures 在 Scala 中不能有循环。

但是，您如何处理 child 多个 parents 更新？

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?

我没有深入研究 Zippers，但我认为它们只适用于简单的树而不是 DAG，对吗？

Answer 1

在不可变/持久数据结构中，你有结构共享，所以当你执行更新时，必须更新整体结构的一部分。对于像树这样的层次结构（如您的示例所示），这意味着您必须更新 top-to-bottom 从根目录到 child 的路径。这反过来又要求您了解您的 parents.

如果 mother 和 father "freely floating" 没有根，您也必须更新它们：

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

如果你有嵌套的数据结构并且你想避免手动执行 book-keeping（这很容易导致错误），你可以使用诸如 Lenses.[=15= 之类的方法]

如果你的结构是 directed-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")

Scala DAG更新了几个parents

Scala DAG update several parents

scala

data-structures

immutability