Take the 2-minute tour ×

In Stanford Scala course I've come across the following assignment:

Exercise 1 – Sets as Functions:

In this exercise we will represent sets as functions from Ints to Booleans:

type Set = Int => Boolean

a) Write a function "set" that takes an Int parameter and returns a Set containing that Int.

b) Write a function "contains" that takes a Set and an Int as parameters and returns true if the Int is in the Set and false otherwise.

c) Write the functions "union", "intersect", and "minus" that take two Sets as parameters and return a Set.

d) Can you write a function "subset" which takes two Sets as parameters and returns true if the first is a subset of the second and false otherwise?

Solutions to the a, b and c are fairly trivial:

def set(i: Int): Set = n => n == i

def contains(s: Set, i: Int) = s(i)

def union(a: Set, b: Set): Set = i => a(i) || b(i)

def intersect(a: Set, b: Set): Set = i => a(i) && b(i)

def minus(a: Set, b: Set): Set = i => a(i) && !b(i)

But is there any elegant solution for d? Of course, strictly speaking, the answer to d is "yes", as I can write something like:

def subset(a: Set, b: Set) = Int.MinValue to Int.MaxValue filter(a) forall(b)

but that's probably not the right way.

share|improve this question
I think that is the right way. –  Malvolio Aug 6 '11 at 3:26
the course has nothing to do with Stanford –  Seth Tisue Oct 1 '12 at 14:22
@Seth It was from Stanford's course, not current Coursera one even though the second assignment there is almost the same. Notice it didn't have -bound/bound tip, which btw answers my question. –  Grozz Oct 1 '12 at 22:38
I stand corrected. –  Seth Tisue Oct 2 '12 at 17:56
add comment

2 Answers

up vote 8 down vote accepted

I don't think it's possible without iterating through all the integers. For a pseudo-proof, look at the desired type:

def subset: (a: Set, b: Set): Boolean

Somehow, we've got to produce a Boolean when all we have to work with are sets (a, b) of type Int => Boolean, and integer equality (Int, Int) => Boolean. From these primitives, the only way to get a Boolean value is to start with Int values. Since we don't have any specific Int's in our hands, the only option is to iterate through all of them.

If we had a magical oracle, isEmpty: Set => Boolean, the story would be different.

A final option is to encode "false" as the empty set and "true" as anything else, thus changing the desired type to:

def subset: (a: Set, b: Set): Set

With this encoding, logical "or" corresponds to the set union operation, but I don't know that logical "and" or "not" can be defined easily.

share|improve this answer
add comment

I agree with Kipton Barros, you would have to check all values for Ints since you want to prove that forall x, a(x) implies b(x).

Regarding the optimization of it, I'd probably write:

  def subset(a: Set, b: Set) = Int.MinValue to Int.MaxValue exists(i => !a(i) || b(i))

since !a(i) || b(i) is equivalent to a(i) implies b(i)

share|improve this answer
From where do you get that function "exists"? Is it somewhere defined or did you leave it undefined? –  L4_ Nov 6 '13 at 15:05
The expression Int.MinValue to Int.MaxValue creates a Range type, which inherits from IterableLike, TraversableLike, TraversableOnce and finally from GenTraversableOnce, which is where the function exists is defined. Check out the docs at scala-lang.org/api/current/… –  Carlos Eduardo López Camey Nov 7 '13 at 18:42
Thanks, that day I seemed to be blind to see that it was a method call of that range. –  L4_ Nov 8 '13 at 12:37
add comment

Your Answer


