Equality, ordering, and hashing

In comparable.cecil:

  abstract object comparable[T <= comparable[T]];
    extend type comparable[`T] subtypes comparable[`S <= T];
  signature =(x1:`T <= comparable[T], x2:`T <= comparable[T]):bool;  - equal (abstract) values?
  method !=(x1@:`T <= comparable[T], x2@:`T <= comparable[T]):bool;  - not =

Comparable objects can be tested for equality. This equality should be an abstract notion of equality which compares two abstract values, as appropriate to the kind of data types being compared. It is not a low-level representation equality such as ==, which, like Lisp's eq, tests ``pointer equality.'' By default, operations that compare elements use = rather than ==, unless the operation's name includes identity_.

  abstract object identity_comparable[T <= identity_comparable[T]]
        isa comparable[T];
    extend type identity_comparable[`T] subtypes identity_comparable[`S <= T];
  method =(x1@:`T <= identity_comparable[T],
           x2@:`T <= identity_comparable[T]):bool;

Identity_comparable objects are comparable objects that implement = in terms of == by default.

  abstract object partially_ordered[T <= partially_ordered[T]]
        isa comparable[T];
    extend type partially_ordered[`T] subtypes partially_ordered[`S <= T];
  signature <(x1:`T <= partially_ordered[T],
              x2:`T <= partially_ordered[T]):bool;  - x1 ordered below x2?
  method <=(x1@:`T <= partially_ordered[T],
            x2@:`T <= partially_ordered[T]):bool;  - < or =
  method > (x1@:`T <= partially_ordered[T],
            x2@:`T <= partially_ordered[T]):bool;  - x2 < x1?
  method >=(x1@:`T <= partially_ordered[T],
            x2@:`T <= partially_ordered[T]):bool;  - > or =

Partially ordered objects are comparable objects that also can be compared for being less than one another, and other combinations. Since they form only a partial order, not(a < b) does not imply a >= b.

  abstract object ordered[T <= ordered[T]] isa partially_ordered[T];
    extend type ordered[`T] subtypes ordered[`S <= T];
  method <=(x1@:`T <= ordered[T], x2@:`T <= ordered[T]):bool;
  method >=(x1@:`T <= ordered[T], x2@:`T <= ordered[T]):bool;
  method min (x1:`T <= ordered[T], x2:`T <= ordered[T]):T;
  method max (x1:`T <= ordered[T], x2:`T <= ordered[T]):T;
  method compare(x1@:`T <= ordered[T], x2@:`T <= ordered[T],
                 if_less:&():`S, if_equal:&():`S, if_greater:&():`S
                 ):S;
  abstract object ordered_using_compare[T <= ordered_using_compare[T]]
              isa ordered[T]
         subtypes ordered_using_compare[`S<=T];
  method =(x1@:`T <= ordered_using_compare[T],
           x2@:`T <= ordered_using_compare[T]):bool;
  method <(x1@:`T <= ordered_using_compare[T],
           x2@:`T <= ordered_using_compare[T]):bool;
  method compare(x1@:`T <= ordered_using_compare[T],
                 x2@:`T <= ordered_using_compare[T],
                 if_less:&():`S, if_equal:&():`S, if_greater:&():`S
                 ):S;

Ordered objects refine partially-ordered objects by imposing a total order, i.e., not(a < b) does imply a >= b. The min and max functions are defined for all ordered objects. The compare function implements a three-way comparison, invoking one of its argument closures depending on how the first argument compares to its second argument. By default, concrete subclasses provide implementations of = and <, and compare is provided by default in terms of those primitives. Alternatively, a concrete subclass can inherit from ordered_using_compare, which assumes the subclass will provide an implementation of compare and defines = and < in terms of it.

  abstract object hashable[T <= hashable[T]] isa comparable[T];
    extend type hashable[`T] subtypes hashable[`S <= T];
  signature hash(hashable[`T], range:int):int;

A hashable object is a comparable (equality-testable) object that also supports a hash function. hash(x, r) returns an integer in the range [0..r-1], subject to the constraint that if a = b, then hash(a, r) = hash(b, r).

  abstract object identity_hashable[T <= identity_hashable[T]]
        isa identity_comparable[T], hashable[T];
    extend type identity_hashable[`T] subtypes identity_hashable[`S <= T];

An identity_hashable object is both hashable and identity_comparable.

  abstract object ordered_hashable[T <= ordered_hashable[T]] isa ordered[T],
                                                                 hashable[T];
    extend type ordered_hashable[`T] subtypes ordered_hashable[`S <= T];

An ordered_hashable object is both hashable and ordered.