En apprentissage haskell, et je ne peux vraiment voir la différence entreLes arbres dans Haskell
data Tree a = Leaf a | Branch [Tree a]
et
data Tree a = Leaf a | Branch (Tree a) (Tree a)
Quel est le meilleur selon vous? Quelle est l'implication de ces deux façons d'écrire?
La branche de la première contient une liste d'arbres, donc potentiellement n'importe quel nombre de sous-arbres. Le second est explicitement deux sous-arbres, donc un arbre binaire.
Le premier définit un arbre où chaque branche peut avoir arbitrairement beaucoup de sous-arbres (représentés comme une liste d'arbres) et le second définit un arbre où chaque branche a exactement deux sous-arbres. En d'autres termes, le premier est un arbre général et le second est un arbre binaire.
Le choix dépend de si vous souhaitez modéliser un arbre général ou un arbre binaire.
J'ai mis cela comme une réponse plutôt que de commentaires il a une mise en forme:
data Rose a = Branch a [Rose a]
deriving (Show)
sample1 :: Rose Int
sample1 = Branch 1 [Branch 2 [], Branch 3 [Branch 5 []], Branch 4 []]
C'est le même que le module de bibliothèque Data.Tree, bien que Data.Tree utilise des étiquettes sur le terrain et une type synonyme.
J'ai vu à la fois cet arbre et votre première définition appelée "Rosiers" bien qu'ils aient des formes légèrement différentes, donc la terminologie ne semble pas être entièrement précise. Mon interprétation est que c'est la liste "[Rose a]" intégrée dans le seul constructeur récursif qui la définit comme un arbre de Rose.
OK, mais dans les deux cas, Feuille et Branche sont définis par le langage, et je définis mon propre type Arbre. n'est-ce pas? –
@Stephane: Non. Dans les deux cas, ni le type 'Tree' ni les constructeurs' Leaf' et 'Branch' n'existaient auparavant, et vous définissez les trois avec votre définition' data'. – sepp2k
Salut sepp2k - l'arbre général défini dans la question est plus communément appelé un arbre de rose. Parfois, ils sont implémentés avec un constructeur Leaf séparé comme ci-dessus - parfois selon Data.Tree le constructeur de branche porte les données à la place. –