-- An implementation of sets by ordered lists:

module SetsAsOrdLists(Set, empty, insert, isElem, union) where

data Set a = Set [a]
  deriving Show

empty :: Set a
empty = Set []

insert :: Ord a => a -> Set a -> Set a
insert x (Set s) = Set (oinsert s)
 where
   oinsert [] = [x]
   oinsert (y:ys) | x==y = y:ys
                  | x<y  = x:y:ys
                  | otherwise = y : oinsert ys
                  
isElem :: Ord a => a -> Set a -> Bool
isElem x (Set s) = oelem s
 where
   oelem [] = False
   oelem (y:ys) | x==y = True
                | x<y  = False
                | otherwise = oelem ys

union :: Ord a => Set a -> Set a -> Set a
union (Set xs) (Set ys) = Set (ounion xs ys)
 where
  ounion []     ys = ys
  ounion (x:xs) [] = x:xs
  ounion (x:xs) (y:ys) | x==y = x : ounion xs ys
                       | x<y  = x : ounion xs (y:ys)
                       | x>y  = y : ounion (x:xs) ys