Skip to content

Instantly share code, notes, and snippets.

@kgadek
Created October 5, 2012 17:11
Show Gist options
  • Save kgadek/3841058 to your computer and use it in GitHub Desktop.
Save kgadek/3841058 to your computer and use it in GitHub Desktop.
Scala: bughunting in assignment from Coursera's course
package funsets
import common._
/**
* 2. Purely Functional Sets.
*/
object FunSets {
/**
* We represent a set by its characteristic function, i.e.
* its `contains` predicate.
*/
type Set = Int => Boolean
/**
* Indicates whether a set contains a given element.
*/
def contains(s: Set, elem: Int): Boolean = s(elem)
/**
* Returns the set of the one given element.
*/
def singletonSet(elem: Int): Set = (x: Int) => 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)
/**
* Returns the intersection of the two given sets,
* the set of all elements that are both in `s` or `t`.
*/
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)
/**
* Returns the subset of `s` for which `p` holds.
*/
def filter(s: Set, p: Int => Boolean): Set = intersect(s,p)
/**
* 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(a: Int): Boolean = {
if (a>bound) true
else if (diff(s,p)(a)) false
else iter(a+1)
}
iter(-bound)
}
/**
* Returns whether there exists a bounded integer within `s`
* that satisfies `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 => s(f(x))
/**
* Displays the contents of a set
*/
def toString(s: Set): String = {
val xs = for (i <- -bound to bound if contains(s, i)) yield i
xs.mkString("{", ",", "}")
}
/**
* Prints the contents of a set on the console.
*/
def printSet(s: Set) {
println(toString(s))
}
}
package funsets
import org.scalatest.FunSuite
import org.junit.runner.RunWith
import org.scalatest.junit.JUnitRunner
/**
* This class is a test suite for the methods in object FunSets. To run
* the test suite, you can either:
* - run the "test" command in the SBT console
* - right-click the file in eclipse and chose "Run As" - "JUnit Test"
*/
@RunWith(classOf[JUnitRunner])
class FunSetSuite extends FunSuite {
/**
* Link to the scaladoc - very clear and detailed tutorial of FunSuite
*
* http://doc.scalatest.org/1.8/index.html#org.scalatest.FunSuite
*
* Operators
* - test
* - ignore
* - pending
*/
/**
* Tests are written using the "test" operator and the "assert" method.
*/
test("string take") {
val message = "hello, world"
assert(message.take(5) == "hello")
}
/**
* For ScalaTest tests, there exists a special equality operator "===" that
* can be used inside "assert". If the assertion fails, the two values will
* be printed in the error message. Otherwise, when using "==", the test
* error message will only say "assertion failed", without showing the values.
*
* Try it out! Change the values so that the assertion fails, and look at the
* error message.
*/
test("adding ints") {
assert(1 + 2 === 3)
}
import FunSets._
test("contains is implemented") {
assert(contains(x => true, 100))
}
/**
* When writing tests, one would often like to re-use certain values for multiple
* tests. For instance, we would like to create an Int-set and have multiple test
* about it.
*
* Instead of copy-pasting the code for creating the set into every test, we can
* store it in the test class using a val:
*
* val s1 = singletonSet(1)
*
* However, what happens if the method "singletonSet" has a bug and crashes? Then
* the test methods are not even executed, because creating an instance of the
* test class fails!
*
* Therefore, we put the shared values into a separate trait (traits are like
* abstract classes), and create an instance inside each test method.
*
*/
trait TestSets {
val s1 = singletonSet(1)
val s2 = singletonSet(2)
val s3 = singletonSet(3)
}
/**
* This test is currently disabled (by using "ignore") because the method
* "singletonSet" is not yet implemented and the test would fail.
*
* Once you finish your implementation of "singletonSet", exchange the
* function "ignore" by "test".
*/
test("singletonSet(1) contains 1") {
/**
* We create a new instance of the "TestSets" trait, this gives us access
* to the values "s1" to "s3".
*/
new TestSets {
/**
* The string argument of "assert" is a message that is printed in case
* the test fails. This helps identifying which assertion failed.
*/
assert(contains(s1, 1), "Singleton")
}
}
test("union contains all elements") {
new TestSets {
val s = union(s1, s2)
assert(contains(s, 1), "Union 1")
assert(contains(s, 2), "Union 2")
assert(!contains(s, 3), "Union 3")
}
}
test("intersections") {
new TestSets {
val sa = intersect(s1, s2)
val sb = intersect(s1, s1)
assert(!contains(sa, 1), "Intersect 1")
assert(!contains(sa, 2), "Intersect 2")
assert(contains(sb, 1), "Intersect 3")
}
}
test("difference") {
new TestSets {
val s = diff(s1, s2)
assert(contains(s, 1), "Diff 1")
assert(!contains(s, 2), "Diff 2")
assert(!contains(s, 3), "Diff 3")
}
}
test("filtering") {
new TestSets {
val s = filter(s1, s2)
assert(!contains(s, 1), "Filter 1")
assert(!contains(s, 2), "Filter 2")
assert(!contains(s, 3), "Filter 3")
}
}
test("forall predicate") {
new TestSets {
assert(forall(s1, s1))
assert(!forall(s1, s2))
}
}
test("exists predicate") {
new TestSets {
assert(exists(s1, s1))
assert(!exists(s1, s2))
}
}
test("mapping") {
new TestSets {
val s = map(s1, x => x*2)
assert(forall(s, s2))
}
}
}
@yogiHulk
Copy link

i think the map function is wrong. You're supposed to apply inverse f on the right hand side
initSet is 5,6,7
function is *2
newSet 10,12,14
map(initSet, f)(10) = newSet(10) = initSet(5) = true

@hiemal
Copy link

hiemal commented Jun 18, 2016

The map function is indeed wrong. As yogiHuld said, you need to implement an inverse, which suggests that you need the 'exist' function to test if there is element in initSet that satisfies f(element) in newSet.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment