DEV Community

loading...

Getting started with fp-ts: Ord

Giulio Canti
Updated on ・3 min read

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/lib/Eq'

type Ordering = -1 | 0 | 1

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

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)
}
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Indeed the module fp-ts/lib/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/lib/Ord'

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

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
Enter fullscreen mode Exit fullscreen mode

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
}
Enter fullscreen mode Exit fullscreen mode

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))
Enter fullscreen mode Exit fullscreen mode

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/lib/Ord'

const byAge: Ord<User> = contramap((user: User) => user.age)(ordNumber)
Enter fullscreen mode Exit fullscreen mode

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 }
Enter fullscreen mode Exit fullscreen mode

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/lib/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 }
Enter fullscreen mode Exit fullscreen mode

Next post Semigroup

Discussion (10)

Collapse
gcanti profile image
Giulio Canti Author

That's the plan, yes

Collapse
jollytoad profile image
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?

Collapse
gcanti profile image
Giulio Canti Author

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' } ]
*/
Collapse
belgac_2 profile image
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 ?

Collapse
jollytoad profile image
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.

Collapse
veevidify profile image
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.

Collapse
andrasferenczi profile image
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.

Collapse
gcanti profile image
Giulio Canti Author

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

Collapse
eoksni profile image
Dmitry Mazurok

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