scala coursera course week 2

gistfile1.scala

package funsets

import common._

/**
 * 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 = 
    return (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 = 
    return (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 = 
    return (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 = 
  	return (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 = 
    return (x: Int) => 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 (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, x => !p(x))

  /**
   * Returns a set transformed by applying `f` to each element of `s`.
   */
  def map(s: Set, f: Int => Int): Set = {
    def iterate(s:Set, accumulateSet: Set, a:Int): Set = {
      if (a > bound) accumulateSet
      else if (contains(s, a)) iterate(s, union(accumulateSet, x=>f(a) == x), a+1)
      else iterate(s, accumulateSet, a+1)
    }
    iterate(s, x=>false, -3)
  }

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

Thank you for your huge hint!

but, there is little wrong in your filter function.

sometimes, (actually, in some tests) filter function get the x that doesn't exist in Set s.
def filter(s: Set, p: Int => Boolean): Set = (x: Int) => contains(s, x) && p(x)

is working well.

Thank you too! Although in map function you don't have to put "s" set in inner function, it's visible there anyway!

There is a way to implement map with just one line!

There is a way to implement map with just one line!

can you share that line? :-) @mattlevan

def map(s: Set, f: Int => Int): Set = (i: Int) => exists(s, (j: Int) => i == f(j))

Why -3 in the map?

I think the correct value is -bound instead of -3 @valtih1978

How about:
def map(s: Set, f: Int => Int): Set = (x: Int) => contains(map(s, f), f(x))

def map(s: Set, f: Int => Int): Set = (x: Int) => contains(map(s, f), f(x))

This failed my tests ...

is that an infinite loop? 🤔

def map(s: FunSet, f: Int => Int): FunSet = y => exists(s, x => y == f(x))
translates to when you get a y, check if there is a value x in my set, for which f(x)== y

there is a bug in this code
filter should be defined as :
def filter(s: FunSet, p: Int => Boolean): FunSet = (a: Int) => if (contains(s,a)) p(a) else false

otherwise it returns all elements within the bounds. the contains check is necessary, we cannot just blindly apply p(a)