Ho implementato un algoritmo di condivisione strutturale per la creazione di alberi persistenti in stile Clojure, ma si basa sul nodo figlio che conosce il proprio genitore.
function fork
return new Node
children: this.children
value: this.value
parent: this.parent.fork()
Se si chiama fork su un nodo nell'albero, verrà creato un nuovo nodo, con un genitore biforcuto, in modo ricorsivo fino alla radice. In questo modo puoi prendere qualsiasi nodo, cambiarlo e quindi avere accesso a una versione immutabile dell'intero albero.
Tuttavia, l'idea fondamentale per questa struttura di dati è che dovrebbe essere un grafo aciclico diretto, con un riferimento a un genitore che fornisce i cicli del grafico. Ho anche avuto alcuni problemi con la creazione del nuovo genitore. Il nodo dovrebbe conoscere il genitore biforcuto, ma per forzare il genitore dovrebbe sapere del suo nuovo figlio. Questo è praticamente una dipendenza circolare, ma sono riuscito a eluderlo con alcuni riferimenti e mutazione.
C'è un modo più sano per farlo?