implementing binary search tree insertion in Haskell

Question

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.

Please add the details of the error messages you are getting and what you've tried to fix them. — Ganesh Sittampalam
– Ganesh Sittampalam, Commented Jan 18, 2014 at 8:52
Since you are comparing the objects inside the tree, they must be members of the Ord typeclass. The type of < is Ord a => a -> a -> Bool. The correct type for your function would be Ord a => Tree a -> a -> Tree a. — user2407038
– user2407038, Commented Jan 18, 2014 at 8:59

3 revs, 3 users 57% · Accepted Answer · 2016-03-25 16:53:38Z

12

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.

edited Mar 25, 2016 at 16:53

community wiki

3 revs, 3 users 57%
Chris Taylor

Sign up to request clarification or add additional context in comments.

1 Comment

J Freebird Over a year ago

Hi Chris, thanks a lot, but it's actually tinsert :: (Ord a) =》 Tree a -> a -> Tree a. I fixed it. Thanks for the info.

Collectives™ on Stack Overflow

implementing binary search tree insertion in Haskell

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related