如何操作不可变对象树？

Question

我正在使用不可变对象构建整个应用程序,以便更容易实现多线程和撤消.我正在使用Google Collections Library,它提供了Map,List和Set的不可变版本.

我的应用程序模型看起来像一棵树:

对象图可能如下所示:

Scene
 |
 +-- Node
      |
      +-- Node 
           |
           +- Port
      +-- Node
           |
           +- Port
           +- Port

如果所有这些对象都是不可变的,则由顶级SceneController对象控制:

更一般地说:

Answer 1

这里有两个感兴趣的概念.首先,持久的数据结构.如果树的所有元素都是不可变的,则可以通过替换某些部分从原始树派生新树,但是引用较旧的部分,从而节省时间和内存.

例如,如果要向已有两个端口的节点添加第三个端口,则必须创建一个新场景,一个新场景的节点后代以及要更改的节点.另一个节点和所有端口不需要重新创建 - 您只需在新的场景/节点中引用它们.

另一个概念是拉链.拉链是一种"导航"持久数据结构以优化本地更改的方法.例如,如果您添加了四个新端口而不是一个,但是您一次添加一个端口,则必须创建四个新场景和八个新节点.使用拉链,您可以推迟这些创作,直到完成为止,节省了这些中间对象.

我读过有关拉链的最佳解释就在这里.

现在,使用拉链来导航数据结构,无需使用反向链接.通过巧妙地使用递归构造函数,您可以在不可变结构中具有反向链接.但是,这样的数据结构不会持久.非持久性不可变数据结构具有糟糕的修改性能,因为您每次都需要复制整个数据.

至于学术文献,我推荐Okasaki的Purely Function Data Structures(论文PDF,完全成熟的书).

两个都提到Zippers和Okasaki的+1,在字面上,他们写了关于这个主题的书.另一个有趣的概念是Clojure 1.1的*transient*数据结构.(基本上,一个暂时不持久的数据结构.)事实上,Clojure一般很有意思:如果Okasaki写了关于功能数据结构的书,Rich Hickey写了这个库.而且,BTW:Clojure数据结构是*具体*以这样的方式编写的,它们*可以*用作Java库.它们完全独立于Clojure语言和Clojure标准库. (2认同)