Working with Sets as Functions

Question

From a FP course:

type Set = Int => Boolean  // Predicate

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

Why would that make sense?

assert(contains(x => true, 100))

Basically what it does is provide the value 100 to the function x => true. I.e., we provide 100, it returns true.

But how is this related to sets?

Whatever we put, it returns true. Where is the sense of it?

I understand that we can provide our own set implementation/function as a parameter that would represent the fact that provided value is inside a set (or not) - then (only) this implementation makes the contains function be filled by some sense/meaning/logic/functionality.

But so far it looks like a nonsense function. It is named contains but the name does not represent the logic. We could call it apply() because what it does is to apply a function (the 1st argument) to a value (the 2nd argument). Having only the name contains may tell to a reader what an author might want to say. Isn't it too abstract, maybe?

Answer 1

In the code snippet you show above, any set S is represented by what is called its characteristic function, i.e., a function that given some integer i checks whether i is contained in the set S or not. Thus you can think of such a characteristic function f like it was a set, namely

{i | all integers i for which f i is true}

If you think of any function with type Int => Boolean as set (which is indicated by the type synonym Set = Int => Boolean) then you could describe contains by

Given a set f and an integer i, contains(f, i) checks whether i is an element of f or not.

Some example sets might make the idea more obvious:

Set                                Characeristic Function
 empty set                          x => false
 universal set                      x => true
 set of odd numbers                 x => x % 2 == 1
 set of even numbers                x => x % 2 == 0
 set of numbeers smaller than 10    x => x < 10

Example: The set {1, 2, 3} can be represented by

val S: Set = (x => 0 <= x && x <= 3)

If you want to know whether some number n is in this set you could do

contains(S, n)

but of course (as you already observed yourself) you would get the same result by directly doing

S(n)

While this is shorter, the former is maybe easier to read (since the intention is somewhat obvious).