如何操作不可變對象樹？

Question

我使用不可變對象構建整個應用程序，以便多線程和撤銷變得更容易實現。我正在使用提供Map，List和Set的不可變版本的Google Collections Library。

我的應用程序模型看起來就像一棵樹：

• 場景是包含一個根節點的引用的頂層對象。
• 每個節點可以包含子節點和端口。

對象圖可能是這樣的：

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

如果所有這些對象是不可改變的，由頂級SceneController對象控制：

• 什麼是最好的方式構建這個層次？
• 我將如何替換對象樹中任意深度的對象？
• 有沒有一種方法可以支持反向鏈接，例如具有「父」屬性的節點？

更普遍：

• 有任何的型態出現了處理這種類型的數據？
• 有沒有關於這個主題的（學術）文獻？
• 這是個好主意嗎？

Answer 1

這裏有兩個感興趣的概念。首先，持久數據結構。如果樹的所有元素都是不可變的，那麼可以通過替換某些部分從原始樹中派生出新的樹，但是指的是較舊的部分，從而節省時間和內存。例如，如果要向已具有兩個端口的節點添加第三個端口，則必須創建一個新的Scene，一個新的Scene's節點的後代以及您正在更改的Node。其他節點和所有端口不需要重新創建 - 您只需在新的場景/節點中引用它們即可。

另一個概念是拉鍊的。拉鍊是一種通過持久數據結構「導航」以優化本地更改的方式。例如，如果您添加了四個新端口而不是一個端口，但您一次添加了一個端口，則必須創建四個新場景和八個新節點。使用拉鍊，您可以推遲創作，直到完成，節省中間物品。

我讀過關於拉鍊的最好解釋是here。

現在，使用拉鍊來導航數據結構可以消除對後端鏈接的需求。你可以通過巧妙使用遞歸構造函數在不可變結構中具有反向鏈接。但是，這樣的數據結構不會是持久。非永久性不可變數據結構的修改性能差，因爲您需要每次都複製整個數據。至於學術文獻，我推薦Okasaki的純功能數據結構（dissertation PDF,fully fledged book）。

Answer 2

如果你的樹是不可變的，那麼如果你想改變它，你必須生成一棵新的樹。

這聽起來很糟糕，但它不是你的所有節點也是不可變的！由於您不需要製作不可變對象的副本，所以除了您所做的更改之外，您的新樹大多會引用舊樹。

你要設計你的樹以這樣的方式，每個不可改變樹指其他不可變樹。這樣你就不需要重現整個不可變樹。

但是如果你去不可變樹的路線，那麼你就不能有反向鏈接。否則，你不能重用子樹。