[Haskell] Beginner - Binary Search Tree Question

[Mihai Maruseac]

On Sat, Feb 12, 2011 at 12:39 PM, htc2011 <jakobusbenne at gmail.com> wrote:
>
> Hi All,
>
> I am learning Haskell and can't understand the following problem. Maybe
> somebody could advise me on a solution?
>
> Using GHCI, I have the following definition of a BST:
> data Ord a => BST a = EmptyBST | Node ( BST a ) a ( BST a ) deriving (Show)
>
> I want to determine the number of leaves that a tree using the above
> definition has:
> 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
>
> However whenever I load my haskell file containing the above code into GHCI,
> I get the following error:
>
> Could not deduce (Eq (BST a)) from the context (Ord a)
>      arising from a use of `==' at a8.hs:17:3-15
>    Possible fix:
>      add (Eq (BST a)) to the context of
>        the type signature for `numLeaves'
>      or add an instance declaration for (Eq (BST a))
>    In the expression: b == EmptyBST
>    In a stmt of a pattern guard for
>                 the definition of `numLeaves':
>          b == EmptyBST
>    In the definition of `numLeaves':
>        numLeaves (Node b a c)
>                    | b == EmptyBST = 1 + numLeaves c
>                    | c == EmptyBST = 1 + numLeaves b
>                    | otherwise = numLeaves b + numLeaves c
>
> Could anybody explain to me what this means? / How to get around this?
>
> Thank you for your time!

Hi,

You are comparing two BST instances in the second expression for
numLeaves without declaring the Eq instance.

numLeaves (Node b a c) will bind b and c to two BST instances. When
you are comparing b and c with EmptyBST an error is raised.

To solve this, you'll have to declare an Eq instance, just like you've
declared a Show one:

data Ord a => BST a = EmptyBST | Node ( BST a ) a ( BST a ) deriving (Show, Eq)

This will solve it :D

-- 
Mihai