A Point-Free Inner Join

In terms of prerequisites for this post, knowing what an inner join is, is not nearly as important as knowing what point-free programming is. For a more detailed introduction to either one, visit here and here.

Point-free programming is a style of functional programming which involves declaring functions without explicitly stating the arguments (or “points”, if you will) that it takes. Hence the name, Point-Free.

One might ask why should I program this way, since declaring arguments to a function is concise and leaves little question as to how the function works.

I would have to say that documentation or a type declaration does all that and more. So leave the “points” in there and forget them when declaring functions to facilitate readability.

For the remainder of this post, I will assume familiarity with the Ramda library, and JavaScript basics.

With that said, let’s look at a motivating problem and see if we can come up with a solution while writing point-free.

const list1 = [
{ id : 1, stuff: 5}, 
{ id : 2, stuff: 10}
]
const list2 = [
{ id : 1, otherstuff: 15}, 
{ id : 2, otherstuff: 20}
]

Given these two lists, I would like to have a new list where the objects now have the “stuff” and “otherstuff” properties. Some might say this isn’t a true inner join on a semantic level, but it is certainly resemblant of one…hence the catchy title of this post.

There are many solutions to this problem and I personally have taken a different route each time I’ve encountered it. However, the following approach stands out as the most “Functional” way.

I will detail each step for understanding and when all is crystal clear, I will implement the solution in a couple of lines. With that final blow, I hope the reader will start to see the point of point-free programming.

To start, we take the product of these two lists, with Ramda’s xprod.

xprod(list1, list2) 
/*
[
[{id: 1, stuff: 5}, {id: 1, otherstuff: 15}], 
[{id: 1, stuff: 5}, {id: 2, otherstuff: 20}], 
[{id: 2, stuff: 10}, {id: 1, otherstuff: 15}], 
[{id: 2, stuff: 10}, {id: 2, otherstuff: 20}]
]
*/

Here we have a list containing all pairs of the form (a, b) where a is in list1, and b is in list2. That is, in some sense, the cartesian product.

Now we will remove the pairs that do not have matching ids. Certainly, filter can do the job, but the predicate supplied to filter must examine a pair of objects and check whether they have the same id.

Alternatively, we can try an applied approach such as the following :

const checkPair = (pair) => eqProps(“id”)(head(pair))(last(pair))
filter(checkPair)(xprod(list1, list2))
/*
[
[{id: 1, stuff: 5}, {id: 1, otherstuff: 10}], 
[{id: 2, stuff: 15}, {id: 2, otherstuff: 20}]
]
*/

As nice as this is, it isn’t point-free, and writing “point-full” was certainly not the point of this post.

Problems such as this are usually the most troubling when trying to write point-free. Luckily, we have Ramda’s converge! Converge can be described as follows: Given a function F of arity N and a list of functions [f1,…, fN], we define converge(F, [f1,…,fN], x) = F(f1(x), …,fN(x)). A few small caveats being that each fn must have the same domain and their image must be a subset of the nth argument of F.

Essentially, fn applied to x must be an argument to F in its respective place. The simplest implementation of converge would be an average function for a list of numbers.

const average = converge(divide,[sum, length])
average([1,2,3]) // returns 2
/*
Converge at work
average([1,2,3]) =>
converge(divide, [sum, length])([1,2,3]) =>
divide(sum([1,2,3]), length([1,2,3])) =>
divide(6,3)=>
2
*/

Hopefully, it’s clear what our arguments to converge need to be in our checkPair predicate. Let’s consider the new and improved checkPair:

const checkPairPF = converge(eqProps(‘id’))([head,last])
checkPairPF([{id: 1, stuff: 5}, {id: 1, otherstuff: 10}])// true
filter(checkPairPtFree)(xprod(list1, list2))
/*
[
[{id: 1, stuff: 5}, {id: 1, otherstuff: 10}], 
[{id: 2, stuff: 15}, {id: 2, otherstuff: 20}]
]
*/

But we aren’t done there! Now we have the pairs that belong together, but they are still just that…pairs. We need to take each pair of objects and merge them (any identical keys will assume the value of the object on the far right).

The missing piece would be to map Ramda’s mergeAll across the filtered list, and I will leave it to the reader to convince themselves of this final nugget.

Using everything together, along with compose (any functional programmer’s bread and butter), we have this beautiful three-liner:

const checkPairPF = converge(eqProps(‘id’))([head,last])
const filterProd = filter(checkPairPF)
const innerJoinById = compose(map(mergeAll), filterProd, xprod)
innerJoinById(list1, list2)
/*
[
{"id": 1, "otherstuff": 15, "stuff": 5}, 
{"id": 2, "otherstuff": 20, "stuff": 10}
]
*/

So that’s it, a point-free inner join, if you will. Each individual piece of your solution should be dissected and reasoned with, but once we’re sure of its correctness, we wrapit up into one neat function. It really doesn’t get much prettier than this, and that’s the point of point-free programming.

Jesse Racicot studies Pure & Applied Mathematics at Concordia University and is Head of Engineering at Descript Software.