Creating Composable Sorting Hierarchies in Typescript
This post draws heavy influence from an incredible post from Brian Lonsdorf. The goal will be to define primitive sorting rules and and combine them to create sorting rules for more complex structures.
So the first thing we need to do is to have a way of specifying a comparison so that we can sort. To do this so that we can integrate nicely with Array.sort we use an enum with specified values of 1, -1, and 0 respectively. We’ll also create a generic interface defining what it means to compare two values.
As you can see, we now have the interface structure we need and some example instances of our Ord interface with ascending and descending. Those instances can be read as “ascending and descending are descriptions of how to order numbers”.
There are a couple of ways to use our instance. We can actually use our instance with the default Array.sort method by passing the compare function from our instance like so
We can also create a sort function that takes an A[] and an Ord<A> and sorts the array.
A second look at Descending
Looking back at our ascending and descending functions, it seems like a lot of similar code between them, and we probably won’t want to write those for every type. Luckily, now that we have our Ord<A> interface as an abstraction point for ordering, we can actually write a function that will produce the inverse ordering!
Sweet, now we’ve written descending in terms of ascending so that we don’t have to squint our eyes to determine whether we have our angle brackets pointing the correct way!
Our invert function just switches the order of arguments (thanks to gcanti for the much simpler implementation). Because our invert function relies only on the generic interface, it works for any instance of Ord<A>. Have an Ord<Date> or Ord<LiterallyAnyOtherType> that you want in descending order? No problem, just wrap it with invert and you’re done!
Composable Hierarchies
Now that we have our abstraction let’s see how we can make it composable. This is where our friend Closure again comes in. We want to be able to take two Ord<A> instances and combine them together to return another Ord<A> instance. This is the basis of composable architecture.
Our appendOrdering function takes two Ordering values and returns the first if it is not equal else it returns the second. This works like “sort by x and then y”.
Next we define append for Ord<A> which compares the values with the first and second Ord<A> instances and delegates off to appendOrdering to complete our “sort by this and then that” concept.
While that gets a bit complex and abstract, the important thing to remember here is that this code works for all Ord<A> instances, so this code only ever has to exist once.
Let’s see it in use to get a better intuition for how this all fits together.
Look at that beautiful composition of Ord<Person> instances! Our initial sort function still works and we could easily extend to include any other property that might exist on a more complex Person interface.
Contravariance to the rescue
As beautiful as our composition was, our Ord<Person> instances were pretty ugly. Basically we’re just comparing string properties on a Person object, but we’ve had to define string comparison on a specific property of a specific type. That seems very limited and a recipe for future boilerplate. Luckily we can do better with the power of contramap!
Our contramap function takes a function from B -> A and an Ord<A> and returns an Ord<B>! That means we can take primitive sorting algorithms and extend them to work for more complex types. contramap just applies the function to the values before comparing them.
In this article we’ve seen how to define ordering rules and combine them in a couple of different ways. We can now take primitive sorting rules and combine them, invert them, and extend them to work on more complex types. Just look at how easily we were able to define firstThenLastDescending!