Today’s DevAdvent 2022 issue is about set theory. Given two arrays of elements, how do I find their difference? There is a very easy way to do this. And also to do the intersection of two arrays and to calculate their geometric difference.
The Problem: Array.diff()
link to the Kata
Your goal in this kata is to implement a difference function, which subtracts one list from another and returns the result.
It should remove all values from list a
, which are present in list b
keeping their order.
array_diff({1, 2}, 2, {1}, 1, *z) == {2} (z == 1)
If a value is present in b, all of its occurrences must be removed from the other:
array_diff({1, 2, 2, 2, 3}, 5, {2}, 1, *z) == {1, 3} (z == 2)
Array.diff(): A \ B
(also written A − B
)

But let’s start with the basic problem. To solve it I start from the Wikipedia definition of difference between sets:
Given any two sets A
and B
, the set difference A \ B (also written A − B)
is the set of all things that belong to A
but not B
. Especially when B
is a subset of A
, it is also called the relative complement of B
in A
.
I can translate this definition into an algorithm:
- for each element of A
- check if it belongs to B
- if it doesn’t belong to B, go to the next element
- if it belongs to B, I delete it from A
I can also rewrite it in the form:
- filter every element of A that does not belong to B
At this point I have everything I need. I can use Array.filter() method to select values. And decide to filter all values based on the result of Array.includes() method:
export const arrayDiff = (a: number[], b: number[]): number[] =>
a.filter((x) => !b.includes(x));
Array.intersect(): A ∩ B

After solving the basic problem, I can have fun and try adding more operations with arrays and sets. Pass at the intersection of the sets:
Given any two sets A
and B
, their intersection A ∩ B
is the set of all things that are members of both A
and B
. If A ∩ B = ∅
, then A and B are said to be disjoint.
I can translate this definition into an algorithm:
- for each element of A
- check if it belongs to B
- if it doesn’t belong to B, I delete it from A
- if it belongs to B, go to the next element
I can also rewrite it in the form:
- filter every element of A that does belong to B
export const arrayIntersect = (a: number[], b: number[]): number[] =>
a.filter((x) => b.includes(x));
Array.union(): A ∪ B

Joining two sets is a simple problem in JavaScript. But before the solution, the definition:
Given any two sets A
and B
, their union A ∪ B
is the set of all things that are members of A
or B
or both.
In this case there is the Array.concat() method which allows you to join two arrays:
export const arrayUnion = (a: number[], b: number[]): number[] => a.concat(b);
Array.symDiff(): A Δ B

The next operation is the symmetric difference. Wikipedia defines it like this:
Given any two sets A
and B
, their symmetric difference A Δ B
is the set of all things that belong to A or B but not both. One has to be a member of A and not a member of B, or a member of B and not a member of A: A Δ B = (A \ B) ∪ (B \ A)
.
In fact it is an operation composed of two different ones. I can write it like this:
export const arraySymDiff = (a: number[], b: number[]): number[] =>
arrayUnion(arrayDiff(a, b), arrayDiff(b, a));
Or if I prefer to use an extended notation:
export const arraySymDiff = (a: number[], b: number[]): number[] =>
a.filter((x) => !b.includes(x)).concat(b.filter((x) => !a.includes(x)));
Array.cartesian(): A × B
The last operation to deal with is the Cartesian product of two arrays. Wikipedia defines it like this:
Given any two sets A
and B
, their cartesian product A × B
is the set of all ordered pairs (a,b)
such that a
is an element of A
and b
is an element of B
.
In other words, it is an operation that allows you to generate all possible pairs of the elements of two arrays.
I can solve the problem with a function like this:
export const arrayCartesian = (a: number[], b: number[]): number[][] =>
a.map((x) => b.map((y) => [x, y])).flat();
Or with this:
const arrayCartesian = (a: number[], b: number[]): number[][] =>
a.reduce((p, x) => [...p, ...b.map((y) => [x, y])], []);
Conclusion

Finally I can add these functions to the prop. This way I can use them directly with each array:
Array.prototype.diff = function (arr2) {
return this.filter((x) => !arr2.includes(x));
};
Array.prototype.intersect = function (arr2) {
return this.filter((x) => arr2.includes(x));
};
Array.prototype.union = function (arr2) {
return this.concat(arr2);
};
Array.prototype.symDiff = function (arr2) {
return this.diff(arr2).concat(arr2.diff(this));
};
Array.prototype.cartesian = function (arr2) {
return this.reduce((p, x) => [...p, ...arr2.map((y) => [x, y])], []);
};
[1, 2, 3].diff([2, 3]);
[1, 2, 3].intersect([2, 3]);
[1, 2, 3].union([2, 3]);
[1, 2, 3].symDiff([2, 3]);
[1, 2, 3].cartesian([2, 3]);