Getting started with fp-ts: Ord

In the previous blog post about Eq we were dealing with the concept of equality. In this blog post we are going to deal with the concept of order.

A type class Ord, intended to contain types that admit a total ordering, is declared in the following way

import { Eq } from 'fp-ts/Eq'

type Ordering = -1 | 0 | 1

interface Ord<A> extends Eq<A> {
  readonly compare: (x: A, y: A) => Ordering
}

We say that

• x < y if and only if compare(x, y) is equal to -1
• x is equal to y if and only if compare(x, y) is equal to 0
• x > y if and only if compare(x, y) is equal to 1

As a consequence we can say that x <= y if and only if compare(x, y) <= 0

As an example here's the instance of Ord for the type number

const ordNumber: Ord<number> = {
  equals: (x, y) => x === y,
  compare: (x, y) => (x < y ? -1 : x > y ? 1 : 0)
}

Instances must satisfy the following laws:

1. Reflexivity: compare(x, x) === 0, for all x in A
2. Antisymmetry: if compare(x, y) <= 0 and compare(y, x) <= 0 then x is equal to y, for all x, y in A
3. Transitivity: if compare(x, y) <= 0 and compare(y, z) <= 0 then compare(x, z) <= 0, for all x, y, z in A

Additionally compare must comply with Eq's equals:

compare(x, y) === 0 if and only if equals(x, y) === true, for all x, y in A

Note. A lawful equals can be derived from compare in the following way

equals: (x, y) => compare(x, y) === 0

Indeed the module fp-ts/Ord exports an handy fromCompare helper which allows you to define an Ord instance by simply specifying a compare function

import { Ord, fromCompare } from 'fp-ts/Ord'

const ordNumber: Ord<number> = fromCompare((x, y) => (x < y ? -1 : x > y ? 1 : 0))

A programmer could then define a function min (which takes the minimum of two values) in the following way

function min<A>(O: Ord<A>): (x: A, y: A) => A {
  return (x, y) => (O.compare(x, y) === 1 ? y : x)
}

min(ordNumber)(2, 1) // 1

Totality might seem obvious (i.e. either x <= y or y <= x) when we're talking about numbers, but this isn't always the case. Let's consider a more complex type

type User = {
  name: string
  age: number
}

How can we define an Ord<User>?

Well it really depends, but a possible choice is to sort users by their age

const byAge: Ord<User> = fromCompare((x, y) => ordNumber.compare(x.age, y.age))

We can avoid some boilerplate by using the contramap combinator: given an instance of Ord for A and a function from B to A, we can derive an instance of Ord for B

import { contramap } from 'fp-ts/Ord'

const byAge: Ord<User> = contramap((user: User) => user.age)(ordNumber)

Now we can pick the younger of two users using min

const getYounger = min(byAge)

getYounger({ name: 'Guido', age: 48 }, { name: 'Giulio', age: 45 }) // { name: 'Giulio', age: 45 }

What if we want to pick the older instead? We'd need to "reverse the order", or more technically speaking, get the dual order.

Fortunately there's another exported combinator for this

import { getDualOrd } from 'fp-ts/Ord'

function max<A>(O: Ord<A>): (x: A, y: A) => A {
  return min(getDualOrd(O))
}

const getOlder = max(byAge)

getOlder({ name: 'Guido', age: 48 }, { name: 'Giulio', age: 45 }) // { name: 'Guido', age: 48 }

Next post Semigroup

Comments

[andrasferenczi]

Great article. Just a minor typo I think:

Instances must satisfy the following laws:

Reflexivity: compare(x, x) <= 0, for all x in A

Didn't you mean == instead of <= ? Otherwise the fromCompare method would not work correctly.

[Giulio Canti]

It's not a typo, please note that Reflexivity + Antisymmetry imply compare(x, x) === 0, for all x in A. However I'll restate the Reflexivity property to make it clearer, thanks for pointing out

[Dmitry Mazurok]

It mentions a Setoid which I believe was renamed to Eq.

[Mark Gibson]

Is there a way to combine Ords that compare individual properties of an object, for example:

const ordWeight: Ord<Weighted> = contramap((a: Weighted) => a.weight, ordNumber)
const ordLabel: Ord<Labelled> = contramap((a: Labelled) => a.label, ordString)

const ordWeightLabel: Ord<Weighted & Labelled> = combinedOrd(ordWeight, ordLabel)

so that ordWeightLabel would order first by weight, and then by label where weights are equal?

[Giulio Canti]

Yes, Ords form a Semigroup

import { contramap, getSemigroup, Ord, ordNumber, ordString } from 'fp-ts/lib/Ord'

interface Weighted {
  weight: number
}

interface Labelled {
  label: string
}

const ordWeighted: Ord<Weighted> = contramap((a: Weighted) => a.weight, ordNumber)

const ordLabelled: Ord<Labelled> = contramap((a: Labelled) => a.label, ordString)

interface WeightLabel extends Weighted, Labelled {}

const S = getSemigroup<WeightLabel>()

const ordWeightLabel: Ord<WeightLabel> = S.concat(ordWeighted, ordLabelled)

//
// Usage
//

import { sort } from 'fp-ts/lib/Array'

const xs: Array<WeightLabel> = [
  { weight: 3, label: 'b' },
  { weight: 1, label: 'c' },
  { weight: 3, label: 'a' }
]

console.log(sort(ordWeightLabel)(xs))
/*
[ { weight: 1, label: 'c' },
  { weight: 3, label: 'a' },
  { weight: 3, label: 'b' } ]
*/

[Hans Scheuren]

Hi, your library and articles finally made me love typescript. Thanks a lot. I have a question : would an Ord that always returns 0 be enough to transform the semigroup from get Semigroup in a monoid ?

[Mark Gibson]

Oh, excellent, thank you very much. I suspected it had something to do with Semigroups, but hadn't managed to make that leap in understanding them yet.

[V]

Really looking forward to see more articles from this series.
Had my eye on fp-ts for a while but it'd always seemed to me your target audience were more of advanced Haskell/Purescript users.

[Giulio Canti]

That's the plan, yes