summaryrefslogtreecommitdiff
path: root/fp1/week4/mart/StdSet.icl
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))])