Interface Ord<T>

An interface that provides evidence of a total order.

Remarks

Properties

In addition to being equivalence relations, implementors of Ord must define a method of comparison such that an implementation is also:

• reflexive: le(x, x);
• antisymmetric: le(x, y) and le(y, x) implies eq(x, y);
• transitive: le(x, y) and le(y, z) implies le(x, z); and
• comparable: le(x, y) or le(y, x)

for all values x, y, and z.

Implementing Ord

Ord extends Eq, and therefore requires an implementation for both [Eq.eq] and [Ord.cmp].

The most common implementation strategies are writing classes and patching existing prototypes. Implementation is implicit and does not require an implements clause. TypeScript uses structural subtyping to determine whether a value implements Ord.

Conditional implementation

Working with generic types requires additional consideration: in some cases, a generic type implements Ord only when one or more of its generic parameters implement Ord; in these cases, we must require an Ord implementation from the parameter(s). In other cases, there are no such requirements.

Deriving [Eq.eq] from [Ord.cmp]

Implementing [Eq.eq] for a type that has already implemented [Ord.cmp] is trivial: simply check whether the result of comparing two instances is the Equal variant of Ordering. Sometimes, determining equality can be done in a more efficient manner without relying on [Ord.cmp].

Writing classes

Classes and objects can implement Ord. This strategy works best for types that:

• are already modeled using classes or objects.
• provide direct access to their implementation.
• have a single, specific behavior as a total order.

Additionally, classes can easily wrap existing types to provide a variety of Ord implementations. These "helper" classes are useful for types that:

• have more than one behavior as a total order, or already have a default implementation for Ord but can have alternative implementations.
• do not provide access to their implementation, and where patching the implementation is undesireable.

Patching existing prototypes

Existing types can be patched to implement Ord. This strategy works well for types that:

• are built-in or imported from external modules.
• do not provide access to their implementation.
• have a single, specific behavior as a total order, or where the programmer wishes to implement a default behavior.

Patching a type in TypeScript requires two steps:

1. an augmentation for a module or the global scope that patches the type-level representation; and
2. a concrete implementation for [Ord.cmp] and [Eq.eq].

The concrete implementation logic is similar to writing a method body for a class or object, and the same practices apply for requiring generic parameters to implement Ord.

Example

Non-generic implementation

Consider a Book type that determines ordering by comparing ISBNs:

import { Eq, Ord, Ordering } from "@neotype/prelude/cmp.js";

enum BookFormat { HARD_BACK, PAPER_BACK, DIGITAL }

class Book {
    constructor(readonly isbn: number, readonly fmt: BookFormat) {}

    [Eq.eq](that: Book): boolean {
        // An exercise for the reader...
    }

    [Ord.cmp](that: Book): Ordering {
        return Ordering.fromNumber(this.isbn - that.isbn);
    }
}
Copy

If desired, we can also consider the book format when ordering two books:

import { Eq, Ord, Ordering } from "@neotype/prelude/cmp.js";

enum BookFormat { HARD_BACK, PAPER_BACK, DIGITAL }

class Book {
    constructor(readonly isbn: number, readonly fmt: BookFormat) {}

    [Eq.eq](that: Book): boolean {
        // An exercise for the reader...
    }

    [Ord.cmp](that: Book): Ordering {
        return cmb(
            Ordering.fromNumber(this.isbn - that.isbn),
            Ordering.fromNumber(this.fmt - that.fmt),
        );
    }
}
Copy

In this example, books are ordered first by their ISBN, and then by their format. Notice how the semigroup behavior of Ordering along with the cmb function is used here to combine two Ordering.

Example

Generic implementation with no Ord requirements

Consider a type that orders arrays by comparing their lengths:

import { Eq, Ord, Ordering } from "@neotype/prelude/cmp.js";

class Len<out T> {
    constructor(readonly val: T[]) {}

    [Eq.eq](that: Len<T>): boolean {
        // An exercise for the reader...
    }

    [Ord.cmp](that: Len<T>): Ordering {
        return Ordering.fromNumber(this.val.length - that.val.length);
    }
}
Copy

Notice how Len is generic, but there are no special requirements for implementing [Ord.cmp].

Example

Generic implementation with an Ord requirement

Consider a type that orders arrays by comparing their elements lexicographically, which requires that the elements implement Ord:

import { Eq, Ord, Ordering, icmp } from "@neotype/prelude/cmp.js";

class Arr<out T> {
    constructor(readonly val: T[]) {}

    [Eq.eq]<T extends Eq<T>>(this: Arr<T>, that: Arr<T>): boolean {
        // An exercise for the reader...
    }

    [Ord.cmp]<T extends Ord<T>>(this: Arr<T>, that: Arr<T>): Ordering {
        return icmp(this.val, that.val);
    }
}
Copy

Notice the extra syntax when implementing [Ord.cmp]. We introduce a method-scoped generic parameter T and require that it has an Ord implementation by writing T extends Ord<T> (the name T is arbitrary).

Then, we require that this and that are Arr<T> where T extends Ord<T>. This allows us to use icmp to implement our desired behavior.

Example

Generic implementation with multiple Ord requirements

Consider a Pair type that orders two distinct values lexicographically, which requires that each value is an implementor of Ord:

import { cmb } from "@neotype/prelude/cmb.js";
import { Eq, Ord, Ordering, cmp } from "@neotype/prelude/cmp.js";

class Pair<out A, out B> {
    constructor(readonly fst: A, readonly snd: B) {}

    [Eq.eq]<A extends Eq<A>, B extends Eq<B>>(
        this: Pair<A, B>,
        that: Pair<A, B>,
    ): boolean {
        // An exercise for the reader...
    }

    [Ord.cmp]<A exends Ord<A>, B extends Ord<B>>(
        this: Pair<A, B>,
        that: Pair<A, B>,
    ): Ordering {
        return cmb(cmp(this.fst, that.fst), cmp(this.snd, that.snd));
    }
}
Copy

The syntax is similar to the Arr implementation above. Notice there are now two method-scoped generic parameters that are each required to implement Ord.

Example

Non-generic augmentation

Consider a module augmentation for an externally defined Book type:

import { Eq, Ord, Ordering } from "@neotype/prelude/cmp.js";
import { Book } from "path_to/book.js";

declare module "path_to/book.js" {
    interface Book {
        [Eq.eq](that: Book): boolean
        [Ord.cmp](that: Book): Ordering
    }
}

Book.prototype[Eq.eq] = function (that: Book): boolean {
    // An exercise for the reader...
};

Book.prototype[Ord.cmp] = function (that: Book): Ordering {
    return Ordering.fromNumber(this.isbn - that.isbn);
};
Copy

Example

Generic augmentation

Consider a global augmentation for the Array prototype:

import { Eq, Ord, Ordering, icmp } from "@neotype/prelude/cmp.js";

declare global {
    interface Array<T> {
        [Eq.eq]<T extends Eq<T>>(this: T[], that: T[]): boolean
        [Ord.cmp]<T extends Ord<T>>(this: T[], that: T[]): Ordering
    }
}

Array.prototype[Eq.eq] = function <T extends Eq<T>>(
    this: T[],
    that: T[],
): boolean {
    // An exercise for the reader...
}

Array.prototype[Ord.cmp] = function <T extends Ord<T>>(
    this: T[],
    that: T[],
): boolean {
    return icmp(this, that);
};
Copy