Navigation Menu

Skip to content

Instantly share code, notes, and snippets.

@counter2015
Created August 3, 2019 14:35
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save counter2015/986be53b64d6e6e1aa723651da27d91e to your computer and use it in GitHub Desktop.
Save counter2015/986be53b64d6e6e1aa723651da27d91e to your computer and use it in GitHub Desktop.
Functional Programming Principles in Scala Week2 Code
package funsets
/**
* 2. Purely Functional Sets.
*/
object FunSets {
/**
* We represent a set by its characteristic function, i.e.
* its `contains` predicate.
*/
type Set = Int => Boolean
/**
* Indicates whether a set contains a given element.
*/
def contains(s: Set, elem: Int): Boolean = s(elem)
/**
* Returns the set of the one given element.
*/
def singletonSet(elem: Int): Set = (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: Set, t: Set): Set = (x:Int) => contains(s, x) || contains(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: Set, t: Set): Set = (x:Int) => contains(s, x) && contains(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: Set, t: Set): Set = (x:Int) => contains(s, x) && !contains(t, x)
/**
* Returns the subset of `s` for which `p` holds.
*/
def filter(s: Set, p: Int => Boolean): Set = (x:Int) => contains(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: Set, p: Int => Boolean): Boolean = {
def iter(a: Int): Boolean = {
if (contains(s,a) && !p(a)) false
else if (a>bound) true
else iter(a+1)
}
iter(-bound)
}
/**
* Returns whether there exists a bounded integer within `s`
* that satisfies `p`.
*/
def exists(s: Set, p: Int => Boolean): Boolean = !forall(s, (x:Int) => !p(x))
/**
* Returns a set transformed by applying `f` to each element of `s`.
*/
def map(s: Set, f: Int => Int): Set = (x:Int) => exists(s, (y: Int) => x == f(y))
/**
* Displays the contents of a set
*/
def toString(s: Set): 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: Set) {
println(toString(s))
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment