Coursera FP Assignment 2

Assigment 2

Seans's solutions

;; https://class.coursera.org/progfun-003/assignment/view?assignment_id=3
;; A note on terminology - in order to avoid all sorts of dumb confusion with
;; the built in set function, I'm going to use 'cset' to refer to
;; 'characteristic sets' used in this assignment.
(ns scala-class.two)


;; 2.0 Representation
(defn cset-contains [cset elem]
  (cset elem))

;; 2.1 Basic Functions on Sets
(defn cset-singleton [elem]
  #(= elem %))

(defn cset-union [cset-s cset-t]
  #(or (cset-s %) (cset-t %)))

(defn cset-intersect [cset-s cset-t]
  #(and (cset-s %) (cset-t %)))

(defn cset-diff [cset-s cset-t]
  #(and (cset-s %) (not (cset-t %))))

(def cset-filter cset-intersect)

;; 2.2 Queries and Transformations on Sets
(defn cset-forall [cset pred]
  (loop [x -1000]
    (cond ((cset-diff cset pred) x) false
          (> x 1000) true
          :else (recur (+ x 1)))))

(defn cset-exists [cset pred]
  (not (cset-forall cset #(not (pred %)))))

(defn cset-map [cset fun]
  (fn [elem] (cset-exists cset #(= elem (fun %)))))

;; Bonus - https://class.coursera.org/progfun-003/forum/thread?thread_id=554
(defn csubset? [cset-s cset-t]
  (cset-forall cset-s cset-t))

(defn cset-equal? [cset-s cset-t]
  (and (cset-forall cset-s cset-t) (cset-forall cset-t cset-s)))

(defn cset-cartesian [cset-s cset-t]
  #(and (cset-s %1) (cset-t %2)))

Nick's solutions

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 = (value: Int) => elem == value

  /**
   * 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 = (value: Int) => contains(s, value) || contains(t, value)

  /**
   * 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 = (value: Int) => contains(s, value) && contains(t, value)

  /**
   * 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 = (value: Int) => contains(s, value) && !contains(t, value)

  /**
   * Returns the subset of `s` for which `p` holds.
   */
  def filter(s: Set, p: Int => Boolean): Set = (value: Int) => contains(s, value) && p(value)

  /**
   * 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 (a > bound) true
      else if (contains(s, a) && !p(a)) false
      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, (value: Int) => !p(value))

  /**
   * Returns a set transformed by applying `f` to each element of `s`.
   */
  def map(s: Set, f: Int => Int): Set = (value: Int) => exists(s, (boundedVal: Int) => f(boundedVal) == value)

  /**
   * 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))
  }
}