Quelles sont les applications des rosiers?

J'ai récemment découvert la structure des données du rosier, mais en partant d'une datadéfinition de Haskell et de la minuscule description de Wikipédia , j'ai du mal à comprendre quelles applications un rosier pourrait avoir.

Pour référence, la datadéfinition de Haskell :

data RoseTree a = RoseTree a [RoseTree a]

Pour ceux qui ne connaissent pas Haskell - il s'agit d'une définition de type de données récursive avec un type arbitraire a, où le constructeur de type est fourni avec un littéral de type asuivi d'une liste de type éventuellement vide RoseTreesur le même type a.

La façon dont je le vois:

• Cette structure de données n'est pas ordonnée par défaut (bien que je suppose que la plupart des applications pratiques implémentent une certaine forme d'ordonnancement pour la recherche)

• La structure de données n'applique à aucun moment un nombre fixe de nœuds par couche, à l'exception de la racine globale, qui doit avoir un seul nœud

Étant donné cette quantité minimale d'informations, j'ai du mal à déterminer quand on pourrait utiliser ce type d'arbre.

En plus de la question dans le titre, si la recherche est effectivement implémentée dans la plupart des applications d'un rosier, comment cela se fait-il?

Vous semblez avoir une mentalité trop "de structures de données et d'algorithmes". Tous les arbres ne sont pas des arbres de recherche. Les structures de données sont souvent conçues pour correspondre ou capturer des aspects d'un modèle de domaine.

Les expressions S sont presque exactement des rosiers. (Ou plutôt, je dirais qu'ils sont généralement considérés comme des rosiers. Wikipedia a raison de dire qu'ils ressemblent davantage à des arbres binaires, mais ce que vous pourriez appeler des expressions S "correctes" ne diffèrent que légèrement des rosiers.) En tout cas, vous pouvez les utiliser comme représentation générique pour un arbre de syntaxe abstraite. L'avantage de cette opération est que vous pouvez facilement écrire des opérations génériques, par exemple «trouver toutes les variables» ou «permuter les paramètres» ou «renommer ce symbole». Il est également extensible en ce que l'ajout d'un nouveau type de nœud à votre syntaxe abstraite ne nécessite souvent rien de vraiment changer. Les inconvénients sont qu'il n'y a pas vraiment de contraintes, donc cela ne vous empêche pas a priori d'écrire des bêtises. Cela peut être atténué pour les utilisateurs par des techniques standard de type de données abstraites, mais l'implémentateur de transformations et autres doit traiter la représentation non structurée même s'ils "savent" que l'entrée est structurée via un invariant de type de données. Bien sûr, lorsque cette certitude est déplacée (peut-être parce que les choses ont changé), les erreurs ont tendance à être imprévisibles et difficiles à déboguer.

En pratique, alors que le Data.Treemodule des bibliothèques standard fournit un rosier, presque personne ne l'utilise dans la communauté Haskell. La définition de types de données personnalisés qui capturent explicitement les contraintes est si simple qu'il n'y a guère de raison d'utiliser un type de bibliothèque générique. De plus, il y a eu énormément de recherches et de pratiques autour de l'exécution d'opérations génériques sur des types personnalisés, ce qui élimine de nombreux avantages de l'utilisation d'une représentation générique. Enfin, les Haskellers ont tendance à être très en faveur de contraintes explicites et forcées et sont prêts à payer pour l'obtenir.

Pour répondre à votre dernière question, la recherche d'un AST n'est souvent pas importante et / ou les AST sont généralement supposés être suffisamment petits pour que le simple fait de marcher le tout soit acceptable. Certes, il n'est pas rare de collecter des définitions dans une structure de données distincte avec des références dans l'AST qui pourraient être considérées comme une sorte d'index. De même, certaines passes d'optimisation créeront (généralement localement et temporairement) des index pour simplifier et accélérer leur fonctionnement. La structure de l'AST correspond à l'entrée et ne peut donc pas être «rééquilibrée» ou quelque chose du genre. En tant que tel, il est rare que l'AST lui-même contienne des informations d'indexation ou des informations pour aider à la «recherche».