From 32021a0347c4f364a3407ced8455dff139b18adb Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= <jeremy@asynk.ch>
Date: Wed, 10 Apr 2013 15:05:28 +0200
Subject: Scala : week2: implement forall, exists, map

---
 Scala/funsets/src/main/scala/funsets/FunSets.scala | 22 ++++----
 .../src/test/scala/funsets/FunSetSuite.scala       | 60 ++++++++++++++++++----
 2 files changed, 62 insertions(+), 20 deletions(-)

diff --git a/Scala/funsets/src/main/scala/funsets/FunSets.scala b/Scala/funsets/src/main/scala/funsets/FunSets.scala
index 15a6bfc..99b0748 100644
--- a/Scala/funsets/src/main/scala/funsets/FunSets.scala
+++ b/Scala/funsets/src/main/scala/funsets/FunSets.scala
@@ -20,25 +20,25 @@ object FunSets {
   /**
    * Returns the set of the one given element.
    */
-  def singletonSet(elem: Int): Set = (x =>  x == elem)
+  def singletonSet(elem: Int): Set = 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: Set, t: Set): Set = (x => s(x) | t(x))
+  def union(s: Set, t: Set): Set = x => s(x) | 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 = (x => s(x) & t(x))
+  def intersect(s: Set, t: Set): Set = x => s(x) & 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 = (x => s(x) & !t(x))
+  def diff(s: Set, t: Set): Set = x => s(x) & !t(x)
 
   /**
    * Returns the subset of `s` for which `p` holds.
@@ -56,23 +56,25 @@ object FunSets {
    */
   def forall(s: Set, p: Int => Boolean): Boolean = {
     def iter(a: Int): Boolean = {
-      if (???) ???
-      else if (???) ???
-      else iter(???)
+      if (a > bound) true
+      else if (contains(s, a) && !p(a)) false
+      else iter(a + 1)
     }
-    iter(???)
+    iter(-bound)
   }
 
   /**
    * Returns whether there exists a bounded integer within `s`
    * that satisfies `p`.
    */
-  def exists(s: Set, p: Int => Boolean): Boolean = ???
+   // elements of s do NOT all NOT satisfy 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 = ???
+  // x is in S' if exists y in S so that f(y) = x
+  def map(s: Set, f: Int => Int): Set = x => exists(s, y => f(y) == x)
 
   /**
    * Displays the contents of a set
diff --git a/Scala/funsets/src/test/scala/funsets/FunSetSuite.scala b/Scala/funsets/src/test/scala/funsets/FunSetSuite.scala
index 7c3fd53..4ca61a5 100644
--- a/Scala/funsets/src/test/scala/funsets/FunSetSuite.scala
+++ b/Scala/funsets/src/test/scala/funsets/FunSetSuite.scala
@@ -77,6 +77,8 @@ class FunSetSuite extends FunSuite {
     val s1 = singletonSet(1)
     val s2 = singletonSet(2)
     val s3 = singletonSet(3)
+    def boundedSet(m: Int, n: Int): Set =  x => x >= m && x <= n
+    val v13 = boundedSet(1,3)
   }
 
   /**
@@ -165,16 +167,54 @@ class FunSetSuite extends FunSuite {
 
   test("filter") {
     new TestSets {
-      val s = filter(s1, (x => x == 1))
-      assert(!contains(s, 0), "Filter none")
-      assert(contains(s, 1), "Filter 1")
-      assert(!contains(s, 2), "Filter none")
-      assert(!contains(s, 3), "Filter none")
-      val v = filter(s1, (x => x == 0))
-      assert(!contains(v, 0), "Filter none")
-      assert(!contains(v, 1), "Filter none")
-      assert(!contains(v, 2), "Filter none")
-      assert(!contains(v, 3), "Filter none")
+      val s = filter(s1, x => x == 1)
+      assert(!contains(s, 0), "Filter not s 0")
+      assert(contains(s, 1), "Filter s 1")
+      assert(!contains(s, 2), "Filter not s 2")
+      assert(!contains(s, 3), "Filter not s3")
+      val v = filter(s1, x => x == 0)
+      assert(!contains(v, 0), "Filter not v 0")
+      assert(!contains(v, 1), "Filter not v 1")
+      assert(!contains(v, 2), "Filter not v 2")
+      assert(!contains(v, 3), "Filter not v 3")
+    }
+  }
+
+  test("forall") {
+    new TestSets {
+      assert(forall(s1, x => x == 1), "forall 1")
+      assert(forall(s2, x => x == 2), "forall 2")
+      assert(forall(s3, x => x == 3), "forall 3")
+      assert(!forall(s1, x => x == 0), "forall not s1 0")
+      assert(!forall(s2, x => x == 0), "forall not s2 0")
+      assert(!forall(s3, x => x == 0), "forall not s3 0")
+      assert(forall(s1, v13), "s1 v13")
+      assert(forall(s2, v13), "s2 v13")
+      assert(forall(s3, v13), "s3 v13")
+    }
+  }
+
+  test("exists") {
+    new TestSets {
+      assert(exists(v13, x => x == 1), "exists 1")
+      assert(exists(v13, x => x == 2), "exists 1")
+      assert(exists(v13, x => x == 3), "exists 1")
+      assert(!exists(v13, x => x == 0), "exists not 0")
+      assert(!exists(v13, x => x == 4), "exists not 4")
+    }
+  }
+
+  test("map") {
+    new TestSets {
+      val x = map(v13, x => x * 3)
+      assert(contains(x, 3), "map 1")
+      assert(!contains(x, 4), "map 2")
+      assert(!contains(x, 5), "map 3")
+      assert(contains(x, 6), "map 4")
+      assert(!contains(x, 7), "map 5")
+      assert(!contains(x, 8), "map 6")
+      assert(contains(x, 9), "map 7")
+      assert(!contains(x, 10), "map 8")
     }
   }
 }
-- 
cgit v1.1-2-g2b99