Implementation of scala set.contains

Question

type Set = Int => Boolean
/**
* Indicates whether a set contains a given element.
*/
def contains(s: Set, elem: Int): Boolean = s(elem)

Why does this contains function work?

I don't get it. How does the () operator return true/false about existence of this element in set?

Answer 1

Taking this piece by piece, the type alias in the first line means that we can rewrite the second line as follows:

def contains(s: Int => Boolean, elem: Int): Boolean = s(elem)

But A => B is just syntactic sugar for Function1[A, B], so we can do more rewriting:

def contains(s: Function1[Int, Boolean], elem: Int): Boolean = s(elem)

s(elem) is also syntactic sugar—any time you "apply" a value to a value in this way, Scala desugars it to s.apply(elem):

def contains(s: Function1[Int, Boolean], elem: Int): Boolean = s.apply(elem)

And if you look at the apply method on Function1 you'll see that the types line up.

So that's it—we're just representing the set as its indicator function and then burying that under three layers of syntactic sugar.

---

Update to address the comment: representing a set as its indicator function makes it possible to model infinite sets (and lots of other sets) much more naturally than the usual list-based representation. Suppose I want a set of all odd numbers, for example. Using the representation you have here, this is easy:

val odds: Set[Int] = (_ % 2 != 0)

Try doing the same thing with HashSet, for example.

Answer 2

Set here is a function from Int to Boolean, so calling s(someInt) returns a boolean, you have of course to provide that function:

def contains(s: Set, elem: Int): Boolean = s(elem)

contains({ someInt => someInt == 1 }, 1) // returns true