Expression evaluation in assignment of Functional Programing Principles In Scala

Question

I'm taking the title's coursera course by Martin Odersky. However, I'm having a hard time understanding a solution of week 2's assignment.

My problem is with the .map() function in the following snippet:

type FunSet = Int => Boolean


/**
 * Returns the set of the one given element.
 */
def singletonSet(elem: Int): FunSet =
  x => 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: FunSet, t: FunSet): FunSet = (e: Int) => s(e) || t(e)

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

/**
 * Returns whether all bounded integers within `s` satisfy `p`.
 */
def forall(s: FunSet, p: Int => Boolean): Boolean =
  def iter(a: Int): Boolean =
    if a > bound then true
    else if s(a) && !p(a) then false
    else
      iter(a + 1)
  iter(-bound)
 
/**
 * Returns a set transformed by applying `f` to each element of `s`.
 */
def map(s: FunSet, f: Int => Int): FunSet =
  x => !forall(s, y => f(y) != x)

/**
 * Displays the contents of a set
 */
def toString(s: FunSet): String =
  val xs = for i <- (-bound to bound) if contains(s, i) yield i
  xs.mkString("{", ",", "}")

A unit test demonstrating expected behaviour

test("map f(x) = x-1") {
  val s1 = singletonSet(1)
  val s3 = singletonSet(3)
  val s4 = singletonSet(4)
  val s5 = singletonSet(5)
  val s7 = singletonSet(7)
  val s1000 = singletonSet(1000)
  val input = union(union(union(union(union(s1, s3), s4), s5), s7), s1000)

  val result = map(input, x => x - 1)

  assertEquals(FunSets.toString(result), "{0,2,4,5,6,999}")
}

Question: How is the above .map() function returning a transformed FunSet? I understand that we are returning a FunSet because x: Int => Bollean expression fits the definition (type FunSet = Int => Boolean). But, I'm having a hard time grasping how is the body's expression (!forall(s, y => f(y) != x)) actually "transforming" the set.

Please can anybody explain me what is happening?

Answer 1

There is nothing particularly FP-specific here, it's more about basic notions of set theory.

Here, when calling map(s, f), you want to obtain the image of subset s under function f, which is defined as the set

{f(y): y ? s},

or, equivalently,

{x: ?y ? s. f(y) = x}.

Since you have no exists, but only forall here, there is additionally an application of De Morgan's law, giving you

{x: ¬(?y ? s. f(y) ? x) },

which translates directly into the code

x => !forall(s, y => f(y) != x)

---

An aside: I don't know what the course expects of you, but I'd find it highly instructive to extend the exercise to 2D, and take a 2000x2000 pixel image instead of a linear 2000 pixel line, and then play around with some 2D constructive solid geometry on it, that's usually quite fun. The main reason why it's fun is that unions / intersections are trivial: you can trivially glue together or intersect arbitrary shapes (which would be a major pain in all body parts if you tried to do it with polygons or triangle meshes or anything similar). (alright, I should stop before I convince myself to go and buy a 3D-printer)