implementation module StdSet

import StdEnv
import StdClass

::	Set a :== [a]

toSet			:: [a]             -> Set a | Eq a
toSet l = toSet` l []
where 
    toSet` [] s = s
    toSet` [x:xs] s = toSet` xs (join x s)
    where
        join :: a (Set a) -> Set a | Eq a
        join e s
            | memberOfSet e s = s
            | otherwise = s ++ [e]

fromSet			:: (Set a)         -> [a]
fromSet s = s

isEmptySet		:: (Set a)         -> Bool
isEmptySet [] = True
isEmptySet _ = False

isDisjoint		:: (Set a) (Set a) -> Bool  | Eq a
isDisjoint s1 s2 = length (intersection s1 s2) == 0

isSubset		:: (Set a) (Set a) -> Bool  | Eq a
isSubset s1 s2 = nrOfElements (intersection s1 s2) == nrOfElements s1

isStrictSubset	:: (Set a) (Set a) -> Bool  | Eq a
isStrictSubset s1 s2 = isSubset s1 s2 && s1 <> s2

memberOfSet		:: a       (Set a) -> Bool  | Eq a
memberOfSet e [] = False
memberOfSet e [x:xs] 
    | e == x = True
    | otherwise = memberOfSet e xs

union           :: (Set a) (Set a) -> Set a | Eq a
union s1 s2 = toSet (s1 ++ s2)

intersection	:: (Set a) (Set a) -> Set a | Eq a
intersection s1 s2 = [e \\ e <- s1 | memberOfSet e s2]

nrOfElements	:: (Set a) -> Int
nrOfElements s = length (fromSet s)

without			:: (Set a) (Set a) -> Set a | Eq a
without s1 s2 = [e \\ e <- s1 | (memberOfSet e s2) == False]

product			:: (Set a) (Set b) -> Set (a,b)
product s1 s2 = [(e1,e2) \\ e1 <- s1, e2 <- s2]

instance zero (Set a)
where zero = []

instance ==   (Set a) | Eq a 
where (==) s1 s2 = isSubset s1 s2 && isSubset s2 s1

powerSet		:: (Set a)         -> Set (Set a)
powerSet [] = [zero]
powerSet [e:es] = map ((++) [e]) (powerSet es) ++ powerSet es