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 ifcompare(x, y)
is equal to-1
-
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 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
Top comments (9)
That's the plan, yes
Is there a way to combine Ords that compare individual properties of an object, for example:
so that ordWeightLabel would order first by weight, and then by label where weights are equal?
Yes,
Ord
s form a SemigroupHi, 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 ?
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.
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.
Great article. Just a minor typo I think:
Didn't you mean
==
instead of<=
? Otherwise thefromCompare
method would not work correctly.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 outIt mentions a
Setoid
which I believe was renamed toEq
.