#2.5. Comparison traits

The rok::core::cmp module is the trait family that defines comparison between values. Not only the ==, !=, <, >, <=, >= operators but also hashing, sorting and pattern matching dispatch through the traits of this chapter.

rok splits comparison into a 4-trait hierarchy (PartialEq / Eq / PartialOrd / Ord) plus a separate Hash trait. The split satisfies two practical requirements at once: NaN handling for IEEE 754 floating-point, and guaranteed hash consistency.

#2.5.1. The 4-trait hierarchy - why partial is needed

The hierarchy can be described from two viewpoints at once.

Set viewpoint - A ⊃ B means "the set of types satisfying A contains the set of types satisfying B". A is more general; B is more specific.

PartialEq  ⊃  Eq           // set of PartialEq types ⊇ set of Eq types
PartialOrd ⊃  Ord          //  (every Eq is PartialEq, but not vice versa)
PartialEq  ⊃  PartialOrd

Implication viewpoint (supertrait) - B ⇒ A means "implementing B automatically requires A"; in rok code it is written trait B: A. A is then a supertrait of B.

trait Eq: PartialEq { ... }                    // PartialEq is a supertrait of Eq
trait PartialOrd: PartialEq { ... }            // PartialEq is a supertrait of PartialOrd
trait Ord: PartialOrd + Eq { ... }             // PartialOrd and Eq are supertraits of Ord

The two viewpoints express exactly the same fact from different angles. If B ⇒ A, every type that is B is also A, so A ⊃ B follows. In the set viewpoint, the supertrait is "the larger side".

The Hash trait sits on a line separate from the hierarchy above.

Eq ⊃ Hash         // only some Eq types are Hash - Hash promises consistency with Eq

Partial is split out because of NaN in IEEE 754 floating point.

let a: f64 = 0.0 / 0.0;       // NaN
let b: f64 = 0.0 / 0.0;       // NaN
a == b;                       //→ false (NaN != NaN by IEEE 754)
a < b;                        //→ false
a > b;                        //→ false
a <= b;                       //→ false

NaN is not equal even to itself. This violates reflexivity: a == a is not guaranteed. Trait implementations therefore split by type: f32 and f64 implement only PartialEq, PartialOrd, while i32, bool, str and the like implement up to Eq, Ord and satisfy a total order.

This split keeps Hash's consistency promise and the total ordering guarantee safe in Hash, HashMap, BTreeMap and sort algorithms.

#2.5.2. PartialEq - partial equality (==, !=)

Partial equality is defined as follows.

#[lang("eq_trait")]
trait PartialEq<Rhs = Self> {
    #[infix("==")]
    #[infix("≡")]    // Unicode alias
    fn eq(self, rhs: Rhs) -> bool;

    #[infix("!=")]
    #[infix("≠")]    // Unicode alias
    fn ne(self, rhs: Rhs) -> bool {
        !self.eq(rhs)                // default impl
    }
}

The promises of PartialEq are symmetry - a == b and b == a are equivalent - and transitivity - if a == b and b == c hold, a == c holds. Reflexivity (a == a) is not guaranteed, because of IEEE 754 NaN.

#Default ne

ne is implemented by default as !self.eq(rhs). A user may implement it separately, e.g. for performance.

#Examples

let r1 = 5i32 == 5i32;     //→ true
let r2 = "hi" != "hello";  //→ true

let nan: f64 = f64::NAN;
let r3 = nan == nan;       //→ false  (PartialEq is partial)

#2.5.3. Eq - total equality

Total equality is defined as a marker trait.

trait Eq: PartialEq<Self> {
    // marker trait - no additional methods
}

Eq is a marker trait: it adds no methods, only the reflexivity promise.

The promise Eq adds is reflexivity: a == a is always true. HashMap keys, BTreeMap keys and sort algorithms work correctly only with this promise.

The impl policy is as follows. All integer / boolean / character / string types - i32, i64, u8..u64, bool, char, c_char, str, etc. - implement Eq. Floating-point types and sum types containing them - f32, f64, f64 | none, etc. - do not implement Eq. #[derive(Eq)] on a user struct or enum is possible only when every field is Eq.

let n: i32 = 42;
n == n;       //→ true (guaranteed by Eq)

#2.5.4. PartialOrd - partial order (<, >, <=, >=)

The partial order trait defines the comparison operators.

#[lang("cmp_trait")]
trait PartialOrd<Rhs = Self>: PartialEq<Rhs> {
    #[infix("<")]
    fn lt(self, rhs: Rhs) -> bool;

    #[infix(">")]
    fn gt(self, rhs: Rhs) -> bool;

    #[infix("<=")]
    #[infix("≤")]    // Unicode alias
    fn le(self, rhs: Rhs) -> bool;

    #[infix(">=")]
    #[infix("≥")]    // Unicode alias
    fn ge(self, rhs: Rhs) -> bool;

    fn partial_cmp(self, rhs: Rhs) -> Ordering | none {
        // default impl - combination of lt/gt/eq
        if self.eq(rhs) { Ordering::Equal }
        else if self.lt(rhs) { Ordering::Less }
        else if self.gt(rhs) { Ordering::Greater }
        else { none }                     // NaN vs NaN etc. - incomparable
    }
}

The promises of this trait: antisymmetry - if a < b then !(b < a) - and transitivity - for defined comparisons, if a < b and b < c then a < c. Trichotomy holds only partially: the order between two values is not always defined, and incomparable values such as NaN exist.

partial_cmp is a provided method (with a default implementation) and returns Ordering | none. It is none when the values are incomparable (NaN, etc.).

#The Ordering type

The result of a 3-way comparison is represented by this enum.

enum Ordering {
    Less,
    Equal,
    Greater,
}

Ord::cmp returns Ordering directly. Ordering implements Debug (Less / Equal / Greater).

#Comparison chaining rejected

As defined by refs-lang 3.2.5, chains of non-associative traits are rejected.

a < b < c;        // compile error - non-associative (none) trait chain rejected

Use an explicit AND instead.

a < b && b < c;   // explicit AND

#2.5.5. Ord - total order

The total order trait is defined as follows.

#[lang("ord_trait")]
trait Ord: Eq + PartialOrd<Self> {
    fn cmp(self, rhs: Self) -> Ordering;

    // default - two values with Ord are always comparable
    fn min(self, rhs: Self) -> Self {
        if self.le(rhs) { self } else { rhs }
    }

    fn max(self, rhs: Self) -> Self {
        if self.ge(rhs) { self } else { rhs }
    }

    fn clamp(self, low: Self, high: Self) -> Self {
        if self.lt(low) { low }
        else if self.gt(high) { high }
        else { self }
    }
}

The promise Ord adds is totality: the order between any two values is defined as one of Less, Equal, Greater. partial_cmp therefore never returns none; it always returns an Ordering value.

Sort algorithms work correctly only with this guarantee.

Impl policy: i32, i64, u*, bool, char, c_char, str implement Ord. f32 and f64 do not, because NaN makes some values incomparable.

#min / max / clamp

Three default methods are provided, usable without the impl implementing them.

let r = 3i32.min(7i32);              //→ 3
let m = 5.max(10);                   //→ 10
let c = 100.clamp(0, 50);            //→ 50
let nan_safe = 1.0f64.clamp(0.0, 10.0);  // ERROR - Ord is not defined for f64
                                          // (use a separate method for NaN-safe clamp)

#2.5.6. Hash - hashing (Eq consistency promise)

The hash trait is defined as follows.

#[lang("hash_trait")]
trait Hash: Eq {
    fn hash(self) -> u64;
}

The core promise is:

a == b ⇒ a.hash() == b.hash()

This promise underpins the correctness of every algorithm in HashMap<K, V> and HashSet<K>.

Since Hash: Eq, a type that does not implement Eq cannot implement Hash either. f64 does not implement Eq, so it cannot implement Hash.

#Examples

use rok::core::cmp::Hash;

let h1 = "hello".hash();
let h2 = "hello".hash();
h1 == h2;            //→ true (Hash consistency)

let h3 = 42i32.hash();

#User-defined

#[derive(PartialEq, Eq, Hash)]
struct UserId { id: u64; }

// automatic derive - possible because every field (id: u64) is Eq+Hash

#Collisions

Two different values of the same type may return the same hash; that is, a.hash() == b.hash() is allowed even when a != b. This is not a bug: collisions are unavoidable in a 64-bit hash space. Data structures such as HashMap handle collisions.

#2.5.7. Implementation matrix

Trait implementations per type are summarized below.

Dict and Set are unordered containers, so they have no PartialOrd / Ord. They implement PartialEq / Eq / Hash when their elements (keys and values) implement those traits, and compare and hash independently of iteration order (2.9).

List compares lexicographically: elements are compared from the front, the first differing element decides the order, and if one is a prefix of the other, the shorter one is smaller.

Two values of a sum type are compared first by member (variant) order, and, if they are the same member, by their payload using that member type's Ord. Member order is the canonical order of the sum type (refs-lang 2.6.4), independent of the written order. none is always last, so in T | none, none is greater than any T value. min / max / clamp follow the same order.

#2.5.8. Broadcast comparison traits

Of the 19 broadcast traits of 2.6 broadcast, the 6 comparison traits are defined as follows.

trait DotEq<Rhs>  { #[infix(".==")] fn dot_eq(...) -> Output; }
trait DotNe<Rhs>  { #[infix(".!=")] fn dot_ne(...) -> Output; }
trait DotLt<Rhs>  { #[infix(".<")] fn dot_lt(...) -> Output; }
trait DotGt<Rhs>  { #[infix(".>")] fn dot_gt(...) -> Output; }
trait DotLe<Rhs>  { #[infix(".<=")] fn dot_le(...) -> Output; }
trait DotGe<Rhs>  { #[infix(".>=")] fn dot_ge(...) -> Output; }

Each trait handles element-wise comparison of containers such as List or Vec3; the result type (Output) is usually List<bool> or [bool; N].

See 2.6 broadcast for the full broadcast semantics.

#2.5.9. #[derive(Eq, Ord, Hash, ...)]

refs-lang 6.2 #[derive] defines the derive mechanism. All five cmp traits can be derived.

#[derive(PartialEq, Eq, PartialOrd, Ord, Hash)]
struct Version { major: u32; minor: u32; patch: u32; }

Derive behavior per trait: PartialEq and Eq are defined as the AND of equality of all fields. PartialOrd and Ord compare lexicographically in field declaration order. Hash combines the hashes of all fields; the combining function is not specified.

The requirement is that every field (recursively) implements the same trait, and Eq / Ord also require their supertraits (PartialEq / PartialOrd, Eq) to be derived or implemented. If even one field does not implement Eq, #[derive(Eq)] is a compile error.

#2.5.10. Pattern matching and cmp

Literal patterns in match arms use PartialEq::eq.

match x {
    0 => "zero",
    1 => "one",
    _ => "other",
}
// → 0.eq(x) → compare, 1.eq(x) → compare, ...

Range patterns (0..=10 =>) use PartialOrd::le and ge.

See refs-lang 3.11 Patterns for the full pattern semantics.

Edit this page on GitHub