TreeMagic.hs

class Comparable a where
  compareTo :: a -> a -> Int

intCompare :: Int -> Int -> Int
intCompare x y 
  | x < y  = -1
  | x > y  =  1
  | x == y =  0
  
instance Comparable Int where 
  compareTo x y  =  intCompare x y

data Tree a = Tip | Node (Tree a) a (Tree a)
  deriving Show

insert :: (Comparable a) => Tree a -> a -> Tree a
insert t e = 
  case t of
    Node l c r -> 
       case compareTo c e of
         -1 -> Node (insert l e) c r
         1 -> Node l c (insert r e)
         0 -> Node l e r
    Tip -> Node Tip e Tip             

main :: IO ()
main = do
      let tmp = Node Tip (3::Int) Tip
          tmp2 = insert tmp 4
      print tmp2