The Set Function

Estimated reading time: 2m 58s

What is a Set? A Set can tell you whether or not an value is a member of the Set. This means that a Set is merely a function, specifically of A => Boolean. In this post I will explore the usage of combinators to build a Set from elementary functions alone.

Modeling a Set

I’m going to use a trait to model a Set:

trait Set[A] extends (A => Boolean)

And define the most elementary of Sets, the empty Set and singleton Set:

def empty[A](): Set[A] = _ => false

def singleton[A](value: A): Set[A] = test => test == value

val emptyInts = empty[Int]()
emptyInts(1) // false
emptyInts(2) // false

val justOne = singleton(1)
justOne(1) // true
justOne(2) // false

But what about more complex sets?

The Set of natural numbers

The Set of natural numbers requires more work to model. Specifically, it represents a lower bound of 0:

def nat(value: Int): Boolean = value >= 0

But this is very concrete. A lower bound specifically is a type of predicate, and this can be parameterized:

def satisfy(predicate: A => Boolean): Set[A] = predicate

def nat: Set[Int] = satisfy(_ >= 0)

nat(-1) // false
nat(0) // true
nat(1) // true

Building a Set

How do I add values to the Set? I have to be able to combine Sets:

trait Set[A] extends (A => Boolean) {

  def |[B >: A](other: Set[B]): Set[B] =
    value => this(value) || other(value)
}

By combining Sets, I can now specify that a value be one of two values in a Set:

val oneOrTwo = singleton(1) | singleton(2)

oneOrTwo(1) // true
oneOrTwo(2) // true
oneOrTwo(3) // false

But this | operator doesn’t allow me to set boundaries using predicates, as it represents a disjoint Set. This means values must be present at least in one Set or the other:

val singleDigits = satisfy(_ >= 0) | satisfy(_ <= 9)

singleDigits(10) // true
singleDigits(-1) // true

I need another operator requiring membership in both Sets, so that I can create a joint Set:

trait Set[A] extends (A => Boolean) {

  def |[B >: A](other: Set[B]): Set[B] =
    value => this(value) || other(value)

  def &[B >: A](other: Set[B]): Set[B] =
    value => this(value) && other(value)
}

The & operator now requires that the value exists in both Sets:

val singleDigits = satisfy(_ >= 0) & satisfy(_ <= 9)

singleDigits(2) // true
singleDigits(9) // true
singleDigits(10) // false
singleDigits(-1) // false

Building a complex Set

I’m going to build a weird Set of numbers from 0-100, 102, 104, 220-230, and all numbers greater than 300 that are divisible by 17:

val complexSet = (satisfy(_ >= 0) & satisfy(_ <= 100)) |
  singleton(102) |
  singleton(104) |
  (satisfy(_ >= 220) | satisfy(_ <= 230)) |
  (satisfy(_ >= 300) & satisfy(_ % 17 == 0))

complexSet(60) // true
complexSet(104) // true
complexSet(180) // false
complexSet(227) // true
complexSet(340) // true
complexSet(341) // false

Takeaway

Using functions alone, complex logic can be composed from atomic, testable building blocks. These functions that take other functions as arguments to produce new functions are referred to as combinators as they combine their capabilities.

Composing programs from small units ensures testability and ease in refactoring, as the single-responsibility principle is taken to its logical extreme with this technique.

Why don’t we use Sets as functions?

This seems like a cool way to model Sets, but that’s about where the utility stops. As an exercise, it’s fun to see what you can do to model Sets using functions alone, as this is an excellent vehicle for learning functional composition with combinators. In practice this would produce a Set with linear-time performance, and you don’t want that.

Please share with me your thoughts and feedback!