Assignment 2 in "Functional Programming Principles in Scala" from Coursera

Functional Sets: Instructions

Representation

We will work with sets of integers.

As an example to motivate our representation, how would you represent the set of all negative integers? You cannot list them all… one way would be so say: if you give me an integer, I can tell you whether it’s in the set or not: for 3, I say ‘no’; for -1, I say yes.

Mathematically, we call the function which takes an integer as argument and which returns a boolean indicating whether the given integer belongs to a set, the characteristic function of the set. For example, we can characterize the set of negative integers by the characteristic function (x: Int) => x < 0.

Therefore, we choose to represent a set by its characterisitc function and define a type alias for this representation:

type Set = Int => Boolean

Using this representation, we define a function that tests for the presence of a value in a set:

def contains(s: Set, elem: Int): Boolean = s(elem)

2.1 Basic Functions on Sets

Let’s start by implementing basic functions on sets.

1. Define a function which creates a singleton set from one integer value: the set represents the set of the one given element. Its signature is as follows:

   def singletonSet(elem: Int): Set

   Now that we have a way to create singleton sets, we want to define a function that allow us to build bigger sets from smaller ones.

2. Define the functions union, intersect, and diff, which takes two sets, and return, respectively, their union, intersection and differences. diff(s, t) returns a set which contains all the elements of the set s that are not in the set t. These functions have the following signatures:

   def union(s: Set, t: Set): Set
   def intersect(s: Set, t: Set): Set
   def diff(s: Set, t: Set): Set

3. Define the function filter which selects only the elements of a set that are accepted by a given predicate p. The filtered elements are returned as a new set. The signature of filter is as follows:

   def filter(s: Set, p: Int => Boolean): Set

2.2 Queries and Transformations on Sets

In this part, we are interested in functions used to make requests on elements of a set. The first function tests whether a given predicate is true for all elements of the set. This forall function has the following signature:

def forall(s: Set, p: Int => Boolean): Boolean

Note that there is no direct way to find which elements are in a set. contains only allows to know whether a given element is included. Thus, if we wish to do something to all elements of a set, then we have to iterate over all integers, testing each time whether it is included in the set, and if so, to do something with it. Here, we consider that an integer x has the property -1000 <= x <= 1000 in order to limit the search space.

1. Implement forall using linear recursion. For this, use a helper function nested in forall. Its structure is as follows (replace the ???):

   def forall(s: Set, p: Int => Boolean): Boolean = {
    def iter(a: Int): Boolean = {
      if (???) ???
      else if (???) ???
      else iter(???)
    }
    iter(???)

   }

2. Using forall, implement a function exists which tests whether a set contains at least one element for which the given predicate is true. Note that the functions forall and exists behave like the universal and existential quantifiers of first-order logic.

   def exists(s: Set, p: Int => Boolean): Boolean

3. Finally, write a function map which transforms a given set into another one by applying to each of its elements the given function. map has the following signature:

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

Extra Hints

• Be attentive in the video lectures on how to write anonymous functions in Scala.
• Sets are represented as functions. Think about what it means for an element to belong to a set, in terms of function evaluation. For example, how do you represent a set that contains all numbers between 1 and 100?
• Most of the solutions for this assignment can be written as one-liners. If you have more, you probably need to rethink your solution. In other words, this assignment needs more thinking (whiteboard, pen and paper) than coding ;-).
• If you are having some trouble with terminology, have a look at the glossary.

object FunSets {

  type Set = Int => Boolean

  def contains(s: Set, elem: Int): Boolean = s(elem)
  def singletonSet(elem: Int): Set={

  	(x : Int) => x==elem

  } 
  def union(s: Set, t: Set): Set = {

  	(x:Int )  => s(x)||t(x)

  } 
  def intersect(s: Set, t: Set): Set = {

  	(x:Int) => s(x)&&t(x)

  }
  def diff(s: Set, t: Set): Set = {

  	(x:Int) => s(x)&& !t(x)

  } 
  def filter(s: Set, p: Int => Boolean): Set ={

	  (x:Int) => s(x)&& p(x)

  } 
  /**

   * The bounds for `forall` and `exists` are +/- 1000.

   */

  val bound = 1000

  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)

  }  
  def exists(s: Set, p: Int => Boolean): Boolean = {

  	 !(forall ( s, (x:Int)=> !p(x)))

  }
  def map(s: Set, f: Int => Int): Set = {

 	 (x:Int) => exists(s, (a:Int)=> f(a) == x)

  } 
  def toString(s: Set): String = {

    val xs = for (i <- -bound to bound if contains(s, i)) yield i

    xs.mkString("{", ",", "}")

  }
  def printSet(s: Set) {

    println(toString(s))

  }

}