Scala set function
Solution 1
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.
Solution 2
We have
Set A =
Returns the intersection of the two given sets,
the set of all elements that are both in `s` and `t`.
Set B =
Returns the subset of `s` for which `p` holds.
Isn't Set A is equivalent to Set B
def filter(s: Set, p: Int => Boolean): Set = intersect(s, p)
Related videos on Youtube
Grozz
Software developer at Uber. Intro to Scala blog (in Russian): http://groz.github.io
Updated on June 11, 2022Comments
-
Grozz over 1 year
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.
-
Michael Lorton over 12 yearsI think that is the right way.
-
-
mins over 8 yearsWhile the statement is correct, it doesn't provide and answer to the question.
-
Icoder over 8 years@mins answer is given by Ronak. I just wanted to say that Intersection of two set is a subset of any of those two set. I am adding exact answer as well.