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?
Counting nodes is the same as counting occurrences of the b type parameter, which is exactly what length does for any Foldable . All we have to do is wrap the tree to get something Foldable . Finally, you can count leaves and nodes using the bilength function from the Bifoldable class.
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.
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?
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With