Set-builder Notation as a Powerful Data Constructor

*WARNING* Do not let the symbols scare you, please! Just take your time reading this. I promise you'll come out a better person afterwards.

Set-builder notation is perfect for defining a data set. It's in the name: Set-builder notation. Programmers use data sets every day, whether they realize it or not. In fact, usually when a data set is well understood a programmer can write code very easily to manipulate it. Mathematicians claim (OK not entirely, but you Mathematicians know what I'm talking about) even functions are just fancy sets of data. {(0,2),(1,6)} could be implicitly expressing a function.

Lets jump to the chase and construct a set of numbers that are even.

{ x ∈ N | x%2 = 0 }

Pretty simple right? It's pretty expressive too. Lets break this down.

{} indicates we are building a set.
x ∈ N means that x is an integer from zero to infinity.
| simply translates to "such that".
x%2 = 0 means if x has no remainder, it is even.

Together it could be read as "x is an element that is an integer, such that the element (x) is divisible by 2".

We'll get to how this ties into programming shortly. Lets up the complexity a bit.

{ x ∈ Q | 3/38 < x+m < 2/10, 0 < m < 10, m ∈ Z } 
∪ 
{ x ∈ N | x < 10 and is even }

...I hope your mind didn't explode. With that we've just defined a set that is a combination (known as a union) of two sets. The set on the left is a bunch of fractions between a range, and the one on the right is just { 0, 2, 4, 6, 8 }. Statements like "is even" are valid in set-builder notation.

This clearly demonstrates the expressiveness of set-builder notation with numbers, but what about characters, or any object? That can be done too.

A = { Golden Doodle, Great White Shark, Maine Coon }
{ x ∈ A | x is a breed of dog }

A is known as "roster notation". It's just a really simple way of building a set, but much less expressive. Pretty cool though, eh? This leads us to a way of no longer needing chunks of code to build arrays/lists/sets.

Lets try this in a short Java example:

ArrayList<Animal> get_dog_breeds() {
  ArrayList<Animal> dogs = new ArrayList<Animal>();
  for(int i = 0; i < Animals.size(); i++) {
    if(Animals.get(i).type == "dog")
      dogs.add(Animals[i]);
  }
  return dogs;
}

Ugh, wow that looks ugly. In fact it's surprising people agree to do this every day. Lets try it out with Python since it translates a little easier.

[ animal for animal in Animals if animal.type == "dog" ]

Holy jeez. That would convince anyone not to use Java.

I actually wonder what this could look like in Java.

[ animal; for(Animal animal : Animals); animal.type == "dog" ]

I don't know. Use your imagination.

So now you've been exposed to set-builder notation and an actual example from a programming language using that idea. Even if your language doesn't support something similar to set-builder notation, with a little bit of templating, you can get something close.

A lot of people have the opinion that math isn't necessary for programming, which I totally agree with. The thing is, math offers a lot of tools that make programmers much better than those who don't use it.

Go Set-Builder, Go.

Comments

Popular Posts