如何操作不可变对象树？
我正在用不可变对象构建整个应用程序，以便多线程和撤消变得更容易实现。我使用的是 Google Collections Library，它提供了不可变版本的地图、列表和放。
我的应用程序模型看起来像一棵树：
- 场景是一个顶级对象，包含对根节点的引用。
- 每个节点可以包含子节点和端口。
对象图可能如下所示：
Scene
|
+-- Node
|
+-- Node
|
+- Port
+-- Node
|
+- Port
+- Port
如果所有这些对象都是不可变的，并由顶级 SceneController 对象控制：
- 构造此层次结构的最佳方法是什么？
- 如何替换对象树中任意深度的对象？
- 有没有办法支持反向链接，例如具有“父”属性的节点？
更一般地说：
- 是否出现了处理此类数据的模式？
- 是否有关于该主题的（学术）文献？
- 这是个好主意吗？
I'm building an entire application out of immutable objects so that multi-threading and undo become easier to implement. I'm using the Google Collections Library which provides immutable versions of Map, List, and Set.
My application model looks like a tree:
- Scene is a top-level object that contains a reference to a root Node.
- Each Node can contain child Nodes and Ports.
An object graph might look like this:
Scene
|
+-- Node
|
+-- Node
|
+- Port
+-- Node
|
+- Port
+- Port
If all of these objects are immutable, controlled by a top-level SceneController object:
- What is the best way to construct this hierarchy?
- How would I replace an object that is arbitrarily deep in the object tree?
- Is there a way to support back-links, e.g. a Node having a "parent" attribute?
And more generally:
- Have any patterns emerged for dealing with this type of data?
- Is there (academic) literature available on the subject?
- Is this a good idea?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这里有两个有趣的概念。首先，持久数据结构。如果树的所有元素都是不可变的，那么可以通过替换某些部分但引用旧部分来从原始树派生出一棵新树，从而节省时间和内存。
例如，如果要向已有两个端口的节点添加第三个端口，则必须创建一个新场景、新场景的节点的后代以及要更改的节点。不需要重新创建其他节点和所有端口 - 您只需在新场景/节点中引用它们即可。
另一个概念是拉链。拉链是一种通过持久数据结构“导航”以优化本地更改的方法。例如，如果您添加了四个新端口而不是仅一个，但每次添加每个端口一个，则必须创建四个新场景和八个新节点。使用拉链，您可以将此类创作推迟到完成为止，从而节省了这些中间对象。
我读过的关于拉链的最好解释是这里。
现在，使用拉链来导航数据结构消除了反向链接的需要。通过巧妙地使用递归构造函数，您可以在不可变结构中拥有反向链接。然而，这样的数据结构不会是持久的。非持久不可变数据结构的修改性能很差，因为每次都需要复制整个数据。
至于学术文献，我推荐 Okasaki 的《Purely Function Data Structures》（论文 PDF ，完全成熟的书）。
There are two concepts of interest here. First, persistent data structures. If all elements of the tree are immutable, then one can derive a new tree from the original tree by replacing some parts, but referring to the older parts, thus saving time and memory.
For example, if you were to add a third Port to the Node that has two ports already, you'd have to create a new Scene, a new Scene's Node's descendant, and the Node that you are changing. The other Node and all of the Ports do not need to be created anew -- you just refer to them in the new Scene/Nodes.
The other concept is that of a Zipper. A zipper is a way to "navigate" through a persistent data structure to optimize local changes. For instance, if you added four new Ports instead of just one, but you added each Port one at a time, you'd have to create four new Scenes, and eight new Nodes. With a zipper, you defer such creations until you are done, saving up on those intermediary objects.
The best explanation I ever read about zipper is here.
Now, use of a zipper to navigate a data structure remove the need to have back-links. You can have back-links in an immutable structure, by clever use of recursive constructors. However, such a data structure would not be persistent. Non-persistent immutable data structures have lousy modification performance, because you need to copy the whole data each time.
As for academic literature, I recommend Purely Function Data Structures, by Okasaki (dissertation PDF, fully fledged book).
如果你的树是不可变的，那么如果你想以任何方式改变它，你就必须生成一棵新树。
这听起来很糟糕，但如果所有节点都是不可变的，那就不是了！由于您不需要复制不可变对象，因此除了您所做的更改之外，您的新树将主要引用旧树。
您必须以这样的方式设计树，即每个不可变树都引用其他不可变树。这样您也不需要重现整个不可变树。
但如果你走不可变的树路线，那么你就不能有反向链接。否则你不能重用子树。
If your tree is immutable, then if you want to change it in anyway you have to produce a new tree.
This sounds bad, but its not if all your nodes are also immutable! Since you don't need to make copies of immutable objects, your new tree will mostly refer to the old tree except for the changes you made.
You'll have to design your tree in such a way that each immutable tree refers to other immutable trees. This way you won't need to reproduce the entire immutable tree either.
But if you go the immutable tree route, then you can't have back links. Otherwise you can't reuse sub trees.