shinyhappy

Coursera FP in Scala Course Assignments Code

Assignment 1

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

Assignment 3

Sean's Solutions

(ns scala-class.three
  (:import java.util.NoSuchElementException))

(defrecord Tweet [user text retweets])

(defn gt [tweet-a tweet-b] (> (compare (:text tweet-a) (:text tweet-b)) 0))
(defn lt [tweet-a tweet-b] (< (compare (:text tweet-a) (:text tweet-b)) 0))
(defn eq [tweet-a tweet-b] (= (compare (:text tweet-a) (:text tweet-b)) 0))

(defprotocol Tree
  (contains [this target])
  (incl [this new-tweet])
  (_filter [this acc pred])
  (tfilter [this pred])
  (union [this that])
  (tremove [this target])
  (_most-retweeted [this acc])
  (most-retweeted [this])
  (descending-by-retweet [this]))

(defrecord TweetTree [tweet left right]
  Tree
  (contains [this target]
    (cond (gt tweet target) (contains left target)
          (lt tweet target) (contains right target)
          :else true))
  (incl [this new-tweet]
    (cond (gt tweet new-tweet) (->TweetTree tweet (incl left new-tweet) right)
          (lt tweet new-tweet) (->TweetTree tweet left (incl right new-tweet))
          :else this))
  (_filter [this acc pred]
    (let [sub-filtered (_filter right (_filter left acc pred) pred)]
      (if (pred tweet) (incl sub-filtered tweet) sub-filtered)))
  (tfilter [this pred]
    (_filter this nil pred))
  (union [this that]
    (->TweetTree tweet
                 (_filter that left #(lt % tweet))
                 (_filter that right #(gt % tweet))))
  (tremove [this target]
    (cond (gt tweet target) (->TweetTree tweet (tremove left target) right)
          (lt tweet target) (->TweetTree tweet left (tremove right target))
          :else (union left right)))
  (_most-retweeted [this acc]
    (let [best (if (> (:retweets tweet) (:retweets acc)) tweet acc)]
      (_most-retweeted left (_most-retweeted right best))))
  (most-retweeted [this]
    (_most-retweeted this tweet))
  (descending-by-retweet [this]
    (let [most (most-retweeted this)]
      (cons most (descending-by-retweet (tremove this most))))))

(extend-protocol Tree
  nil
  (contains [this target] false)
  (incl [this new-tweet] (->TweetTree new-tweet nil nil))
  (_filter [this acc pred] acc)
  (tfilter [this pred] nil)
  (union [this that] that)
  (tremove [this target] nil)
  (_most-retweeted [this acc] acc)
  (most-retweeted [this] (throw (NoSuchElementException.)))
  (descending-by-retweet [this] (list)))

(ns scala-class.three-trending
  (:use scala-class.three)
  (:use expectations)
  (:use [scala-class.three-test :only [twit build-tree]])
  (:use [scala-class.three-data :only [tech-tweets]]))

(defn re-test [regex string]
  (not (nil? (re-find regex string))))

(defn any [pred lst]
  (reduce #(or %1 %2) false (map pred lst)))

(def google-patterns [#"[aA]ndroid" #"[gG]alaxy" #"[nN]exus"])
(def apple-patterns [#"i[Oo][Ss]" #"i[pP]hone" #"i[pP]ad"])

(defn filter-pattern-list [patterns tree]
  (tfilter tree (fn [tweet] (any #(re-test % (:text tweet)) patterns))))

(def google-tweets (filter-pattern-list google-patterns tech-tweets))
(def apple-tweets (filter-pattern-list apple-patterns tech-tweets))

(def trending (descending-by-retweet (union google-tweets apple-tweets)))

Nick's Solutions

package objsets

import common._
import TweetReader._

/**
 * A class to represent tweets.
 */
class Tweet(val user: String, val text: String, val retweets: Int) {
  override def toString: String =
    "User: " + user + "\n" +
    "Text: " + text + " [" + retweets + "]"
}

/**
 * This represents a set of objects of type `Tweet` in the form of a binary search
 * tree. Every branch in the tree has two children (two `TweetSet`s). There is an
 * invariant which always holds: for every branch `b`, all elements in the left
 * subtree are smaller than the tweet at `b`. The elements in the right subtree are
 * larger.
 *
 * Note that the above structure requires us to be able to compare two tweets (we
 * need to be able to say which of two tweets is larger, or if they are equal). In
 * this implementation, the equality / order of tweets is based on the tweet's text
 * (see `def incl`). Hence, a `TweetSet` could not contain two tweets with the same
 * text from different users.
 *
 *
 * The advantage of representing sets as binary search trees is that the elements
 * of the set can be found quickly. If you want to learn more you can take a look
 * at the Wikipedia page [1], but this is not necessary in order to solve this
 * assignment.
 *
 * [1] http://en.wikipedia.org/wiki/Binary_search_tree
 */
abstract class TweetSet {

  /**
   * This method takes a predicate and returns a subset of all the elements
   * in the original set for which the predicate is true.
   *
   * Question: Can we implement this method here, or should it remain abstract
   * and be implemented in the subclasses?
   */
  def filter(p: Tweet => Boolean): TweetSet = filterAcc(p, new Empty)

  /**
   * This is a helper method for `filter` that propagates the accumulated tweets.
   */
  def filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet

  /**
   * Returns a new `TweetSet` that is the union of `TweetSet`s `this` and `that`.
   *
   * Question: Should we implment this method here, or should it remain abstract
   * and be implemented in the subclasses?
   */
   def union(that: TweetSet): TweetSet = filterAcc( (p) => true, that.filter( (p) => true) )

  /**
   * Returns the tweet from this set which has the greatest retweet count.
   *
   * Calling `mostRetweeted` on an empty set should throw an exception of
   * type `java.util.NoSuchElementException`.
   *
   * Question: Should we implement this method here, or should it remain abstract
   * and be implemented in the subclasses?
   */
  def mostRetweeted: Tweet

  /**
   * Returns a list containing all tweets of this set, sorted by retweet count
   * in descending order. In other words, the head of the resulting list should
   * have the highest retweet count.
   *
   * Hint: the method `remove` on TweetSet will be very useful.
   * Question: Should we implement this method here, or should it remain abstract
   * and be implemented in the subclasses?
   */
  def descendingByRetweet: TweetList = {
    if (isEmpty) Nil
    else {
      val maxRetweeted = mostRetweeted
      new Cons(maxRetweeted, remove(maxRetweeted).descendingByRetweet)
    }
  }

  def isEmpty: Boolean

  /**
   * The following methods are already implemented
   */

  /**
   * Returns a new `TweetSet` which contains all elements of this set, and the
   * the new element `tweet` in case it does not already exist in this set.
   *
   * If `this.contains(tweet)`, the current set is returned.
   */
  def incl(tweet: Tweet): TweetSet

  /**
   * Returns a new `TweetSet` which excludes `tweet`.
   */
  def remove(tweet: Tweet): TweetSet

  /**
   * Tests if `tweet` exists in this `TweetSet`.
   */
  def contains(tweet: Tweet): Boolean

  /**
   * This method takes a function and applies it to every element in the set.
   */
  def foreach(f: Tweet => Unit): Unit
}

class Empty extends TweetSet {

  def filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet = acc

  def mostRetweeted: Tweet = throw new java.util.NoSuchElementException
  
  def isEmpty: Boolean = true
  
  /**
   * The following methods are already implemented
   */

  def contains(tweet: Tweet): Boolean = false

  def incl(tweet: Tweet): TweetSet = new NonEmpty(tweet, new Empty, new Empty)

  def remove(tweet: Tweet): TweetSet = this

  def foreach(f: Tweet => Unit): Unit = ()
}

class NonEmpty(elem: Tweet, left: TweetSet, right: TweetSet) extends TweetSet {

  def filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet = {
    if (p(elem)) left.filterAcc(p, right.filterAcc(p, acc.incl(elem)))
    else left.filterAcc(p, right.filterAcc(p, acc))
  }
  
  def mostRetweeted: Tweet = {
    def tweetMax(t1: Tweet, t2: Tweet): Tweet = {
      if (t1.retweets > t2.retweets) t1
      else t2
    }
    if (left.isEmpty && right.isEmpty) elem
    else if (left.isEmpty) tweetMax(right.mostRetweeted, elem)
    else if (right.isEmpty) tweetMax(left.mostRetweeted, elem)
    else tweetMax(left.mostRetweeted, tweetMax(right.mostRetweeted, elem))
  }	

  def isEmpty: Boolean = false
  
  /**
   * The following methods are already implemented
   */

  def contains(x: Tweet): Boolean =
    if (x.text < elem.text) left.contains(x)
    else if (elem.text < x.text) right.contains(x)
    else true

  def incl(x: Tweet): TweetSet = {
    if (x.text < elem.text) new NonEmpty(elem, left.incl(x), right)
    else if (elem.text < x.text) new NonEmpty(elem, left, right.incl(x))
    else this
  }

  def remove(tw: Tweet): TweetSet =
    if (tw.text < elem.text) new NonEmpty(elem, left.remove(tw), right)
    else if (elem.text < tw.text) new NonEmpty(elem, left, right.remove(tw))
    else left.union(right)

  def foreach(f: Tweet => Unit): Unit = {
    f(elem)
    left.foreach(f)
    right.foreach(f)
  }
}

trait TweetList {
  def head: Tweet
  def tail: TweetList
  def isEmpty: Boolean
  def foreach(f: Tweet => Unit): Unit =
    if (!isEmpty) {
      f(head)
      tail.foreach(f)
    }
}

object Nil extends TweetList {
  def head = throw new java.util.NoSuchElementException("head of EmptyList")
  def tail = throw new java.util.NoSuchElementException("tail of EmptyList")
  def isEmpty = true
}

class Cons(val head: Tweet, val tail: TweetList) extends TweetList {
  def isEmpty = false
}


object GoogleVsApple {
  val google = List("android", "Android", "galaxy", "Galaxy", "nexus", "Nexus")
  val apple = List("ios", "iOS", "iphone", "iPhone", "ipad", "iPad")

  lazy val googleTweets: TweetSet = TweetReader.allTweets.filter( tweet => google.exists( keyword => tweet.text.contains(keyword)))
  lazy val appleTweets: TweetSet = TweetReader.allTweets.filter( tweet => apple.exists( keyword => tweet.text.contains(keyword)))

  /**
   * A list of all tweets mentioning a keyword from either apple or google,
   * sorted by the number of retweets.
   */
  lazy val trending: TweetList = googleTweets.union(appleTweets).descendingByRetweet
}

object Main extends App {
  // Print the trending tweets
  GoogleVsApple.trending foreach println
}