[Haskell] Beginner - Binary Search Tree Question

[Benjamin Jakobus]

Wow, this was a fast reply :-) Thank you Mihai! This works.

On 12 February 2011 10:45, Mihai Maruseac <mihai.maruseac at gmail.com> wrote:

> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell/attachments/20110212/d2221174/attachment.htm>