Counting items in a tree in Haskell

Question

Basically, I created a data type of a polymorphic tree, and I need a way to count the number of elements in a given tree. Here is the declaration for my Tree data type:

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

So, I can define the Ints tree as follows:

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

However, I need a function to count the number of elements in one of these lists. I defined this recursive function, but I get the error: "the intended type is not general enough":

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

Is there something here that I should not do?

Answer 1

I think it's just a typo when you write

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

which should just be

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

since y is not a subtree, but only a saved item.

Or make it even more understandable

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

---

Technically, your error occurs because the term size y only makes sense if y again a tree whose size can be calculated. Therefore, the type of this sentence will be deduced on Tree (Tree a) -> Int , which, in comparison with the actual Tree a -> Int , and not general enough.

Answer 2

Look at the last sentence: looking at the left side in Node xyz , what is the type of y ? Does size y make sense?