module SetEq (Set(..),emptySet,isEmpty,inSet,subSet,insertSet,
deleteSet,powerSet,takeSet,list2set,(!!!))
where
import Data.List (delete)
{-- Sets implemented as unordered lists without duplicates --}
newtype Set a = Set [a]
instance Eq a => Eq (Set a) where
set1 == set2 = subSet set1 set2 && subSet set2 set1
instance (Show a) => Show (Set a) where
showsPrec _ (Set s) str = showSet s str
showSet [] str = showString "{}" str
showSet (x:xs) str = showChar '{' (shows x (showl xs str))
where showl [] str = showChar '}' str
showl (x:xs) str = showChar ',' (shows x (showl xs str))
emptySet :: Set a
emptySet = Set []
isEmpty :: Set a -> Bool
isEmpty (Set []) = True
isEmpty _ = False
inSet :: (Eq a) => a -> Set a -> Bool
inSet x (Set s) = elem x s
subSet :: (Eq a) => Set a -> Set a -> Bool
subSet (Set []) _ = True
subSet (Set (x:xs)) set = (inSet x set) && subSet (Set xs) set
insertSet :: (Eq a) => a -> Set a -> Set a
insertSet x (Set ys) | inSet x (Set ys) = Set ys
| otherwise = Set (x:ys)
deleteSet :: Eq a => a -> Set a -> Set a
deleteSet x (Set xs) = Set (delete x xs)
list2set :: Eq a => [a] -> Set a
list2set [] = Set []
list2set (x:xs) = insertSet x (list2set xs)
powerSet :: Eq a => Set a -> Set (Set a)
powerSet (Set xs) = Set (map (\xs -> (Set xs)) (powerList xs))
powerList :: [a] -> [[a]]
powerList [] = [[]]
powerList (x:xs) = (powerList xs) ++ (map (x:) (powerList xs))
takeSet :: Eq a => Int -> Set a -> Set a
takeSet n (Set xs) = Set (take n xs)
infixl 9 !!!
(!!!) :: Eq a => Set a -> Int -> a
(Set xs) !!! n = xs !! n