Come faccio a manipolare un albero di oggetti immutabili?

Question

Sto costruendo un'intera applicazione con oggetti immutabili, in modo che multi-threading e undo diventino più facili da implementare. Sto usando lo Google Collections Library che fornisce versioni immutabili di Mappa, Elenco e Set.

Il mio modello di applicazione si presenta come un albero:

• scena è un oggetto di livello superiore che contiene un riferimento a un nodo principale.
• Ogni nodo può contenere nodi figlio e porte.

un oggetto grafico potrebbe essere simile a questo:

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

Se tutti questi oggetti sono immutabili, controllato da un oggetto di livello superiore SceneController:

• Qual è il modo migliore per costruire questa gerarchia?
• Come sostituire un oggetto che è arbitrariamente profondo nella struttura ad albero degli oggetti?
• C'è un modo per supportare i collegamenti di ritorno, ad es. un nodo con un attributo "genitore"?

E più in generale:

• ha nessun modelli emerse per affrontare questo tipo di dati?
• C'è letteratura (accademica) disponibile sull'argomento?
• È una buona idea?

Answer 1

Ci sono due concetti di interesse qui. Innanzitutto, strutture dati persistenti. Se tutti gli elementi dell'albero sono immutabili, è possibile ricavare un nuovo albero dall'albero originale sostituendo alcune parti, ma facendo riferimento alle parti più vecchie, risparmiando così tempo e memoria.

Ad esempio, se si dovesse aggiungere una terza porta al nodo che ha già due porte, sarà necessario creare una nuova scena, un nuovo discendente del nodo di una scena e il nodo che si sta modificando. Non è necessario creare nuovamente l'altro nodo e tutte le porte, basta fare riferimento a esse nella nuova scena/nodi.

L'altro concetto è quello di una cerniera . Una cerniera è un modo per "navigare" attraverso una struttura dati persistente per ottimizzare le modifiche locali.Ad esempio, se hai aggiunto quattro nuove porte invece di una sola, ma hai aggiunto ciascuna porta una alla volta, dovresti creare quattro nuove scene e otto nuovi nodi. Con una cerniera, rimandi tali creazioni fino a quando non hai finito, risparmiando su quegli oggetti intermediari.

La migliore spiegazione che abbia mai letto sulla chiusura lampo è here.

Ora, l'uso di una cerniera per navigare in una struttura di dati elimina la necessità di avere collegamenti di ritorno. È possibile avere back-link in una struttura immutabile, con l'uso intelligente di costruttori ricorsivi. Tuttavia, tale struttura dati non sarebbe persistente. Le strutture di dati immutabili non persistenti hanno prestazioni scadenti di modifica, poiché è necessario copiare l'intero dato ogni volta.

Come per la letteratura accademica, consiglio Purely Function Data Structures, di Okasaki (dissertation PDF, fully fledged book).

Answer 2

Se il tuo albero è immutabile, allora se vuoi cambiarlo in ogni caso devi produrre un nuovo albero.

Sembra male, ma non se tutti i nodi sono anche immutabili! Dato che non hai bisogno di fare copie di oggetti immutabili, il tuo nuovo albero si riferirà principalmente al vecchio albero ad eccezione delle modifiche che hai fatto.

Dovrai progettare il tuo albero in modo tale che ogni albero immutabile si riferisca ad altri alberi immutabili. In questo modo non avrai nemmeno bisogno di riprodurre l'intero albero immutabile.

Ma se si va sulla rotta dell'albero immutabile, non è possibile avere collegamenti di ritorno. Altrimenti non puoi riutilizzare gli alberi secondari.