Csc 4330/6330, Programming Language Concepts (Spring 2018)

Homework 4c (Due: 25 March (Sunday))

Sets

In this programming assignment, you will implement sets and some associated operations in Scala. We will consider only sets of integers. We will use an unusual internal representation of sets:

type Set = Int => Boolean

i.e. A set is a function that maps integers to booleans. In particular, it will map an element in the set to "true" and an element not in the set to "false". You will implement the following functions:

// returns true if elem is in s, false otherwise
def contains(s: Set, elem: Int): Boolean =

// returns a set consisting of a single element, elem
def singletonSet(elem: Int): Set =

// returns an empty set
def emptySet: Set = 

// inserts element x into set s
def add(s: Set, x: Int): Set =

// returns the union of s and t
def union(s: Set, t: Set): Set =

// returns the intersection of s and t
def intersect(s: Set, t: Set): Set =

// returns the difference of s and t, s-t
def difference(s: Set, t: Set): Set =

// returns true is s is a subset of t, false otherwise
def subset(s: Set, t: Set): Boolean =

// returns true is s is equal to t, false otherwise
def equal(s: Set, t: Set): Boolean =

// returns the number of elements in s
def size(s: Set): Int =

// returns a subset of s of elements of s that satisfy the predicate p
def filter(s: Set, p: Int => Boolean): Set =

// returns true if all elements of s satisfy predicate p
def forall(s: Set, p: Int => Boolean): Boolean =

// returns true if at least one element of s satisfies predicate p
def exists(s: Set, p: Int => Boolean): Boolean =

// returns a new set obtained by applying f to each element of s
// and forming a set of the results
// e.g. if s = {1, 2, 3} and f = (x=>x*x) the map(s,f) = {1, 4, 9}
def map(s: Set, f: Int => Int): Set =

For some of these set operations (such as forall, exists, subset, equal, and map), you will need to assume a bounded universal set (-bound to +bound), where

val bound = 1000

Please use the following two files:

Sets.scala
Driver.scala

You need to complete the function definitions in Sets.scala.