CODEWITHSUNDEEP
haskellinsertbinary-search-tree
J Freebird
J Freebird

Reputation: 3910

implementing binary search tree insertion in Haskell

I'm implementing the insert function of a BST, below is my code:

data Tree a = Empty | Branch a (Tree a) (Tree a) 
    deriving (Show, Eq)

tinsert             :: Tree a -> a -> Tree a 
tinsert Empty a         = Branch a Empty Empty
tinsert (Branch a left right) b
    | b == a = Branch a left right
    | b < a = Branch a (tinsert left b) right
    | b > a = Branch a left (tinsert right b)

When I was loading this function in ghci, it gave me many errors, which seem to be related to the comparison parts. I don't see any problem with it. I'm new to Haskell, could anybody help? Thanks a lot.

Upvotes: 8

Views: 10862

Answers (1)

Chris Taylor
Chris Taylor

Reputation: 47382

Changing the type of tinsert to

tinsert :: (Ord a) => Tree a -> a -> Tree a

fixes it.

This is necessary because the functions (<) and (>) are from the Ord typeclass, and you need to own up to that in the type signature.

You also use == and (==) :: Eq a => a -> a -> Bool, but Eq is a superclass of Ord, so the compiler knows that if you have (<) available you already have ==, so you don't need to say Eq a as well.

Upvotes: 12

Related Questions