¿Cómo manipulo un árbol de objetos inmutables?

Question

Estoy construyendo una aplicación completa a partir de objetos inmutables para que el multi-threading y deshacer sea más fácil de implementar. Estoy usando el Google Collections Library que proporciona versiones inmutables de Mapa, Lista y Conjunto.

Mi modelo de aplicación se parece a un árbol:

• Escena es un objeto de nivel superior que contiene una referencia a un nodo raíz.
• Cada nodo puede contener nodos y puertos secundarios.

Un gráfico de objetos podría tener este aspecto:

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

Si todos estos objetos son inmutables, controlado por un objeto de nivel superior SceneController:

• ¿Cuál es la mejor manera de construir esta jerarquía?
• ¿Cómo reemplazaría un objeto que es arbitrariamente profundo en el árbol de objetos?
• ¿Hay alguna manera de admitir enlaces de retroceso, p. un nodo que tiene un atributo "principal"?

Y más en general:

• Tener cualquier patrón surgió para hacer frente a este tipo de datos?
• ¿Hay literatura (académica) disponible sobre el tema?
• ¿Es esta una buena idea?

Answer 1

Aquí hay dos conceptos de interés. Primero, estructuras de datos persistentes. Si todos los elementos del árbol son inmutables, uno puede derivar un nuevo árbol del árbol original reemplazando algunas partes, pero haciendo referencia a las partes más antiguas, ahorrando así tiempo y memoria.

Por ejemplo, si añadiera un tercer puerto al nodo que ya tiene dos puertos, tendría que crear una nueva escena, un nuevo descendiente del nodo de escena y el nodo que está cambiando. El otro Nodo y todos los Puertos no necesitan ser creados de nuevo, solo se refieren a ellos en la nueva Escena/Nodos.

El otro concepto es el de una cremallera . Una cremallera es una forma de "navegar" a través de una estructura de datos persistente para optimizar los cambios locales.Por ejemplo, si agrega cuatro Puertos nuevos en lugar de uno solo, pero agregó cada Puerto de uno en uno, tendrá que crear cuatro Escenas nuevas y ocho Nodos nuevos. Con una cremallera, pospones esas creaciones hasta que termines, ahorrando en esos objetos intermedios.

La mejor explicación que he leído sobre la cremallera es here.

Ahora, el uso de una cremallera para navegar por una estructura de datos elimina la necesidad de tener enlaces de retroceso. Usted puede tener enlaces de retroceso en una estructura inmutable, mediante el uso inteligente de constructores recursivos. Sin embargo, dicha estructura de datos no sería persistente. Las estructuras de datos inmutables no persistentes tienen un rendimiento de modificación pésimo, porque necesita copiar la información completa cada vez.

En cuanto a literatura académica, recomiendo estructuras de datos puramente funcionales, por Okasaki (dissertation PDF, fully fledged book).

Answer 2

Si el árbol es inmutable, a continuación, si desea cambiarlo en cualquier caso se tienen que producir un nuevo árbol.

Esto suena mal, pero no lo es si todos sus nodos también son inmutables. Como no necesita hacer copias de objetos inmutables, su nuevo árbol se referirá principalmente al árbol anterior, excepto por los cambios que realizó.

Tendrá que diseñar su árbol de tal manera que cada árbol inmutable se refiera a otros árboles inmutables. De esta forma, tampoco será necesario reproducir todo el árbol inmutable.

Pero si vas a la ruta de árbol inmutable, entonces no puedes tener enlaces de regreso. De lo contrario, no puede reutilizar árboles secundarios.