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

-- Implementing sets by an ordered list of elements:
data Set a = Set [a]
 deriving Show

empty :: Set a
empty = Set []

insert :: Ord a => a -> Set a -> Set a
insert x (Set xs) = Set (oinsert xs)
 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 xs) = oelem xs
 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 xs1) (Set xs2) = Set (ounion xs1 xs2)
 where ounion []       ys     = ys
       ounion xs@(_:_) []     = xs
       ounion (x:xs)   (y:ys) | x == y    = x : ounion xs ys
                              | x < y     = x : ounion xs (y:ys)
                              | otherwise = y : ounion (x:xs) ys
-- > linear complexity!!