# "type Set = Int => Boolean" in Scala

can someone please explain to me this:

type Set = Int => Boolean

i don’t understand it.

thanks

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

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

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

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 `Int`s.

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

2 Likes

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

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: https://www.scala-lang.org/api/current/scala/collection/Set.html It has a final method apply: https://www.scala-lang.org/api/current/scala/collection/Set.html#apply(elem:A):Boolean 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.