# Fantas, Eel, and Specification 3.5: Ord

Honestly, at this rate, the spec is going to grow faster than this blog series… We interrupt our usual schedule to introduce Fantasy Land’s newest member: let’s welcome `Ord`! Spoiler alert: if you’ve been following this series, this is going to be a pretty easy one.

`Ord` types are types with a total ordering. That means that, given any two values of a given `Ord` type, you can determine whether one be greater than the other. To do this, we actually only need one method. Given that all `Ord` types must also be `Setoid` types, it could actually have been any of the comparison operators (`>`, `>=`, `<`, `<=`; think about why any of these would have worked), but the spec settled on `<=` (less-than-or-equal), which it refers to as `lte`:

``````lte :: Ord a => a ~> a -> Boolean
``````

I’m sure that, for most of you, this isn’t your first type signature, so I’ll leave that link for anyone who may not have seen it. It’s almost identical to `Setoid`’s `equals`, though; the only difference is that, this time, we return a boolean to indicate whether `this <= that`, rather than `this == that`. Using only `lte` and `equals` (because every `Ord` is a `Setoid`), we can derive all the things we might want:

``````// Greater than. The OPPOSITE of lte.
// gt :: Ord a => a -> a -> Boolean
const gt = function (x, y) {
return !lte(x, y)
}

// Greater than or equal.
// gte :: Ord a => a -> a -> Boolean
const gte = function (x, y) {
return gt(x, y) || x.equals(y)
}

// Less than. The OPPOSITE of gte!
// lt :: Ord a => a -> a -> Boolean
const lt = function (x, y) {
return !gte(x, y)
}

// And we already have lte!
// lte :: Ord a => a -> a -> Boolean
const lte = function (x, y) {
return x.lte(y)
}
``````

That is how, using `equals` and one of those four functions, we have enough to derive the other three. This is really neat, and `Ord` continues to please:

``````// Recursive Ord definition for List!
// lte :: Ord a => [a] ~> [a] -> Boolean
List.prototype.lte = function (that) {
return this.cata({

Nil: () => false
}),

Nil: () => true
})
}

// Just for demo - forgive me!
Number.prototype.equals =
function (that) { return this == that }

Number.prototype.lte =
function (that) { return this <= that }

Cons(1, Cons(2, Nil)).lte(Cons(1, Nil)) // false
Cons(1, Nil).lte(Cons(1, Cons(2, Nil))) // true
``````

Oh yeah, it composes; were you expecting anything less? Of course, we can write `Ord` instances for container types with inner `Ord` types, just as we did for `Setoid`, `Monoid`, and so on. We just nest as we want. Do we want to compare `Tuple`s of `List`s of `Maybe`s of some custom type of ours? No problem! `Ord` takes care of everything, just as `Setoid` did for equivalence.

Anyway, we got a bit carried away! Let’s talk about laws.

``````// Given any two values of an Ord type...

a.lte(b) || b.lte(a) === true // Totality

a.lte(b) && b.lte(a)
=== a.equals(b) // Antisymmetry

a.lte(b) && b.lte(c)
=== a.lte(c) // Transitivity
``````

Totality might seem obvious (`a <= b` or `b <= a`, surely?) when we’re talking about integers, for example, but this isn’t always so easy. There are examples of types that only have partial order, which means that there are certain pairs of values that are incomparable. Because of this, they unfortunately don’t make it into the `Ord` club!

A good example is the semilattice, if you’re interested, but we won’t spend any time discussing this further. Feel free to tweet me if you want to talk through it, though!

Antisymmetry, at least to me, seems like a big word for something reasonably obvious. If you compare any `a` and `b` values within the type, then find `a.lte(b)` and `b.lte(a)`, well, they can’t both be less than the other, right? The only possible explanation is that `a == b`!

Finally, transitivity, in practice, says that all the values in your type could in theory be arranged into a fixed, ordered list. No special cases! Typically, though, you’d be doing well to find an implementation that satisfies the other two laws but not this one!

That’s really all there is, in terms of theory. Significantly less frightening than `Contravariant` functors, right? It’s really just a way to define, for your type, what it means for one thing to be “bigger” than another.

Want some exercises? Why not write some of your favourite sorting algorithms (like bubble, merge, and quicksort) to work on any `Ord`-implementing structure*? Maybe write a more efficient version of our `Setoid`-using `Set` type by using an ordered list to hold the inner elements? There are plenty of opportunities!

Of course, if you don’t want to relive your technical interview nightmares, remember that `Ord` is just as useful for ordering search results on a web page. The Fantasy Land structures are just a bunch of design patterns that are written with composition (and discipline!) in mind.

Regardless, I hope you enjoyed this surprise addition to the series. Normal service will resume, and we’ll be discovering `Apply` and `Applicative` tomorrow, right on schedule. It’s also a good time to mention that I’ve been putting together a collection of Fantasy Land structure examples to go along with this series! I have quite a lot of catching up to do, but I’ll get there. I’m implementing all the examples and exercises that I mention in the articles, as well as other structures that may be interesting. Naturally, I would be honoured if you wanted to contribute any examples you’ve found helpful, or even just add a couple comments and helpful tips to what’s already there!

Anyway, that’s all from me! See you tomorrow, everyone - enjoy the rest of your weekends, and take care ♥

* If you decide to do this, this is a great candidate for an npm package. Seriously, I will use this - let me know when you publish!