Getting started with fp-ts: Ord Giulio Canti github logo Mar 13Updated on Apr 09, 2019・3 min read

Part of "Getting started with fp-ts" series

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 'fp-ts/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 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 `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 `fp-ts/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 '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 }
``````

Next post Semigroup

Part of "Getting started with fp-ts" series

DISCUSS (7) 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?

Yes, `Ord`s 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' } ]
*/
``````

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 ?

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.

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 fp-ts for a while but it'd always seemed to me your target audience were more of advanced Haskell/Purescript users.

Classic DEV Post from Aug 29 '18

4 Things Developers Take for Granted That Used to Be Really Hard Join dev.to  