Beginner - Binary Search Tree Question
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! -- View this message in context: http://haskell.1045720.n5.nabble.com/Beginner-Binary-Search-Tree-Question-tp... Sent from the Haskell - Haskell mailing list archive at Nabble.com.
On Sat, Feb 12, 2011 at 12:39 PM, htc2011 <jakobusbenne@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
Wow, this was a fast reply :-) Thank you Mihai! This works. On 12 February 2011 10:45, Mihai Maruseac <mihai.maruseac@gmail.com> wrote:
On Sat, Feb 12, 2011 at 12:39 PM, htc2011 <jakobusbenne@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
Wow, this was a fast reply :-) Thank you Mihai! This works. -- View this message in context: http://haskell.1045720.n5.nabble.com/Beginner-Binary-Search-Tree-Question-tp... Sent from the Haskell - Haskell mailing list archive at Nabble.com.
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
participants (4)
-
Benjamin Jakobus -
htc2011
-
Mihai Maruseac -
Tillmann Rendel