[Haskell] Beginner - Binary Search Tree Question

[Tillmann Rendel]

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