Advertisement
jules0707

FunSets

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