CODEWITHSUNDEEP
haskelltypesbinary-search-treemembership
Abraham P
Abraham P

Reputation: 15471

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

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?

Upvotes: 3

Views: 1667

Answers (1)

Bartek Banachewicz
Bartek Banachewicz

Reputation: 39370

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

Upvotes: 7

Related Questions