Counting elements in a tree in Haskell

Question

Hi

Basically I've made a polymorphic tree data type and I need a way of counting the number of elements in a given tree. Here's 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 a tree of Ints like this:

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've defined this recursive function but I get the error "inferred type is not general enough":

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

Is there something here I shouldn't be doing?

Thanks

Ben

Answer 1

Look at you last clause: Looking at the left hand side, at Node x y z, what is the type of y? Does size y make sense?

Answer 2

I think it's just a typo when you write

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

which should just be

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

since y is no subtree but just the element stored.

Or to make it even clearer

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

---

Technically, your error occurs because the term size y does only make sense if y is again a tree whose size can be computed. Therefore the type of this clause would be inferred to Tree (Tree a) -> Int, which is, compared with the actual Tree a -> Int, not general enough.