Set Theory with Functional JavaScript

Photo by Edwin Andrade on Unsplash

The mother of all mathematics they say, gimme a break. Well, that might be true to some degree, but one thing that surely piqued my interest is how relatable Set Theory in our daily life. Let’s say that I’m holding an apple? But wait, why do I call it by “apple” in the first place? I’m free to name it blorb if I so choose, but that will only confuse people I converse with. The word “apple” was there because english people chose to conventionally call it so. If it’s conventional, then why bother arguing what combination of letters that made up the words stood up for, as long as people agree what each of the words associates to. This association thing is what actually matters in set theory. Every nouns and verbs in the dictionary are our ways of associating certain things to words signified by their similar characteristics. We’re free to say that both the fruit I’m eating and the device I post this article with are "Apple", so you’d know that what matters isn’t the word itself but rather the characteristics. So, having a set of fruits like {orange, pineapple, Rihanna, banana} would be bizzare as hell.

Yes, that curly brackets are what conventionally accepted by mathematicians to denote a set, where it has to adhere to two rules. First, each of the elements are only allowed to appear only once in the set. Second, their orders doesn’t matter, unless it’s called an ordered set. So set {a, b, c} is considered equal to {c, a, b}. Meanwhile, the ordered set has also two rules to adhere to. First, the orders matter, like the winners of running competition. Second, any elements are allowed to appear more than once in the set, like a parcel of fruits where grapes may appear few dozens of times. In JS we actually have befitting data structures to represent each of them. An Object to represent a set, and an Array to represent ordered set. But in JS there’s also a class called "Set" which we could use for building a set in Array form.

uniqSet = arr => [... new Set(arr)]

uniqSet(['apple', 'orange', 'orange', 'banana'])
// gets ['apple', 'orange', 'banana']
// it shall omits any redundant elements

equal = (a, b) => a === b
sort = arr => [...arr].sort(
  (a, b) => (''+a).localeCompare(''+b)
)
equalSet = (setA, setB) => equal(...
  [setA, setB].map(sort).map(JSON.stringify)
)

equalSet(['a', 'b', 'c'], ['b', 'c', 'a']) // true

Now let’s have a case here, in my class there are about thirty students. If I use the word “students”, then they’re all belong to this set. But if I use the word “gender”, suddenly there are two sets emerged from my class. If I use grades A to F, then all of them could be split into 6 unique sets. What if I make a set called “Alex”, there would be a set that contains exactly one element, and the rest of the class shall belong to the set “not Alex”. But if there are two “Jane”s in the class, then the “Jane” set could contain 2 elements. Does the two Janes in the Jane set exactly equal? Of course it doesn’t, for one is blonde while the other is Asian. Sorry if my analogies didn’t reach you quite well. I’m just trying to say that any set you could ever think of, is our way of categorizing things according to certain characteristics, whatever they are. Then without furtherado, let me show you what set theory has to offer for this kind of problems.

Union of Sets

Let’s say in this class of thirty three are students who take math class and physics class. Most of them took those class exclusively, while some of them took both at once. Now let’s say that you want to group them in a new set "any students who takes math or physics class". What would you do? It’s intuitive to think that the group shall cover anyone who take math class only, physics class only, and those who took both at once. Why bother involving those who took both at once? Because if you ask any of them in this third category, "Do you take any of math class or physics?" They’d answer yes. And as this new group consists of those three sub-groups, it’d be logical for the new set to consist all of those students whom meet the criteria with no redundancy. So, how to express this union logic in JS? This is how it’s done functionally:

unionSet = sets => uniqSet(sets.reduce(
  (acc, inc) => [...acc, ...inc], []
))

unionSet([ ['a', 'd'], ['e', 'c'], ['b', 'd'] ])
// gets ['a', 'c', 'd', 'b', 'e']

Intersection of Sets

Now let’s say that we want only those who took both math AND physics class at once, the group could be smaller right? Among these thirty students 22 of them take either math or physics exclusively, the other 8 took both classes at once. What logic can we build to get the names of those 8 students? Of course, by finding the names that appears in math class list and physics class list. Do we ought to use for loop and conditional statement to face this problem? Nah. This is how it’s done in functional JS:

interSet = (setA, setB) =>
  setA.filter(i => setB.includes(i))

interSet(['a', 'b'], ['b', 'c']) // gets ['b']

Difference or Complement of Set

We already knew that the number of students in this class are thirty, if we know that the number of female students are 14, we’d intuitively know that there should be 16 male students here. Let’s say that we have the names of all the students and the name of all female students, how do we suppose to make a function which when given those two sets — namely the universe and the target set — it shall yield the complement elements? We’d intuitively think to check each of the elements in the universe set and remove those that exists in the target set right? So, this is how to put it in functional JS:

differSet = (setA, setB) =>
  setA.filter(i => !setB.includes(i))

differSet(['a', 'b'], ['b']) // gets ['a']

Notice both interSet and differSet only difference is in the filtering expression, where it contains a negation. We don't have to create separate functions for Difference and Complement as they're actually has similar concept.

Symmetric Difference of Set

Now let’s say that you’d like to have a set that contains students whom exclusively belongs to math class or physics class, but not those whom take both at once. It’d be intuitive to think of finding the union of both set first (the math class set and the physics class set) then find its difference to the intersection of both set. Following the prior logic, then the function should be like this:

symDiff = (setA, setB) => unionSet([
  differSet(setA, setB), differSet(setB, setA)
])

symDiff(['a', 'b', 'c'], ['c', 'd', 'e'])
// gets [’a’, 'b’, 'd’, 'e’]

Notice that the only elements left are a, b, d, and e where each belongs to particular set, not both. But there isn’t only one path leads to Rome, so does the Symmetric Difference. You can also imagine it by unify the two set first and then cut the intersection part. The function goes like this:

symDiff = (setA, setB) => differSet(
  unionSet([setA, setB]), interSet(setA, setB)
) // alternate version

symDiff(['a', 'b', 'c'], ['c', 'd', 'e'])
// gets [’a’, 'b’, 'd’, 'e’] too

Cartesian Set

Let’s say you want to make heat in the classroom by setting up team vs team competition. Each team consists of three members, so does the opposing team. You wanna judge the final score by the sum of wins the team has after each contestant face each of the other contestants of the opposing team once. So that means, the amount of duel shall equal to the multiplication of the size of each team, in this case 3x3 or 3 squared or 9. As a lazy teacher, I’d like to have JS set up all the matching combinations, so here is how it’s should be done:

carteSet = (setA, setB) =>
  setA.flatMap(i => setB.map(
    j => j.length ? [i, ...j] : [i, j]
  ))

carteSet(['a', 'b', 'c'], ['d', 'e', 'f']) 
/* gets 9 combinations [
  ['a', 'd'], ['a', 'e'], ['a', 'f'],
  ['b', 'd'], ['b', 'e'], ['b', 'f'],
  ['c', 'd'], ['c', 'e'], ['c', 'f']
] */

But unfortunately this lecturer is even lazier to grade the duel scores by himself, I have to invite three seniors from upper class whom each got to judge all the nine matches. That’ll also make the judging less subjective by one person, right? So this is how the lazy teacher set up the grading tasks:

carteSet(
  ['x', 'y', 'z'],
  carteSet(
    ['a', 'b', 'c'],
    ['d', 'e', 'f']
  )
)

/* gets 27 of combinations [
  ['x', 'a', 'd'], ['x', 'a', 'e'], ['x', 'a', 'f'],
  ['x', 'b', 'd'], ['x', 'b', 'e'], ['x', 'b', 'f'],
  ['x', 'c', 'd'], ['x', 'c', 'e'], ['x', 'c', 'f'],

  ['y', 'a', 'd'], ['y', 'a', 'e'], ['y', 'a', 'f'],
  ['y', 'b', 'd'], ['y', 'b', 'e'], ['y', 'b', 'f'],
  ['y', 'c', 'd'], ['y', 'c', 'e'], ['y', 'c', 'f'],

  ['z', 'a', 'd'], ['z', 'a', 'e'], ['z', 'a', 'f'],
  ['z', 'b', 'd'], ['z', 'b', 'e'], ['z', 'b', 'f'],
  ['z', 'c', 'd'], ['z', 'c', 'e'], ['z', 'c', 'f']
] */

Now what if we want to have a function which when given an array of sets, it shall yield all the possible unique combinations of each elements? This is how it would like:

multiCarte = ([head, ...tail]) =>
  tail.length === 1 ? carteSet(head, tail[0])
  : carteSet(head, multiCarte(tail))

multiCarte([
  ['a', 'b', 'c'],
  ['d', 'e', 'f'],
  ['x', 'y', 'z']
])
/* gets 27 combinations [
  ['a', 'd', 'x'],
  ['a', 'd', 'y'],
  ['a', 'd', 'z'],
  ['a', 'e', 'x']... and so on
] beautiful */

// Codes explanation
multiCarte = ([head, ...tail]) => // split the head from the rest
  tail.length === 1 // is there only 1 set left in the tail?
  ? carteSet(head, tail[0]) // if yes, then carteSet the last two
  : carteSet(head, multiCarte(tail)) // if not, loop the tail deeper

Hey hey, waitt.. That’s exactly the simpler solution of multi-dimentional combinatoric function we faced before. It means that the multiCarte function can yield a flattened multi-dimentional matrix that consists of the combinations of all given axis. Oh boy, I can die peacefully after this.

Codes Recap

equal = (a, b) => a === b

sort = arr => [...arr].sort(
  (a, b) => (''+a).localeCompare(''+b)
)

uniqSet = arr => [... new Set(arr)]

equalSet = (setA, setB) => equal(...
  [setA, setB].map(sort).map(JSON.stringify)
)

unionSet = sets => uniqSet(sets.reduce(
  (acc, inc) => [...acc, ...inc], []
))

interSet = (setA, setB) =>
  setA.filter(i => setB.includes(i))

differSet = (setA, setB) =>
  setA.filter(i => !setB.includes(i))

symDiff = (setA, setB) => unionSet([
  differSet(setA, setB), differSet(setB, setA)
])

carteSet = (setA, setB) =>
  setA.flatMap(i => setB.map(
    j => j.length ? [i, ...j] : [i, j]
  ))

multiCarte = ([head, ...tail]) =>
  tail.length === 1 ? carteSet(head, tail[0])
  : carteSet(head, multiCarte(tail))