implementation module StdSet

import StdEnv
import StdClass

::	Set a = Set [a]

toSet	:: [a]             -> Set a | Eq a
toSet s = Set (removeDup s)

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

isEmptySet	:: (Set a)         -> Bool
isEmptySet s = isEmpty (fromSet s)

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

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

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

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

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

intersection	:: (Set a) (Set a) -> Set a | Eq a
intersection (Set s1) s2 = Set [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 (Set s1) s2 = Set [e \\ e <- s1 | not (memberOfSet e s2)]

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

instance zero (Set a)
where zero = Set []

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

powerSet	:: (Set a)         -> Set (Set a) | Eq a
powerSet (Set []) = Set [(Set [])]
powerSet (Set [e:xs]) = union (powerSet (Set xs))
	(Set [union (Set [e]) x \\ x <- fromSet (powerSet (Set xs))])