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

import Test.QuickCheck
    
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)
                       | otherwise = y : ounion (x:xs) ys


instance (Ord a, Arbitrary a) => Arbitrary (Set a) where
  arbitrary = do xs <- arbitrary
                 return ((foldr :: (a->b->b) -> b -> [a] -> b) insert empty xs)