blob: 01c854b1da25d9459ca267931532be448275510e (
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
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
powerSet` :: (Set a) -> [Int]
powerSet` s = [0 .. 2^(nrOfElements s) - 1]
takeMod :: (Set a) Int -> Set a
takeMod s m = [e \\ e <- s & k <- [0..] | k rem m == 0]
|
