• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled a guest Mar 18th, 2019 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. package funsets
2.
3.
4. /**
5.   * 2. Purely Functional Sets.
6.   */
7. object FunSets {
8.   /**
9.     * We represent a set by its characteristic function, i.e.
10.     * its `contains` predicate.
11.     */
12.   type Set = Int => Boolean
13.
14.   /**
15.     * Indicates whether a set contains a given element.
16.     */
17.   def contains(s: Set, elem: Int): Boolean = s(elem)
18.
19.   /**
20.     * Returns the set of the one given element.
21.     */
22.   def singletonSet(elem: Int): Set = x => x == elem
23.
24.
25.   /**
26.     * Returns the union of the two given sets,
27.     * the sets of all elements that are in either `s` or `t`.
28.     */
29.   def union(s: Set, t: Set): Set = x => contains(s, x) || contains(t, x)
30.
31.   /**
32.     * Returns the intersection of the two given sets,
33.     * the set of all elements that are both in `s` and `t`.
34.     */
35.   def intersect(s: Set, t: Set): Set = x => contains(s, x) && contains(t, x)
36.
37.   /**
38.     * Returns the difference of the two given sets,
39.     * the set of all elements of `s` that are not in `t`.
40.     */
41.   def diff(s: Set, t: Set): Set = x => contains(s, x) && !contains(t, x)
42.
43.   /**
44.     * Returns the subset of `s` for which `p` holds.
45.     */
46.   def filter(s: Set, p: Int => Boolean): Set = x => contains(s, x) && p(x)
47.
48.
49.   /**
50.     * The bounds for `forall` and `exists` are +/- 1000.
51.     */
52.   val bound = 1000
53.
54.   /**
55.     * Returns whether all bounded integers within `s` satisfy `p`.
56.     */
57.   def forall(s: Set, p: Int => Boolean): Boolean = {
58.     def iter(a: Int): Boolean = {
59.       if (a > bound) true
60.       else if (contains(s, a)) p(a) && iter(a + 1)
61.       else iter(a + 1)
62.     }
63.
64.     iter(-bound)
65.   }
66.
67.   /**
68.     * Returns whether there exists a bounded integer within `s`
69.     * that satisfies `p`.
70.     */
71.   def exists(s: Set, p: Int => Boolean): Boolean = !forall(s, x => !p(x))
72.
73.   /**
74.     * Returns a set transformed by applying `f` to each element of `s`.
75.     */
76.   def map(s: Set, f: Int => Int): Set = y => exists(s, x => f(x) == y)
77.
78.   /**
79.     * Displays the contents of a set
80.     */
81.   def toString(s: Set): String = {
82.     val xs = for (i <- -bound to bound if contains(s, i)) yield i
83.     xs.mkString("{", ",", "}")
84.   }
85.
86.   /**
87.     * Prints the contents of a set on the console.
88.     */
89.   def printSet(s: Set) {
90.     println(toString(s))
91.   }
92. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top