J'ai le problème suivant: j'ai un arbre d'objets de différentes classes où une action dans la classe enfant invalide le parent. En langues impératives, il est trivial à faire. Par exemple, en Java:
public class A {
private List<B> m_children = new LinkedList<B>();
private boolean m_valid = true;
public void invalidate() {
m_valid = false;
}
public void addChild(B child) {
m_children.add(child);
child.m_parent = this;
}
}
public class B {
public A m_parent = null;
private int m_data = 0;
public void setData(int data) {
m_data = 0;
m_parent.invalidate();
}
}
public class Main {
public static void main(String[] args) {
A a = new A();
B b = new B();
b.setData(0); //invalidates A
}
}
6 Réponses :
Je n'ai pas beaucoup d'expérience avec Haskell, mais aussi loin que je sais que ce n'est pas possible d'avoir des cercles dans le graphique de référence dans des langues fonctionnelles pures. Cela signifie que:
L'essentiel est, je n'essaierais pas de prendre un algorithme Java (ou autre langue impérative) et essayer de le convertir en haskell. Au lieu de cela, essayez de trouver un algorithme plus fonctionnel (et peut-être même une structure de données différente) pour résoudre le problème.
Dans votre clarification, il n'est pas tout à fait clair si vous devez invalider uniquement le parent direct de l'objet qui a changé ou tous ses ancêtres dans la hiérarchie, mais cela n'a pas beaucoup d'importance. Étant donné que l'invalidation d'un objet signifie essentiellement de la modifier et que cela n'est pas possible, vous devez essentiellement créer un duplicata de cet objet modifié, puis vous devez faire valoir son parent à ce sujet, vous devez donc créer un nouvel objet pour cela. . Cela continue jusqu'à ce que vous arriviez à la racine. Si vous avez une nouvelle récursion pour traverser l'arborescence afin de "modifier" votre objet, vous pouvez recréer le chemin de cet objet à la racine de votre sortie de la récursion.
espère que cela a eu sens. : s
* Comme indiqué dans les commentaires de Joisetman et dans d'autres réponses, il est possible de créer des graphiques de référence circulaires dans HASKELLL à l'aide d'une évaluation paresseuse.
En fait ce n'est pas vrai. Dans Haskell Laziness nous permet de définir une structure de données en fonction de lui-même, même de manière très complexe (Google "attachant le nœud"). Donc, une liste doublement liée n'est pas un problème. Mais vous avez des problèmes lorsque vous essayez de modifier l'un des éléments de la liste :)
Pour répondre à la question de votre titre: Oui, vous pouvez créer des nœuds qui ont des liens vers leurs parents ainsi que leurs enfants. Exemple: La question est de savoir si c'est utile pour votre cas d'utilisation particulier (souvent ce n'est pas). maintenant la question de votre corps: vous " De droite, vous ne pouvez pas modifier une valeur après sa création. Donc, une fois que vous avez un arbre valide, vous aurez toujours un arborescence valide aussi longtemps que la variable référençant cet arborescence d'une portée. Vous n'avez pas vraiment décrit quel problème vous essayez de résoudre, Donc, je ne peux pas vous dire comment modéliser fonctionnellement ce que vous essayez de faire, mais je suis sûr qu'il y a un moyen sans muter l'arbre.
Le problème que j'essaie de résoudre est ce qui suit: j'ai une application qui modifie les documents. Un document est une hiérarchie d'objets. Lorsque les propriétés des objets pour enfants sont modifiées, le document doit être défini sur un état non valide, de sorte que l'utilisateur sait que le document doit être validé.
Recherchez à l'aide de l'instance Foncteur du type Par exemple, votre problème est peut-être quelque chose comme ceci: vous voulez insérer un élément dans un Arbre binaire, mais seulement si ce n'est pas déjà présent. Vous pouvez le faire avec quelque chose comme: afin que la fonction renverra Espérons que cela est pertinent pour tout ce que vous essayez de faire. peut-être type. rien si nous avons trouvé l'élément à être déjà présent ou renvoyer Juste le nouvel arbre avec l'élément inséré.
Modification d'un arbre qui pourrait nécessiter des excursions fréquentes dans le chemin de la racine et de l'arrière semble être le travail parfait pour une variante de la structure de données à glissière avec des "cicatrices", dans la terminologie du papier d'origine par HUET; Les échantillons de code du papier suggèrent également un nom de "fermeture à glissière de mémorisation". Bien sûr, avec certains soins, une fermeture à glissière régulière pourrait également être utilisée, mais la version augmentée pourrait être plus pratique et / ou efficace à utiliser.
L'idée de base est la même que celle derrière une fermeture à glissière régulière, qui permet déjà à un arbre de monter et de descendre d'un arbre de manière purement fonctionnelle (sans aucun point de dos explicite), mais une opération «montez» suivie de Une opération "baisser" devient un non-op, laissant la mise au point sur le nœud d'origine (alors que la fermeture à glissière ordinaire, il le déplacerait au frère le plus à gauche du nœud d'origine).
Voici un lien vers le papier: Gérard Huet, Perle fonctionnelle: la fermeture à glissière . Il n'ya que six pages, mais les idées qui y sont contenues sont d'une grande utilité pour tout programmeur fonctionnel.
Un article sur des fermetures à glissière à Haskell scienceblogs.com/goodmath/2010/01/...
Merci pour le document, j'ai déjà lu la structure à glissière avant. Je ne comprends pas comment l'utiliser dans mon programme cependant pour la tâche à la main. Par exemple, il n'est pas possible de monter et de définir un nouveau parent à l'enfant avec la propriété "invalide" définie sur true, car l'invalidation doit être valide pour tous les enfants. Si j'utilise la structure de fermeture à glissière, je devrais changer l'objet parent pour tous les enfants et, étant donné que mon arbre est de 6 couches de profondeur, ce changement entraînera l'ondulation à l'objet racine.
Il y a aussi un autre problème: je comprends comment utiliser les fonctions données ("go_up", "go_left", etc.), et je comprends également le concept de la fermeture à glissière (utilisez essentiellement les arguments locaux comme des variables mises à jour destructivement), mais je n'ai pas t comprendre comment le combiner avec le reste du programme. Supposons que j'utilise la fonction 'go_up'. Où puis-je stocker le résultat? Est-ce que je le stocke dans une liste? Et si oui, alors où puis-je stocker la liste? Devrais-je faire un enregistrement contenant toutes les «données actuelles», telles que les données de la structure de fermeture à glissière? Des solutions à cela grandement apprécié.
Je ne suis pas sûr de comprendre votre premier commentaire. Si vous mettez à jour le parent d'un nœud, tous les frères et sœurs du nœud auront également un parent mis à jour à partir de ce point. Si vous devez aller plus loin - au noeud grand-parent peut-être - alors toute mise à jour de la mise à jour sera visible comme une mise à jour du nœud de grand-parent sur tout «nœuds de cousin» du nœud, l'accent était mis à l'origine. Etc. C'est toute l'idée derrière la fermeture à glissière: vous apportez des changements localement, puis à tout moment, vous pouvez extraire le nœud racine de la fermeture à glissière pour obtenir l'arborescence d'origine avec toutes vos mises à jour effectuées.
En ce qui concerne le stockage du résultat, il s'agit de la même question que "lorsque je suis une nouvelle entrée sur une liste, où puis-je stocker la liste plus longue résultante?". :-) Toutes les fonctions de manipulation de la fermeture à glissière (cela inclut des fonctions pour se déplacer sur la fermeture à glissière ainsi que les fonctions d'insertion / mise à jour / Supprimer) agissent sur des "emplacements de fermeture à glissière" (LOC pour court-circuit) et renvoyer de nouveaux locs; Ensuite, vous pouvez prendre ces nouveaux LOC et les manipuler plus loin, ou si vous avez terminé de mettre à jour votre arbre, grimperez le chemin à la racine et extrayez le nœud racine (= l'arbre entier) de la fermeture à glissière dans sa forme nouvellement mise à jour. J'espère que cela t'aides.
Si ce qui précède n'est pas clair (et je ne suis pas entièrement satisfait de mon phrasé - ce n'est que mon premier coup ...), je n'ai qu'une question avant de faire une autre tentative: après avoir mis à jour un "nœud d'objet", vous Voulez-vous invalider l'ensemble du document (définir un drapeau sur le nœud racine le plus probablement), n'est-ce pas? Ou s'agit-il de la racine qui doit être mise à jour? Toute seule façon est d'accord avec une fermeture à glissière, demandant simplement d'ajuster tous les exemples que je peux penser à votre cas d'utilisation ... De plus, où souhaitez-vous que l'accent soit mis après la mise à jour et l'invalidation est effectué? (Le nœud enfant ciblé à l'origine? La racine?)
Après avoir mis à jour le nœud d'objet, je souhaite invalider l'ensemble du document en définissant un indicateur dans le nœud racine. En ce qui concerne l'accent, le nœud racine serait bien.
Dans ce cas, commencez par construire une fermeture à glissière pour l'arborese entière, puis descendez-vous au nœud que vous souhaitez, exécutez votre mise à jour, go_up plusieurs fois jusqu'à ce que vous soyez à la racine (vous Peut découvrir si vous êtes à la racine par motif correspondant - seuls les LOC racines ont le champ de chemin de chemin défini sur TOP ), mettez à jour le drapeau de validation à la racine, puis extrayez votre arbre. Et Voilà, vous avez maintenant un arbre exactement comme l'original, mais avec le nœud enfant modifié et la réinitialisation du drapeau de validation à la racine.
Notez que le papier de HUET décrit des fermetures à glissière sur l'arborescence qui ne tiennent que des données sur les feuilles, cependant adaptant l'idée des arbres qui ont des nœuds d'intérieur «décorés» sont simples. Vous devrez probablement lire sa section sur des fermetures à glissière sur les arbres hétérogènes, cependant.
N'est-ce pas terriblement inefficace, cependant? Mon noeud racine que j'ai besoin de changer 'invalide' contient beaucoup de choses. Chaque instance a 30 champs. Si je repensez l'instance racine à chaque fois que je change un détail, mon programme sera terriblement inefficace. Ceci est également vrai pour les nœuds enfants contenant beaucoup d'informations.
Les fermetures à glissière peuvent être extrêmement efficaces, voir par ex. Stackoverflow.com/Questtions/2531753/... (et peut-être suivre le lien vers le papier là-bas). Mais finalement, vous devrez effectuer des mesures pour découvrir ce qui est efficace dans votre cas particulier. Il est peut-être vrai que le remplacement des 30 champs signifie simplement remplacer 30 pointeurs ... puis si vous exécutez vos mises à jour par lots, marquez uniquement la racine comme invalide une fois par lot, il ne devrait vraiment pas y avoir de problème. Vous aurez juste à profil pour être sûr.
Voici un code de fermeture à glissière qui démontre une modification facile des données un curseur de curseur ainsi que d'une propriété "globale" de l'arbre. Nous construisons un arbre, déplacons le curseur sur le nœud contenant initialement un 1, changez-le à un 3, et laissez-le sur un curseur pointant sur ce nœud dans un arbre entièrement mis à jour.
Left True | +- Right 1 | `- Right 2 Left False | +- Right 3 | `- Right 2 Cursor at Right 3
Merci. D'après ce que je comprends, le code ci-dessus procède aux éléments suivants: 1) crée un arbre en main. 2) Obtient un enfant en obtenant un curseur. 3) Définit les données, invalide l'arborescence et renvoie un nouvel arborescence racine. L'invalidation se produit comme ceci: un nouveau nœud racine est construit sur le nouveau drapeau valide et le reste de l'arborescence. Ai-je compris le ci-dessus correctement?
C'est correct, avec la mise en garde que SetData ne vous donne pas simplement la racine du nouvel arbre, mais un nouvel arbre avec le curseur défini au même endroit que dans l'arborescence d'origine (vous pouvez donc continuer à modifier les changements locaux ultérieurs).
Une autre note est que ce code pourrait être rendu plus efficace en ne reconstrant pas l'arborescence lorsque la racine est déjà invalide.
Et si le nœud racine appelle un rappel lorsqu'il est invalidé? En Java, je peux avoir une liste d'objets à notifier lorsque l'objet est invalidé. Comment puis-je faire ça avec Haskell? Aurai-je besoin de reconstruire l'objet à chaque fois qu'un nouveau rappel est ajouté à l'objet? Qu'en est-il de ces références aux racines précédentes qui ne sont pas mises à jour? Avec Java, une mise à jour d'un membre dans la racine se reflète sur tous les objets qui font référence à cet objet.
Il est difficile de fournir des réponses totalement générales à ces questions. N'oubliez pas que la reconstruction de la racine est une opération très bon marché, car les sous-arbres suspendus ne sont pas affectés. En outre, l'utilisation d'une fermeture à glissière telle que faite ici signifie qu'il n'y a aucun problème de références persistantes à la vieille racines laissée pendante. Ajout d'un nouveau rappel implique donc de reconstruire le nœud racine, mais ce n'est pas une grosse affaire. Si vous avez un autre cas de problème spécifique, je vous encourage à partir de quelque chose comme ce code et de la publier comme une autre question afin que vous puissiez obtenir des réponses concrètes.
La paresse ne pourrait pas veiller à faire en sorte que la validation ne se produise pas trop souvent? De cette façon, vous n'avez pas besoin de stocker le champ Par exemple, si vous ne validez que sur Enregistrer, vous pouvez modifier les objets à votre contenu de votre cœur, sans revalidation de tout le temps; Ce n'est que lorsque l'utilisateur appuie sur le bouton "Enregistrer" est la valeur de Code incomplet et incomplet: Je suppose que la validité globale du document ne dépend que des sous-documents (simulées ici en veillant à ce qu'ils contiennent une chaîne non vide). Au fait, je pense que vous oublié un m_valid . validateateoc calculé. Puisque je ne sais pas à coup sûr de votre notion de moyens valides et de ce dont vous en avez besoin, je pourrais être totalement de la marque. a.addchild (b); dans principal .
Le document valide signifie qu'il passe un certain test. L'idée ici est que l'utilisateur modifie le document, puis la valide.
Pour ajouter sur les réponses de Sepp2k et Tal Pressman, vous pouvez également écrire un code HASKELL pour imiter exactement la manière de faire des choses, en échappant au monde fonctionnel pur et en utilisant le
St ouio monade. Utilisation deStref S pour les pointeurs "modifiables".Intéressant. Comment ça marche? Le compilateur traite-t-il Stref comme une construction spéciale? Et quelles sont les différences entre Stref et ioref? J'ai googlé, mais je ne suis pas venu avec quelque chose de facile à comprendre.