blob: ecb2e60d18dd0ef725d1acda30a2feb311409088 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
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))])
|
