Hi,
(these kind of questions are better posted to the Haskell-Cafe. The main
Haskell list is mostly used for announcements).
htc2011 wrote:
data Ord a => BST a = EmptyBST | Node ( BST a ) a ( BST a ) deriving (Show)
numLeaves :: Ord a => BST a -> Int
numLeaves EmptyBST = 0
numLeaves (Node b a c)
| b == EmptyBST = 1 + numLeaves c
| c == EmptyBST = 1 + numLeaves b
| otherwise = numLeaves b + numLeaves c
I try to explain the error message step-by-step:
Could not deduce (Eq (BST a)) from the context (Ord a)
arising from a use of `==' at a8.hs:17:3-15
You call the equality operator == on trees of type (BST a), but you
haven't defined it.
Possible fix:
add (Eq (BST a)) to the context of
the type signature for `numLeaves'
So you can either add a constraint, so that the caller of numLeaves need
to define equality for the tree she wants to use.
or add an instance declaration for (Eq (BST a))
Or you can define equality for all (BST a) trees once and forall.
If you want to define equality for all (BST a) trees, you can let GHC
derive it for you. Just change "deriving (Show)" into "deriving (Eq,
Show)" on the declaration of BSTTree.
That derived equality will work for the numLeaves function, but it might
not be what you want in general. For example, GHC would think that these
trees are different:
(Node (EmptyBST 1 EmptyBST) 2 Empty)
(Node Empty 1 (EmptyBST 2 EmptyBST))
But sometimes, it might be better to treat them as equal, since they
contain the same numbers.
But fortunately, there is a better way out for the numLeaves function:
Just use pattern matching instead of the equality operator:
numLeaves (EmptyBST) = 0
numLeaves (Node EmptyBST a c) = 1 + numLeaves c
numLeaves (Node b a EmptyBST) = 1 + numLeaves c
numLeaves (Node b a c) = numLeaves b + numLeaves c
By the way, you might want to think about the following question: Is it
really necessary to handle empty trees in the case for non-empty trees,
or can the recursion scheme made more regular?
Tillmann
_______________________________________________
Haskell mailing list
Haskell@haskell.org
http://www.haskell.org/mailman/listinfo/haskell
