Composing sort rules using fp-ts

There is a list of products waiting to be shown on a screen, and someone has to decide the order in which they appear. It is rarely just the one rule. Customers expect the categories on the page in alphabetical order, the products inside each category to follow the same alphabet, and any item that happens to be out of stock to be quietly moved to the back of its category. Three small rules, together, describing one ranking.

Written by hand the ranking works, faithfully, the first time. Six months later the rules have grown into a function full of ternaries and if/else branches, half of them duplicated on the next screen over. The intent has not changed at all; it has only been pressed into a single line until each of the three small voices is talking over the others. The Ord module from fp-ts exists for exactly that situation: it lets each rule say its piece in its own sentence, and lets you fold the sentences together into a single ranking when the time comes.

Modeling the domain

The shop has two entities, products and categories, with a one-to-one relationship between them. Two interfaces are enough to pin them down, with the concrete details left for another day:

// src/category.ts

/**
 * a tag on the shelf that products belong to
 */
export interface Category {
  readonly id: string
  readonly name: string
}

// src/product.ts
import { Category } from './category'

/**
 * an item on the shelf, with its category and a quiet flag for being out of stock
 */
export interface Product {
  readonly id: string
  readonly name: string
  readonly category: Category
  readonly unavailable: boolean
}

An ordering on a string

Take the rules one at a time. The first asks for categories to be ordered alphabetically by name. Read it slowly and the rule reveals itself: a category should be ordered however its name is, and a name is a string, and there is already an ordering on strings the world has long agreed on. Here is what the fp-ts string module hands us:

import * as S from 'fp-ts/string'

S.Ord.compare('a', 'a') //  0
S.Ord.compare('a', 'b') // -1
S.Ord.compare('b', 'a') //  1

That little Ord knows how to compare two strings, and its answer is the most modest one possible: a single number, negative if the first is smaller, positive if the second is, zero if neither owes the other anything. Every richer ordering we are going to write begins with one of these tiny sentences.

Pointing the ordering at a field

A category is not a string, but it has one. To hand the same little sentence to a category, we point it at the field it should read. The fp-ts Ord module provides contramap for exactly that:

// src/category.ts
import * as O from 'fp-ts/Ord'
import * as S from 'fp-ts/string'
import { pipe } from 'fp-ts/function'

/**
 * categories are ordered alphabetically by their name
 */
export const Ord: O.Ord<Category> = pipe(
  S.Ord,
  O.contramap((category: Category) => category.name),
)

The string ordering has not changed at all. We have simply turned it to face the field it should read, and the result is an ordering on categories that knows nothing of strings beyond the one it is asked to compare. Products follow the same path. There are two ways into a product's ranking, by the name and by the category, and each is a single sentence about a single field:

// src/product.ts
import * as O from 'fp-ts/Ord'
import * as S from 'fp-ts/string'
import { pipe } from 'fp-ts/function'
import * as Category from './category'

/**
 * within a category, products are ordered alphabetically by name
 */
export const byName: O.Ord<Product> = pipe(
  S.Ord,
  O.contramap((product: Product) => product.name),
)

/**
 * a product inherits the ordering of the category it belongs to
 */
export const byCategory: O.Ord<Product> = pipe(
  Category.Ord,
  O.contramap((product: Product) => product.category),
)

Linger on byCategory for a moment. It does not rebuild the alphabet on category names, even though in the end that is what it does. It borrows the ordering that already lives next door, Category.Ord, and points it at the category nested inside the product. The rule the catalog page uses to lay out the category list is the very same rule the product grid uses to group by category, and a change to one moves the other in step.

Combining the rules

Two orderings, then, but not yet a ranking. We still need a way to say: order first by category, then by name within each category, and leave room for any rule that may arrive later to slot in as a new line. That little word, then, is itself a Monoid. The name sounds grander than the thing is; think of a Monoid as a pressure cooker, an honest tool that takes a list of pieces and patiently folds them into one. O.getMonoid is the one that turns a list of orderings into a single ordering, falling through to the next rule the moment the previous one was indifferent:

// src/product.ts
import * as M from 'fp-ts/Monoid'

/**
 * the ranking customers see: category first, alphabet within
 */
export const Ord: O.Ord<Product> = M.concatAll(O.getMonoid<Product>())([
  byCategory,
  byName,
])

The order of the rules in the list is exactly the order of precedence. Read it top to bottom and it tells you the whole policy: first by category, then by name. A rule earlier in the list outranks anything below it. A change of mind about which rule wins is a swap of two lines, no more.

A new rule arrives

Then a new requirement lands. Out-of-stock items, the merchandising team agrees, should be pushed to the back of their category so the goods customers can actually buy come first. There is already an unavailable flag on the product, and there is already an ordering on booleans (false before true), so the rule writes itself in one more small sentence:

// src/product.ts
import * as B from 'fp-ts/boolean'

/**
 * available items come before unavailable ones
 */
export const byAvailability: O.Ord<Product> = pipe(
  B.Ord,
  O.contramap((product: Product) => product.unavailable),
)

Adding it to the ranking costs exactly one more line, slotted in where it belongs: after the category has been chosen, before the alphabet within it settles the rest.

// src/product.ts

/**
 * the ranking, with availability between category and name
 */
export const Ord: O.Ord<Product> = M.concatAll(O.getMonoid<Product>())([
  byCategory,
  byAvailability,
  byName,
])

And the call site never has to change. Whichever rules happen to live in that list, sorting a list of products is a single line that says only what it means:

// src/catalog.ts
import { pipe } from 'fp-ts/function'
import * as RA from 'fp-ts/ReadonlyArray'
import * as Product from './product'

const ranked = pipe(
  products,
  RA.sort(Product.Ord),
)

A rule retires

A week later, the customers came back unhappy. The unavailable items, they said, were burying the products they had actually wanted to see. The rule had to come out. Notice what was needed to retire it: not surgery, not a refactor, not even a deletion. One comment on one line:

// src/product.ts

/**
 * the same ranking, with availability quietly suspended
 */
export const Ord: O.Ord<Product> = M.concatAll(O.getMonoid<Product>())([
  byCategory,
  // byAvailability,
  byName,
])

And on the Monday after, when the merchandising team has thought again and the rule is wanted back, the comment slips off and the line slips in. The same shape that made the rules legible has quietly turned them into switches you can throw one at a time.

Conclusion

What composition has given us here is small and ordinary, but worth saying plainly. Each rule names a single thing about a single field, lives in the module that owns it, and combines with the others by being added to a list. A swap of two lines reorders the precedence. A comment retires a rule. The catalog page and the product grid share the rule for category ordering, and cannot drift out of step. The next ranking that comes our way, by stock level, by price, by relevance, by anything at all, is one more small sentence and one more line in the list, and the pressure cooker does the rest.