"type Set = Int => Boolean" in Scala

Question
1

can someone please explain to me this:

type Set = Int => Boolean

i don’t understand it.

thanks

2

What you do not understand about it? the type keyword? The concept of a type alias? the arrow (=>)? The concept of a function? or why we can say that a Set is the same as a Fuction from an Int into a Boolean?

2 Likes
3

why we can say that a Set is the same as a Function from an Int into a Boolean?

4

So first of all remember this is just for academic purposes.
Second, it is important to be clear that in this case we are not representing any generic set but just sets of numbers (integers).

With that in mind, we can say that the most simplest definition of a Set is just check if an element is present or not.

So we can do this:

// The empty set
val empty: Set = _ => false

// The set that just contains the number 2
val justTwo: Set = {
  case 2 => true
  case _ => false
}

// The set of my favorite numbers.
val favorites: Set = {
  case 0 => true
  case 1 => true
  case 3 => true
  case 5 => true
  case _ => false
}

// The union of two sets can be defined like this
def union(s1: Set, s2: Se): Set = x => s1(x) || s2(x)

// The intersection of two sets can be defined like this
def intersect(s1: Set, s2: Se): Set = x => s1(x) && s2(x)
2 Likes
5

One can think of the “core” operation of a set as being contains() -
“is something in the set or not?”.

In this formulation, contains() is a thing that can take an A (the
type of thing the set can “contain”) and gives back a Boolean
indicating if the thing is in the set. Something that takes an A and
gives back a Boolean is at least conceptually a function from A to
Boolean, which we can write as A => Boolean.

In your case, I’m guessing it’s simplified by dropping the A, and
defining a Set as a set of Ints.

If this is from the progfun course, enjoy it, it’s good.

2 Likes
6

In general, a “set” is a group of objects that satisfy some property. There are two ways to describe such groupings

  1. Existentially, by identifying precisely all the elements that are in the group
  2. Intentionally, by testing all the conditions necessary and sufficient to determine if a particular element is in the group

The Set data structure that holds particular elements in memory is the existential kind. For instance, you can have Set(1, 2, 3). This is a Set[Int] that contains exactly those three integers. If you check whether any arbitrary integer is in the set, you only get true for those three integers.

You can also define this set intentionally as “integers greater than 0 and less than 4”. In this formulation, to figure out if an element is in the set you don’t have to compare it to what you have in memory, you can test membership with a boolean comparison: i > 0 && i < 4.

More generally, any boolean-valued function defines an intentional set over its parameters.

For integers in code, you could write these as

type ExistentialSet = collection.Set[Int]
type IntentionalSet = Int => Boolean

This can be useful as there are things intentional sets can do more easily than existential sets, like have very large or infinite domains. What if you wanted the set of all positive primitive integers? You probably don’t want to load 2 billion Int into memory, but you would not mind writing i > 0.

4 Likes
7

In context of type hierarchy in Scala standard library the answer (analogy between sets and functions) is actually quite simple:
scala.collection.Set[A] is a subtype scala.Function1[A, Boolean] (function type can be written as A => Boolean using syntax sugar).

Look at: Set It has a final method apply: Set with following documentation:

final def apply(elem: A): Boolean

Tests if some element is contained in this set.
This method is equivalent to contains. It allows sets to be interpreted as predicates.

elem - the element to test for membership.
returns - true if elem is contained in this set, false otherwise.

Definition Classes - SetOps → Function1
Annotations - @inline()

Indeed, as documentation says, scala.collection.Set extends scala.collection.SetOps which in turn extends scala.Function1.

There are more analogies in Scala standard library, e.g.