What is wrong with my function testing for membership in a binary search tree?

Question

Lets say I have the following datatype:

data BinaryTree a = EmptyTree | Node a (BinaryTree a) (BinaryTree a) deriving (Eq, Ord, Show)

and the following function

  member a EmptyTree = False
  member a (Node x l r)
    | a < x = member a l
    | a > x = member a r
    | a == x = True

This function works.

examining the type of Node:

:t Node
Node :: a -> BinaryTree a -> BinaryTree a -> BinaryTree a

However, if the member function is given a signature: member :: Node a -> BinaryTree a -> Bool

(Node of type a and BinaryTree of type a producing a Bool)

it errors out with:

Not in scope: type constructor or class ‘Node’
A data constructor of that name is in scope; did you mean DataKinds?

Why is that? How can I define a function which accepts (and compares) Nodes and Trees of arbitrary types?

Answer 1

Node isn't a type; it's a:

• value of type BinaryTree when fully applied
• a data constructor for such a value (a -> BinaryTree a -> BinaryTree a -> BinaryTree a)

Both really mean the same, but it can be helpful to realize the appearance in two different contexts, namely pattern matching and construction.

Your member function most probably should take just the element to check for its existence:

member :: a -> BinaryTree a -> Bool

If you need additional constraints on the a (in the case of a binary tree, it's going to be Ord and Eq, most probably, you have to put them there too.

member :: (Ord a, Eq a) => a -> BinaryTree a -> Bool