Contando elementos en un árbol en Haskell

Question

Básicamente he hecho un tipo de árbol de árbol polimórfico y necesito una manera de contar la cantidad de elementos en un árbol dado. Aquí está la declaración de mi árbol de tipo de datos:

data Tree a = Empty 
| Leaf a 
| Node (Tree a) a (Tree a) 
deriving (Eq, Ord, Show) 

Así que puede definir un árbol de INT así:

t :: Tree Int 
t = Node (Leaf 5) 7 (Node (Leaf 2) 3 (Leaf 7)) 

Sin embargo, necesito una función para contar el número de elementos en una de estas liza. He definido esta función recursiva, pero me sale el error "tipo inferido no es suficientemente general":

size :: Tree a -> Int 
size Empty = 0 
size (Leaf n) = 1 
size (Node x y z) = size x + size y + size z 

¿Hay algo aquí que no debería estar haciendo?

Answer 1

creo que es simplemente un error al escribir

size (Node x y z) = size x + size y + size z 

el cual debe ser sólo

size (Node x y z) = size x + size z + 1 

puesto que y no es una sub-árbol, pero sólo el elemento almacenado.

O para que sea aún más clara

size (Node left elem right) = size left + size right + 1 

---

Técnicamente, el error se produce porque el término size y no sólo tienen sentido si y es de nuevo un árbol cuyo tamaño puede ser calculada. Por lo tanto, el tipo de esta cláusula se inferiría a Tree (Tree a) -> Int, que es, comparado con el Tree a -> Int real, no general suficiente.

Answer 2

Mire usted última cláusula: mirando a la izquierda, en Node x y z, ¿cuál es el tipo de y? ¿Tiene sentido size y?