如何初始化和“修改” Scala 中的循环持久数据结构？

Question

我搜索并找到了有关该主题的一些信息，但答案要么令人困惑，要么不适用。

我有这样的事情：

class Thing (val name:String, val refs:IndexedSeq[Ref])
class Ref (val name:String, val thing:Thing)

现在，我想说，加载一个文件，解析它并从中填充这个数据结构。它是不可变的和循环的，我们该如何做到这一点呢？

另外，假设我确实填充了此数据结构，现在我想修改它，例如更改 rootThing.refs(3).name，如何做到这一点？

---

感谢您在这里发布的想法。在这一点上，我在想，如果一个人真的想要像这样的持久数据结构，就应该跳出框框思考，并考虑客户端代码需要提出哪些问题。因此，不要考虑对象和字段，而应该考虑查询、索引等。首先，我在考虑以下方面： 是否存在双向多图持久数据结构？

Answer 1

如果您准备修改它以引入一定程度的惰性，则可以初始化这种形式的循环数据结构，

scala> class Thing (val name:String, refs0: => IndexedSeq[Ref]) { lazy val refs = refs0 } ; class Ref (val name:String, thing0: => Thing) { lazy val thing = thing0 }
defined class Thing
defined class Ref

scala> val names = Vector("foo", "bar", "baz")                                                                                                                       
names: scala.collection.immutable.Vector[java.lang.String] = Vector(foo, bar, baz)

scala> val rootThing : Thing = new Thing("root", names.map { new Ref(_, rootThing) })
rootThing: Thing = Thing@1f7dab1

scala> rootThing.refs(1).name
res0: String = bar

但是，您不能使其持久化：作为循环，任何更改都可以通过结构的每个元素可见，因此版本之间没有共享的机会。

Answer 2

对于单个循环引用，您可以使用惰性：

lazy val t: Thing = new Thing("thing", Vector(new Ref("ref", t)))

但是显然，对于多对多连接，这会变得复杂。

我不知道是否存在通用的纯功能循环图数据结构。对于非循环图，这很容易，因为您可以对其进行拓扑排序，然后逐步初始化它。

也许使用间接是您的一个选择，比如通过标识符而不是实际的 scala 对象引用来引用对象？

case class ThingByID(id: Int, name: String, refs: IndexedSeq[RefByID])
case class RefByID(name: String, thingID: Int)

然后，您可以在加载文件后通过 ID 将事物收集到不可变映射中（例如 collection.immutable.IntMap），并在来自引用时查找它们。

编辑

关于lazy val t的第一种情况，迈尔斯是正确的。事实上，您需要像他的回答中那样的名称参数。

class Thing(val name: String, val refs: IndexedSeq[Ref])
class Ref(val name: String, _thing: => Thing) { def thing = _thing }

val t: Thing = new Thing("thing", Vector(new Ref("ref", t)))

Answer 3

有一种替代方法需要重新考虑如何表示对象关联：不是将对象之间的关联存储在对象本身内部（通常在 OO 代码中完成），而是将它们添加到单独的层中作为映射。

由于对象图中的所有节点在创建关联时都已存在，因此可以使用映射轻松创建不可变的双向关联。

scala> class Thing (val name:String)
defined class Thing

scala> class Ref (val name:String)
defined class Ref

scala> new Thing("Thing1")
res0: Thing = Thing@5c2bae98

scala> new Ref("Ref1")
res1: Ref = Ref@7656acfa       

scala> val thing2Ref = Map(res0 -> res1)
thing2Ref: scala.collection.immutable.Map[Thing,Ref] = Map(Thing@5c2bae98 -> Ref
@7656acfa)

scala> val ref2Thing = Map(res1 -> res0)
ref2Thing: scala.collection.immutable.Map[Ref,Thing] = Map(Ref@7656acfa -> Thing
@5c2bae98)

如果您仔细想想，这种方法类似于关系数据库的工作方式。表之间的多值关联并不存储在行本身中，而是存储在单独的索引中。即使不存在关联索引并且使用表扫描解析查询，它也会使用主键索引来查找结果的所有候选行。

这种风格的优点是可以添加或更改关联而不影响对象本身，并且可以针对不同的受众/用例采用不同的关联。缺点是关联映射在关联开始的实例上无法直接访问；它必须被传递&单独提供。

Answer 4

不可变数据结构可以完全由其构造函数初始化，或者您可以接受在更改其属性时不断复制结构的需要。因此，为了回答问题的第一部分，您可以通过定义接受数据中所有信息的构造函数将数据加载到不可变数据结构中，或者确保您了解循环子图：

循环数据结构不一定完全是我认为是循环的。如果您想象单个实例/状态所保存的指针网络，则可能有一个子图，其中包含彼此指向的父级和子级，但没有其他循环结构。在这种情况下，复制实例 1 以延迟创建具有不同父节点（例如）的实例 2 将需要复制父节点和子节点，因为它们形成循环子图。但是，除父级之外的子级中保存的引用可以继续是对与第一个实例相同的不可变结构的引用。

例如，我的“房屋”类引用了“门”、“窗”和“屋顶”。门有颜色和对房屋的 toHouse 引用，窗户有大小，屋顶有坡度。所以我创建了 bobsHouse，有一个绿色的门、一个大窗户和一个平坦的屋顶。事实上，由于所有这些都是不可变的，因此理论上只有一个大窗户 - 所有具有大窗户的房屋都有相同的窗户。第二个实例 janesHouse 与 bobsHouse 类似，但具有山形屋顶。因此，如果我说 janesHouse = bobsHouse.withRoof(gabled)，那么我应该得到一个新的 House 实例，带有一个新的（也是绿色的）门和一个新的（山墙式的）屋顶，但具有相同的窗口。

因此，如果 janesHouse 被延迟评估，则仅当引用 Door 或 Roof 时才需要创建一个新 House。如果请求 janesHouse.Window，它根本不需要创建一个新的 House - 只需要 bosHouse。

tl;dr：您可以拥有持久（惰性）循环数据结构，但前提是您可以在其中找到非循环子图，即它不是链。