class Set set a where
	empty   :: set a
	hasElem :: set a -> a -> set a
	addElem :: set a -> a -> set a
	
data Ord a => Tree a b =
	    Leaf a b
	|   Branch (Tree a b) a (Tree a b)

lookupKey :: Ord a => Tree a b -> a -> (a,b)
lookupKey (Leaf a b) key = (a,b)
lookupKey (Branch l a r) key 
		| key < a   = lookupKey l key
		| otherwise = lookupKey r key

addKey :: Ord a => Tree a b -> (a,b) -> Tree a b
addKey n@(Leaf a' _) (a,b)
	| a <  a'   = (Branch (Leaf a b) a' n)
	| a == a'   = Leaf a b
	| otherwise = (Branch n a (Leaf a b))
addKey (Branch l a' r) e@(a,b)
	| a <  a'   = Branch (addKey l e) a' r
	| otherwise = Branch l a' (addKey r e)

newtype Ord a => TreeSet a = MkTreeSet (Maybe (Tree a ()))

instance (Ord a) => Set TreeSet a where
	empty = MkTreeSet Nothing
	hasElem (MkTreeSet Nothing)  elt = False
	hasElem (MkTreeSet (Just t)) elt = elt == a
		where (a,_) = lookupKey t elt
	addElem (MkTreeSet Nothing)  elt = MkTreeSet $ Just (Leaf elt ())
	addElem (MkTreeSet (Just t)) elt = MkTreeSet $ Just (addKey t (elt,()))