Getting started with fpts: Ord
Giulio Canti Mar 13 Updated on Apr 09, 2019 ・3 min read
In the previous blog post about Setoids 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 { Setoid } from 'fpts/lib/Setoid'
type Ordering = 1  0  1
interface Ord<A> extends Setoid<A> {
readonly compare: (x: A, y: A) => Ordering
}
We say that

x < y
if and only ifcompare(x, y)
is equal to1

x
is equal toy
if and only ifcompare(x, y)
is equal to0

x > y
if and only ifcompare(x, y)
is equal to1
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:

Reflexivity:
compare(x, x) <= 0
, for allx
inA

Antisymmetry: if
compare(x, y) <= 0
andcompare(y, x) <= 0
thenx
is equal toy
, for allx
,y
inA

Transitivity: if
compare(x, y) <= 0
andcompare(y, z) <= 0
thencompare(x, z) <= 0
, for allx
,y
,z
inA
Additionally compare
must comply with Setoid
'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 fpts/lib/Ord
exports an handy fromCompare
helper which allows you to define an Ord
instance by simply specifying a compare
function
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
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 'fpts/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 }
Next post Semigroup
Great article mate! Very insightful and easy to read. I've been trying to write more functional JS code lately so I've been using currying, pure functions, transducers and such but I find it very hard to wrap my head around category theory. Will you consider including them in your next posts?
That's the plan, yes
Really looking forward to see more articles from this series.
Had my eye on fpts for a while but it'd always seemed to me your target audience were more of advanced Haskell/Purescript users.