Multiple condition array sorting made easy

Andrew Makarov — Mon, 22 Aug 2022 21:55:00 +0000

Hi everyone, i'd like to introduce some research and solution for issue, that follows every developer (mostly front-end) from career start - sorting collections by multiple conditions. I must point out, that i'm not the author of fundamental concepts of solution and they where implemented a long time before me in pure functional languages like Haskell, but i found that implementation is very elegant and portable to other languages.

Before we start
Problem
Some theory
Remove abstraction overhead
Conclusion
Live example

Before we start

All code examples will be written on TypeScript because type system of this language is good enough to solve this problem in more robust way and it is simple enough, plus this article is more interesting for front-end develpers, but you can manually adopt implementation to any other language without much problems.

Problem

Every developer has faced the challenge at least once in their career - sort collection by this attribute AND by that attribute AND by other AND so on...For example - multiple column table sorting.

The most common and naive approach to solve this problem is to split array by first condition equality, than by second and so on, and then flatten all resulting arrays. Familiar situation? The obvious disadvantages of the solution is memory consumption and complexity, that will be grow proportionally to conditions increasing and must-reach-nirvana in recursion if you decide to generalize this approach.

The second popular approach is to write unique function for every sort requirements. BTW, this approach is disposable but there is good start and we can take it as base for our decisions.

Let's start and define collection item:

interface User {
  name: string;
  city: string;
  age: number;
  salary: number;
  position: 'director' | 'manager' | 'office-cheif' | 'intern';
  department: 'research' | 'facility' | 'sales';
}

Some theory

Every sorting is achieved by answering question "which of the two elements comes first?" repeatedly, in other words - ordering operation. The result of ordering is - (first) EQual / Greater / Lower (Than second) by criteria. Some languages define readable literals for this values - EQ/GT/LT, others define numerical (0, 1, -1). The first thing we could do is to negate this difference

type EQ = 0;
type GT = 1;
type LT = -1;

const EQ: EQ = 0;
const GT: GT = 1;
const LT: LT = -1;

Furthermore, we can define union that represent result of Ordering operation

type Ordering = EQ | GT | LT;

There is some data types in programming languages, that represents sequence, that can be repeated in natural way. Most common type is string:

'quick fox '.concat('jump') -> 'quick fox jump'

And such concatenation is potentially infinite. Some similar types are arrays, even Numbers. It can be even user-defined types. For generalizing this behaviour, functional languages has implemented special type - Monoid.

Monoid is type, that define binary associative concatenation operator and defines neutral element for this operation. Neutral element is element, that does not change second operand of concatenation.Assume that <> operator is "concatenation". As any data type, monoid has some rules and restrictions to work properly called "laws" and your "real" monoid must obey three laws:

Left identity '' <> 'a' === 'a'
Right identity 'a' <> '' === 'a'
Associativity ('a' <> 'b') <> 'c' === 'a' <> ('b' <> 'c')

Lets test this laws on arrays:

Left identity: assert([].concat([1,2,3])).equal([1,2,3])
Right identity: assert([1,2,3].concat([])).equal([1,2,3])
Associativity:

const a1 = [1,2];
const a2 = [3];
const a3 = [4];

assert(a1.concat(a2).concat(a3)).equal(a1.concat(a2.concat(a3)))

Interesting thing is - Numbers are monoids twice - by sum and by multiplication, the only difference is neutral element - for sum - 0, for multiplication - 1.

Let's define Monoid interface:

interface Monoid<T> {
  empty: T;
  concat(a: T, b: T): T;
  concatAll(list: T[]): T;
}

It is very convenient, because we can implement Monoid behaviour for our Ordering type and check compliance with the laws! The left operand is previous comparison and second is current. If previous comparsion result was Equal, we just return second, because it can be different, BUT if element are not equal, we can not change equality and must omit current comparison.

const monoidOrdering: Monoid<Ordering> = {
  empty: EQ,
  concat(a, b) {
    return a === EQ ? b : a;
  },
  concatAll(list) {
    return list.reduce(this.concat, this.empty);
  },
}

// left identity
assert(monoidOrdering.concat(monoidOrdering.empty, GT)).equal(GT);
// right identity
assert(monoidOrdering.concat(GT, monoidOrdering.empty)).equal(GT);
// associativity
assert(monoidOrdering.concat(monoidOrdering.concat(GT, LT), EQ)).equal(monoidOrdering.concat(GT, monoidOrdering.concat(LT, EQ)));

Now we have such powerful types and can do even more for our general approach - remove many options to compare primitive types in JavaScript and define common compare function for primitive types.

function compare<T>(a: T, b: T): Ordering {
  return a > b ? GT : a < b ? LT : EQ;
}

The next step will be defining new type Ord:

interface Ord<A> {
  compare(a: A, b: A): Ordering;
}

// fabric function for Ord
function fromCompare<A>(comparator: Ord<A>['compare']): Ord<A> {
  return {
    compare: comparator
  }
}

Ord type implements comparsion operation, that has answer to our question "which of the two elements comes first?", thats why its name ORD(ering). There is one very important point - our operation returns monoid, and most beautiful thing is that Ord type can implement monoid behaviour etiher in natural way!
But TypeScript type system has some limitations - if Generic type can hold Generic type, we can't extract concrete type from this wrapper - type A<X<???>> = ... <- error. Thats why we must use workaround and define constructor for Ord monoid, that wraps our concrete type:

function getOrdMonoid<T>(): Monoid<Ord<T>> {
  return {
    empty: fromCompare(() => monoidOrdering.empty),
    concat(a, b) {
      return fromCompare(
        (first, second) => monoidOrdering.concat(a.compare(first, second), b.compare(first, second))
      );
    },
    concatAll(list) {
      return list.reduce(this.concat, this.empty)
    },
  }
}

Now we can create and concatenate our ordering funtcions and be 100% sure, that it will be properly ordered by multiple conditions because monoid laws did all work for us.

const ordNum = fromCompare<number>(compare);
const ordNumMonoid = getOrdMonoid<number>();

const dualOrdNum = ordNumMonoid.concat(ordNum, ordNum);
const tripleOrdNum = ordNumMonoid.concat(dualOrdNum, ordNum);

But it is useless for now in our case, because we can't access to required properties of collection item. Most naive way is to define many functions for every required property

function compareUserByName(a: User, b: User) {
  return compare(a.name, b.name);
}
const ordUserName = fromCompare(compareUserByName);

Btw, such decision is not effective and our goal is completely generalized solution. All we need is to get access to one property, that is required for ordering and we can define very special constructor for our Ord type, that gets special accessor callback that returns property value, and Ord object for that returned value, and returns new Ord without changing type of collection item.

const propOrd = <T, A>(acc: (i: T) => A, ord: Ord<A>): Ord<T> => fromCompare((a, b) => ord.compare(acc(a), acc(b)));

// default string Ord
const ordString = fromCompare<string>(compare);

const ordUserMonoid = getOrdMonoid<User>();

const ordUserName = propOrd((o: User) => o.name, ordString);
const ordUserAge = propOrd((user: User) => user.age, ordNum);

const ordUserNameAge = ordUserMonoid.concat(ordUserName, ordUserAge);

From now, all we must do is build ORDs and concat between them in required comparison sequence.

Now we have almost complete solution. But in some cases we need to invert sort order from ascending to descending and vice versa. Let's define reverse function!

function reverseOrd<A>(ord: Ord<A>): Ord<A> {
  return fromCompare((a, b) => ord.compare(b, a));
}

const ordUserSalaryNameAge = ordUserMonoid.concatAll([
  reverseOrd(propOrd((user: User) => user.salary, ordNum)),
  ordUserName, 
  ordUserAge,
]);

Now we complete all challenges! We can simply define most complex sorting, we can even sort by nested proprties - just define accessor and create Ord object - easy as one two three! We can even do a tricky things like sorting array of arrays by sum of numbers in this nested arrays and moreover we can easy achieve this with Monoids! And even more - we can define utility functions like min/max for user defined objects in simple reusable way.

const Sum: Monoid<number> = {
  empty: 0,
  concat: (a, b) => a + b,
  concatAll(arr) {
    return arr.reduce(this.concat, this.empty);
  }
}

const sortListSum = propOrd(Sum.concatAll, ordNum);

[[5,4], [1,2,3], [3, 3]].sort(sortListSum.compare);

function min<T>(ord: Ord<T>, left: T, right: T) {
  return ord.compare(left, right) === GT ? right : left;
}

function max<T>(ord: Ord<T>, left: T, right: T) {
  return ord.compare(left, right) === GT ? left : right;
}

Remove abstraction overhead.

This aproach is so general and now we can write literally boilerplate code for sorting(Ordering!) tasks, but it is still not ideal - so many rules and abstractions for such simple issue - in most cases you don't need such complicated way to solve multiple condition sort problem, even you need to write this functions one time and reuse them. We will try to simplify our solution to minimize code and complexity. We will remove Monoid, Ord, and leave some key types and principles.

type EQ = 0;
type GT = 1;
type LT = -1;
type Ordering = EQ | GT | LT;

const EQ: EQ = 0;
const GT: GT = 1;
const LT: LT = -1;

interface Comparator<T> {
  (a: T, b: T): Ordering;
}

// default compare function for primitive types
const compare = <T>(a: T, b: T): Ordering => a > b ? GT : a < b ? LT : EQ;

// propOrd without Ord
const compareProp = <T, A>(
  comparator: Comparator<A>,
  accessor: (a: T) => A
): Comparator<T> => (a, b) => comparator(accessor(a), accessor(b));

// for reverse we just need to swap arguments
const reverse = <T>(comparator: Comparator<T>): Comparator<T> => (a, b) => comparator(b, a);

const concatAll = <T>(list: Comparator<T>[]): Comparator<T> => {
  return list.reduce(
    (init, next) => (a, b) => {
      const ord1 = init(a, b);
      return ord1 !== EQ ? ord1 : next(a, b);
    },
    () => EQ
  );
};

Note that concatAll function now inherits MonoidOrd behaviour just in one line plus we benefit from short circuiting concatenation.

Now we have just couple functions that can be composed in ramda/lodash style but we don't loose any functionality comparing to previous solution.

Conclusion.

Once we understand principles of functional data types, we can implement elegant generalized solution for our problem and get more declarative code in our apps, but it is not only way to use that data types:

If you interested in functional programming there is great library, written by Giulio Canti - https://github.com/gcanti/fp-ts , that allready implement similar data types in same maner and even much more from functional languages world, moreover, there is big ecosystem based on fp-ts library - most exiting members are: io-ts - runtime data validation https://github.com/gcanti/io-ts, fault-tolerant and type safe data fetching by Yuriy Bogomolov - https://github.com/YBogomolov/fetcher-ts, functional type for fetched data by devexperts - https://github.com/devexperts/remote-data-ts and much more!

Live example

https://codesandbox.io/s/multiple-condition-sorting-47k92z