Equality, ordering, and hashing

In comparable.diesel:

extend module Stdlib;

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 an object identity test 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_. Subclasses should implement =; != is derived from it.

module Comparable;
  abstract class comparable[T <= comparable[T]] isa comparable[`S <= T];
  fun =(x1:`T <= comparable[T], x2:`T <= comparable[T]):bool;  - equal (abstract) values?
  fun !=(x1:`T <= comparable[T], x2:`T <= comparable[T]):bool;  - not =

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

module IdentityComparable;
  abstract class identity_comparable[T <= identity_comparable[T]]
        isa comparable[T], identity_comparable[`S <= T];

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. The compare function implements a four-way comparison, invoking one of its argument closures depending on how the first argument compares to its second argument. By default, subclasses should implement <; the other operations are defined in terms of < and =. Alternatively, subclasses can inherit instead from partially_ordered_using_<= and then implement <= instead of <.

module PartiallyOrdered;
  abstract class partially_ordered[T <= partially_ordered[T]]
        isa comparable[T], partially_ordered[`S <= T];
  fun < (x1:`T <= partially_ordered[T],
                x2:`T <= partially_ordered[T]):bool;  - x1 ordered below x2?
  fun <=(x1:`T <= partially_ordered[T],
                x2:`T <= partially_ordered[T]):bool;  - < or =
  fun > (x1:`T <= partially_ordered[T],
                x2:`T <= partially_ordered[T]):bool;  - x2 < x1?
  fun >=(x1:`T <= partially_ordered[T],
                x2:`T <= partially_ordered[T]):bool;  - > or =

The PartiallyOrderedCompareResult abstract class and its four concrete objects, Equal, LessThan, GreaterThan, and Unordered, represent the possible outcomes of comparing two partially_ordered values.

  abstract class PartiallyOrderedCompareResult
                        isa identity_comparable[PartiallyOrderedCompareResult];
    abstract class OrderedCompareResult
                                        isa PartiallyOrderedCompareResult;
      object Equal isa OrderedCompareResult;
      object LessThan isa OrderedCompareResult;
      object GreaterThan isa OrderedCompareResult;
    object Unordered isa PartiallyOrderedCompareResult;
  fun compare(x1:`T <= partially_ordered[T],
                     x2:`T <= partially_ordered[T],
                     if_less:&():`S, if_equal:&():`S, if_greater:&():`S,
                     if_unordered:&():`S):S;
  fun compare(x1:`T <= partially_ordered[T],
                     x2:`T <= partially_ordered[T]
                     ):PartiallyOrderedCompareResult;  - compare two partially-ordered values, returning an outcome
module PartiallyOrderedUsingLE;
  abstract class partially_ordered_using_<=
                                        [T <= partially_ordered_using_<=[T]]
        isa partially_ordered[T], partially_ordered_using_<=[`S <= T];

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.

module Ordered;
  abstract class ordered[T <= ordered[T]] isa partially_ordered[T],
                                                     ordered[`S <= T];
  fun min(x1:`T <= ordered[T], x2:`T <= ordered[T]):T;
  fun max(x1:`T <= ordered[T], x2:`T <= ordered[T]):T;
  fun compare(x1:`T <= ordered[T], x2:`T <= ordered[T],
                     if_less:&():`S, if_equal:&():`S, if_greater:&():`S
                     ):S;
module OrderedUsingCompare;  - compare two ordered values, returning an outcome
  abstract class ordered_using_compare[T <= ordered_using_compare[T]]
              isa ordered[T], ordered_using_compare[`S <= T];

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).

module Hashable;
  abstract class hashable[T <= hashable[T]] isa comparable[T],
                                                       hashable[`S <= T];
  fun hash(t:hashable[`T], range:int):int;

An identity_hashable object is both hashable and identity_comparable.

module IdentityHashable;
  abstract class identity_hashable[T <= identity_hashable[T]]
        isa identity_comparable[T], hashable[T], identity_hashable[`S <= T];

An ordered_hashable object is both hashable and ordered.

module OrderedHashable;
  abstract class ordered_hashable[T <= ordered_hashable[T]]
        isa ordered[T], hashable[T], ordered_hashable[`S <= T];