-
Notifications
You must be signed in to change notification settings - Fork 0
/
FunSets.scala
92 lines (76 loc) · 2.23 KB
/
FunSets.scala
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
package funsets
/**
* 2. Purely Functional Sets.
*/
trait FunSets extends FunSetsInterface {
/**
* We represent a set by its characteristic function, i.e.
* its `contains` predicate.
*/
override type FunSet = Int => Boolean
/**
* Indicates whether a set contains a given element.
*/
def contains(s: FunSet, elem: Int): Boolean = s(elem)
/**
* Returns the set of the one given element.
*/
def singletonSet(elem: Int): FunSet = (x: Int) => x == elem
/**
* Returns the union of the two given sets,
* the sets of all elements that are in either `s` or `t`.
*/
def union(s: FunSet, t: FunSet): FunSet = (x: Int) => s(x) || t(x)
/**
* Returns the intersection of the two given sets,
* the set of all elements that are both in `s` and `t`.
*/
def intersect(s: FunSet, t: FunSet): FunSet = (x: Int) => s(x) && t(x)
/**
* Returns the difference of the two given sets,
* the set of all elements of `s` that are not in `t`.
*/
def diff(s: FunSet, t: FunSet): FunSet = (x: Int) => s(x) && !t(x)
/**
* Returns the subset of `s` for which `p` holds.
*/
def filter(s: FunSet, p: Int => Boolean): FunSet = (x: Int) => s(x) && p(x)
/**
* The bounds for `forall` and `exists` are +/- 1000.
*/
val bound = 1000
/**
* Returns whether all bounded integers within `s` satisfy `p`.
*/
def forall(s: FunSet, p: Int => Boolean): Boolean = {
def iter(a: Int): Boolean = {
if (a > bound) true
else if (contains(s, a)) p(a) && iter(a + 1)
else iter(a + 1)
}
iter(-1000)
}
/**
* Returns whether there exists a bounded integer within `s`
* that satisfies `p`.
*/
def exists(s: FunSet, p: Int => Boolean): Boolean = !forall(s, x => !p(x))
/**
* Returns a set transformed by applying `f` to each element of `s`.
*/
def map(s: FunSet, f: Int => Int): FunSet = (y: Int) => exists(s, x => f(x) == y)
/**
* Displays the contents of a set
*/
def toString(s: FunSet): String = {
val xs = for (i <- -bound to bound if contains(s, i)) yield i
xs.mkString("{", ",", "}")
}
/**
* Prints the contents of a set on the console.
*/
def printSet(s: FunSet): Unit = {
println(toString(s))
}
}
object FunSets extends FunSets