Comment manipuler un arbre d'objets immuables?

Question

Je construis une application complète à partir d'objets immuables, ce qui rend l'implémentation et l'annulation de plusieurs threads plus faciles à mettre en œuvre. J'utilise le Google Collections Library qui fournit des versions immuables de Map, List et Set.

Mon modèle d'application ressemble à un arbre:

• Scène est un objet de niveau supérieur qui contient une référence à un nœud racine.
• Chaque nœud peut contenir des nœuds enfants et des ports.

Un graphe d'objet pourrait ressembler à ceci:

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

Si tous ces objets sont immuables, contrôlés par un objet SceneController de niveau supérieur:

• Quelle est la meilleure façon de construire cette hiérarchie?
• Comment est-ce que je remplacerais un objet qui est arbitrairement profond dans l'arbre d'objet?
• Existe-t-il un moyen de prendre en charge les back-links, par ex. un nœud ayant un attribut "parent"?

Et plus généralement:

• Avez des modèles pour faire face à émergé ce type de données?
• Y a-t-il de la littérature (académique) disponible sur le sujet?
• Est-ce une bonne idée?

Answer 1

Il y a deux concepts d'intérêt ici. Tout d'abord, structures de données persistantes. Si tous les éléments de l'arbre sont immuables, alors on peut dériver un nouvel arbre de l'arbre d'origine en remplaçant certaines parties, mais en se référant aux parties plus anciennes, ce qui économise du temps et de la mémoire. Par exemple, si vous deviez ajouter un troisième port au nœud qui a déjà deux ports, vous devrez créer une nouvelle scène, le descendant d'un nouveau nœud de scène et le nœud que vous modifiez. L'autre nœud et tous les ports n'ont pas besoin d'être créés à nouveau - vous vous référez simplement à eux dans la nouvelle scène/nœuds.

L'autre concept est celui d'un Zipper. Une fermeture à glissière est un moyen de «naviguer» à travers une structure de données persistante pour optimiser les changements locaux.Par exemple, si vous avez ajouté quatre nouveaux ports au lieu d'un seul, mais que vous avez ajouté un port à la fois, vous devez créer quatre nouvelles scènes et huit nouveaux nœuds. Avec une fermeture à glissière, vous reporter de telles créations jusqu'à ce que vous ayez terminé, économisant sur ces objets intermédiaires.

La meilleure explication que j'ai jamais lu sur la fermeture à glissière est here. Maintenant, l'utilisation d'une fermeture à glissière pour naviguer dans une structure de données supprimer le besoin d'avoir des back-liens. Vous pouvez avoir back-liens dans une structure immuable, par l'utilisation intelligente de constructeurs récursifs. Cependant, une telle structure de données ne serait pas persistante. Les structures de données immuables non persistantes ont des performances de modification minables, car vous devez copier les données entières à chaque fois.

En ce qui concerne la littérature académique, je recommande les structures de données de fonction pure, par Okasaki (dissertation PDF, fully fledged book).

Answer 2

Si votre arbre est immuable, alors si vous voulez le changer de toute façon, vous devez produire un nouvel arbre.

Cela semble mauvais, mais ce n'est pas si tous vos noeuds sont également immuables! Puisque vous n'avez pas besoin de faire des copies d'objets immuables, votre nouvel arbre se référera principalement à l'ancien arbre à l'exception des changements que vous avez faits.

Vous devrez concevoir votre arbre de telle sorte que chaque arbre immuable se réfère à d'autres arbres immuables. De cette façon, vous n'aurez pas besoin de reproduire l'arbre entier non plus. Mais si vous allez sur la route de l'arbre immuable, alors vous ne pouvez pas avoir de liens de retour. Sinon, vous ne pouvez pas réutiliser les sous-arbres.