gistfile1.hs

data BSTree a = Empty | Node (BSTree a) a (BSTree a) 
                       deriving (Show, Eq)

insert :: (Ord a) => a -> BSTree a -> BSTree a
insert x Empty = Node Empty x Empty
insert x (Node l v r)
  | x < v = Node (insert x l) v r
  | v < x = Node l v (insert x r)
  | otherwise = (Node l x r)

--newtype Set a = BSTree a
type Map k v = BSTree (Key k, Val v)
newtype Key k = Key k deriving (Show, Eq)
newtype Val v = Val v deriving (Show)

instance (Ord k) => Ord (Key k) where   
  (Key k) `compare` (Key k') = compare k k'
instance Eq (Val v) where 
  _ == _ = True
instance Ord (Val v) where 
  _ `compare` _ = EQ

emptyM = Empty

bindM :: (Ord k, Ord v) => Key k -> Val v -> Map k v -> Map k v
bindM k v m = insert (k, v) m

lookupM :: (Ord k) => Key k -> Map k v -> Either String (Val v)
lookupM k m = undefined