daily pastebin goal
40%
SHARE
TWEET

Untitled

a guest Mar 18th, 2019 55 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. OK, I Understand
 
Top