Todavía aprendiendo Haskell, y yo realmente no pueden ver la diferencia entreárboles en Haskell
data Tree a = Leaf a | Branch [Tree a]
y
data Tree a = Leaf a | Branch (Tree a) (Tree a)
lo que es mejor de acuerdo con usted? ¿Cuál es la implicación de estas dos formas de escribir?
La rama de la primera contiene una lista de árboles, por lo que potencialmente cualquier número de subárboles. El segundo es explícitamente dos subárboles, por lo tanto, un árbol binario.
El primero define un árbol donde cada rama puede tener arbitrariamente muchos subárboles (representados como una lista de árboles) y el último define un árbol donde cada rama tiene exactamente dos subárboles.
En otras palabras, el primero es un árbol general y el último es un árbol binario.
Entonces, cuál elegir depende de si desea modelar un árbol general o un árbol binario.
He puesto esto como una respuesta en lugar de comentario por lo que tiene algo de formato:
data Rose a = Branch a [Rose a]
deriving (Show)
sample1 :: Rose Int
sample1 = Branch 1 [Branch 2 [], Branch 3 [Branch 5 []], Branch 4 []]
Ésta es la misma que la Data.Tree módulo de biblioteca, aunque Data.Tree usa el campo-etiqueta y una tipo sinónimo
He visto tanto este árbol como tu primera definición llamada "Rose trees", aunque tienen formas ligeramente diferentes, por lo que la terminología no parece ser del todo precisa. Mi interpretación es que es la lista "[Rose a]" incrustada en el único constructor recursivo que la está definiendo como un árbol de rosas.
De acuerdo, pero en ambos casos Leaf y Branch están definidos por el idioma, y yo defino mi propio tipo Tree. no es así? –
@Stephane: No. En ambos casos, ni el tipo 'Tree' ni los constructores' Leaf' y 'Branch' existían anteriormente, y está definiendo los tres con su definición' data'. – sepp2k
Hola sepp2k: el "árbol general" definido en la pregunta se suele llamar un rosal. A veces se implementan con un constructor separado de Leaf como el anterior, a veces según Data.Tree, el constructor de Branch lleva los datos en su lugar. –