-- setcc.hs
-- Sets as a constructor class

-- this gives an abbreviated version of the Set interface
class SetC f where
  emptyset :: f a
  setinsert :: Ord a => a -> f a -> f a
  setmember :: Ord a => a -> f a -> Bool

data Set a = MkSet [a]
  deriving (Show)

instance SetC Set where
  emptyset = MkSet []

  setinsert x (MkSet xs) = MkSet(insert1 x xs)
     where insert1 x [] = [x]
           insert1 x (s @ (y:ys)) = 
             case compare x y of
               LT -> x : s
               EQ -> s
               GT -> y : insert1 x ys

  setmember x (MkSet(y:ys)) =
    case compare x y of
      LT -> False
      EQ -> True
      GT -> setmember x (MkSet ys)
  setmember x (MkSet []) = False