In Part 1 we saw how to define basic operation like union, intersection etc on Set in terms of its indicator function.

In this section we will see Universal quantification, Existential quantification , map and reduce operations.

**Universal Quantification**

p holds for all the values in Set s. Here there is a notion of value (till this function we were operating in an abstract space). The function abstraction Int => Boolean indicates whether an element is present in a set or not, so inorder to find the values of Set s we will have to iterate from -infinity to +infinity and apply p to each value, which is not at all possible and hence we are limiting our bound to a finite range from -1000 to +1000

/** * 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(e: Int): Boolean = { if (e > bound) true else if (contains(s,e) && !p(e)) false else iter(e + 1) } iter(-bound) }

p holds for all values in s if !p holds for at-least one value in s,

proof by contradiction

**Existential Quantification**

at-least one value in s satisfies p

/** * Returns whether there exists a bounded integer within `s` * that satisfies `p`. */ def exists(s: Set, p: Int => Boolean): Boolean = !forall(s, e => !p(e))

there exists a bounded integer within s that satisfies p if !p doesn’t satisfy for all values in s,

proof by contradiction.

**map**

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

let s1 = [1,2,3] we want to square it and get s2 = [1, 4, 9].

indicator function for s1 = x => x == 1 || x == 2 || x == 3 and

for s2 = x => x == 1 || x == 4 || x == 9

so the function f = x => x * x, applying f on all values in s1 results in s2

there for s2 = x => x == f(1) || x == f(2) || x == f(3)

**reduce**

In addition to these functions, I have added the reduce function on set

def reduce(s: Set, f: (Int, Int) => Int ): Option[Int] = { @tailrec def loop(s: Set, acc: Int, e: Int): Int = { if(e > bound) { acc } else if(s(e)) { loop(s, f(acc, e), e + 1) } else { loop(s, acc, e + 1) } } @tailrec def getFirst(s: Set, e: Int): Option[Int] = { if(e > bound) { None } else if(s(e)) { Some(e) } else { getFirst(s, e + 1) } } val firstElem = getFirst(s, -bound) if(firstElem.isEmpty) { None } else { Some(loop(s, firstElem.get, firstElem.get + 1)) } }