1.10 Comparators

8.12

1.10 Comparators🔗ℹ

A comparator is an object that compares two values and determines whether one is greater than the other, or whether they are equivalent. This comparison must respect some total ordering, meaning that for any two values x and y:

If x is less than y, then y must be greater than x. The reverse must hold true if x is greater than y.
If x is equivalent to y, then y must be equivalent to x.
If x is equal? to y, they must be equivalent.

Note that the third requirement above does not imply that all equivalent values must be equal?. For example, the real<=> comparator considers 3 and 3.0 equivalent, but (equal? 3 3.0) returns false. A comparator for which all equivalent values are also equal is said to be consistent with equality, and comparators which do not satisfy this stronger property are inconsistent with equality. All comparators defined in rebellion/base/comparator are consistent with equality unless otherwise stated.

procedure
(comparator? v) → boolean?
v : any/c

A predicate for comparators.

procedure
(compare comparator left right) → comparison?
  comparator : comparator?
  left : any/c
  right : any/c

Returns whether left is less than, greater than, or equivalent to right.

Examples:

> (compare real<=> 5 8)
#<lesser>
> (compare string<=> "foo" "bar")
#<greater>

syntax
(compare-infix comparator-expr comparison-chain)

comparison-chain = operand-expr operator operand-expr
| operand-expr operator comparison-chain

operator = <
| >
| <=
| >=
| ==
| !=

comparator-expr : comparator?

Compares the given operand-exprs using comparator-expr, returning #true if all of the specified comparisons are true and returning #false otherwise. Unlike compare, this form is a macro and allows specifying comparisons with an infix syntax. The given operand-exprs are evaluated in left-to-right order with short-circuiting. Each operand-expr is evaluated at most once.

Examples:

> (compare-infix real<=> 1 < 3)
#t
> (compare-infix real<=> 1 < 3 < 5)
#t
> (compare-infix real<=> 100 < 3 < (error "short circuits before reaching here"))
#f

procedure
(comparator-min comparator v ...+) → any/c
comparator : comparator?
v : any/c

Returns the smallest v, according to comparator.

Examples:

> (comparator-min real<=> 5 8)
5
> (comparator-min string<=> "foo" "bar")
"bar"

procedure
(comparator-max comparator v ...+) → any/c
comparator : comparator?
v : any/c

Returns the largest v, according to comparator.

Examples:

> (comparator-max real<=> 5 8)
8
> (comparator-max string<=> "foo" "bar")
"foo"

1.10.1 Constructing Comparators🔗ℹ

procedure
(comparator-of-constants constant ...) → comparator?
constant : any/c

Constructs a comparator that compares only the given constants using equal?. The order the constants are given in is interpreted as ascending order. Each constant must be unique, otherwise a contract exception is raised.

Examples:

(define size<=> (comparator-of-constants 'small 'medium 'large))

> (compare size<=> 'small 'large)
#<lesser>
> (compare size<=> 'medium 'medium)
#<equivalent>
> (compare size<=> 'small 'big)
comparator-of-constants: contract violation
expected: one of '(small medium large)
given: 'big

procedure
(comparator-map comparator f [#:name name]) → comparator?
  comparator : comparator?
  f : (-> any/c any/c)
  name : (or/c interned-symbol? #false) = #false

Wraps comparator as a comparator that first calls f on both of its inputs before comparing them. Beware that this often creates a comparator that is inconsistent with equality.

Examples:

> (define-record-type circle (color radius))
> (define circle<=> (comparator-map real<=> circle-radius))
> (compare circle<=>
(circle #:color 'green #:radius 5)
(circle #:color 'blue #:radius 8))
#<lesser>

procedure
(make-comparator function [#:name name]) → comparator?
function : (-> any/c any/c comparison?)
name : (or/c interned-symbol? #false) = #false

Constructs a comparator named name that compares values by calling function. Most users should use comparator-map to wrap an existing comparator instead of constructing one directly.

Examples:

(define symbol<=>
  (make-comparator
   (λ (left right)
     (cond [(symbol<? left right) lesser]
           [(equal? left right) equivalent]
           [else greater]))
   #:name 'symbol<=>))

> (compare symbol<=> 'apple 'banana)
#<lesser>
> (compare symbol<=> 'apple 'aardvark)
#<greater>

procedure
(comparator-reverse comparator) → comparator?
comparator : comparator?

Reverses comparator, returning a comparator that considers one value greater than another when comparator would consider it lesser and vice-versa.

Examples:

> (compare real<=> 2 5)
#<lesser>
> (compare (comparator-reverse real<=>) 2 5)
#<greater>

procedure
(comparator-chain comparator
...+
[ #:name name]) → comparator?
comparator : comparator?
name : (or/c interned-symbol? #false) = #false

Chains each comparator together into a single comparator named name that compares values using the leftmost comparator first, with each next comparator used to break ties in the previous comparator.

Examples:

(define-enum-type gem-type (opal ruby diamond))
(define-tuple-type gemstone (type weight))
(define gemstone-by-type<=>
  (comparator-map (comparator-of-constants opal ruby diamond) gemstone-type))
(define gemstone-by-weight<=> (comparator-map real<=> gemstone-weight))

> (transduce (list (gemstone diamond 3)
                   (gemstone ruby 5)
                   (gemstone diamond 8)
                   (gemstone opal 2)
                   (gemstone ruby 14)
                   (gemstone opal 12))
             (sorting (comparator-chain gemstone-by-type<=> gemstone-by-weight<=>))
             #:into into-list)
(list
(gemstone #<gem-type:opal> 2)
(gemstone #<gem-type:opal> 12)
(gemstone #<gem-type:ruby> 5)
(gemstone #<gem-type:ruby> 14)
(gemstone #<gem-type:diamond> 3)
(gemstone #<gem-type:diamond> 8))

1.10.2 Predefined Comparators🔗ℹ

value
real<=> : (comparator/c comparable-real?)

A comparator that compares real numbers. Note that not all values that satisfy the real? predicate can be compared: the not-a-number constants +nan.0 and +nan.0 are disallowed.

Examples:

> (compare real<=> 42 99.99)
#<lesser>
> (compare real<=> 42 +inf.0)
#<lesser>
> (compare real<=> 42 -inf.0)
#<greater>
> (compare real<=> 42 +nan.0)
real<=>: contract violation
  expected: comparable-real?
  given: +nan.0
  in: an operand of
      (comparator/c comparable-real?)
  contract from:
      <pkgs>/rebellion/base/comparator.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/rebellion/base/comparator.rkt:25:3

Beware that this comparator is inconsistent with equality, as it ignores the exactness of the compared numbers. This is the same behavior as <, =, and >, but it means that two un-equal? numbers may compare equivalent.

Examples:

> (compare real<=> 5 5.0)
#<equivalent>
> (compare real<=> -0.0 0.0)
#<equivalent>
> (compare real<=> +inf.0 +inf.0)
#<equivalent>

procedure
(comparable-real? v) → boolean?
v : any/c

A predicate that identifies real numbers that can be compared sensibly. This predicate is almost identical to real?, with the exception that it rejects the not-a-number constants.

Examples:

> (comparable-real? 42)
#t
> (comparable-real? +inf.0)
#t
> (comparable-real? +nan.0)
#f

value
natural<=> : (comparator/c natural?)

A comparator that compares natural numbers. (A natural number is an exact, nonnegative integer.)

Examples:

> (compare natural<=> 42 100)
#<lesser>
> (compare natural<=> 42 0)
#<greater>
> (compare natural<=> 42 42)
#<equivalent>
> (compare natural<=> 42 100.0)
natural<=>: contract violation
  expected: natural?
  given: 100.0
  in: an operand of
      (comparator/c natural?)
  contract from:
      <pkgs>/rebellion/base/comparator.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/rebellion/base/comparator.rkt:26:3
> (compare natural<=> 42 -10)
natural<=>: contract violation
  expected: natural?
  given: -10
  in: an operand of
      (comparator/c natural?)
  contract from:
      <pkgs>/rebellion/base/comparator.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/rebellion/base/comparator.rkt:26:3

value
string<=> : (comparator/c immutable-string?)

A comparator that lexicographically compares immutable strings. Mutable strings are disallowed, to prevent clients from concurrently mutating a string while it’s being compared.

Examples:

> (compare string<=> "aardvark" "zebra")
#<lesser>
> (compare string<=> "aardvark" (make-string 5 #\z))
string<=>: contract violation
  expected: immutable-string?
  given: "zzzzz"
  in: an operand of
      (comparator/c immutable-string?)
  contract from:
      <pkgs>/rebellion/base/comparator.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/rebellion/base/comparator.rkt:27:3

value
char<=> : (comparator/c char?)

A comparator that compares characters. Comparisons are consistent with the order imposed by char<?.

Example:

> (compare char<=> #\a #\z)
#<lesser>

value
symbol<=> : (comparator/c symbol?)

A comparator that lexicographically compares symbols. Symbols are equivalent if they contain the same characters. Note that this comparator is inconsistent with equality, because symbols that print the same are not necessarily equal, due to the existence of unreadable and uninterned symbols. If only interned symbols need to be compared, use interned-symbol<=> to ensure comparisons are consistent with equality.

Examples:

> (compare symbol<=> 'aardvark 'zebra)
#<lesser>
> (compare symbol<=> 'aardvark 'aardvark)
#<equivalent>
> (compare symbol<=> 'aardvark (string->uninterned-symbol "aardvark"))
#<equivalent>

value
interned-symbol<=> : (comparator/c interned-symbol?)

A comparator that lexicographically compares interned symbols. Unreadable symbols and uninterned symbols are disallowed to ensure the comparator is consistent with equality without imposing an arbitrary order between unequal symbols that print the same.

Examples:

> (compare interned-symbol<=> 'aardvark 'zebra)
#<lesser>
> (compare interned-symbol<=> 'aardvark (gensym 'zebra))
interned-symbol<=>: contract violation
  expected: interned-symbol?
  given: 'zebra983265
  in: an operand of
      (comparator/c interned-symbol?)
  contract from:
      <pkgs>/rebellion/base/comparator.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/rebellion/base/comparator.rkt:30:3

1.10.3 Comparison Constants🔗ℹ

procedure
(comparison? v) → boolean?
v : any/c

A predicate for comparison constants.

value
lesser : comparison?

A comparison constant indicating that the left value of a comparison is smaller than the right value.

value
greater : comparison?

A comparison constant indicating that the left value of a comparison is greater than the right value.

value
equivalent : comparison?

A comparison constant indicating that the left value of a comparison is equivalent to the right value. Note that equivalent values may not be equal?, depending on the comparator used.

1.10.4 Comparator Contracts🔗ℹ

procedure
(comparator/c operand-contract) → contract?
operand-contract : contract?

A contract combinator for comparators. Returns a contract that enforces that the contracted value is a comparator, and wraps the comparator to check every value it compares with operand-contract. If operand-contract is a chaperone contract, then the returned contract is as well.

Examples:

(define/contract even-integer<=>
  (comparator/c (and/c integer? even?))
  real<=>)

> (compare even-integer<=> 2 8)
#<lesser>
> (compare even-integer<=> 3 8)
even-integer<=>: contract violation
  expected: even?
  given: 3
  in: an and/c case of
      an operand of
      (comparator/c (and/c integer? even?))
  contract from: (definition even-integer<=>)
  blaming: top-level
   (assuming the contract is correct)
  at: eval:2:0

procedure
(comparator-operand-contract comparator) → contract?
comparator : comparator?

Returns the contract that guards values compared by comparator, or any/c if comparator does not have a contract attached to it. Note that the entire contract on comparator can be retrieved with value-contract.

Warning: because this function observes whether a contract is attached to comparator, it may return different results for two comparators that are otherwise equal?. The result from comparator-operand-contract should be viewed as a best-effort optimistic estimate: any input that does not satisfy the returned contract will definitely raise an error when given to the contracted comparator, but there is no guarantee that inputs that satisfy the returned contract will be accepted.

Examples:

(define/contract even-integer<=>
(comparator/c (and/c integer? even?))
real<=>)

> (comparator-operand-contract even-integer<=>)
(and/c integer? even?)
> (value-contract even-integer<=>)
(comparator/c (and/c integer? even?))

1.10.5 Comparator Chaperones and Impersonators🔗ℹ

procedure
(comparator-impersonate comparator
[ #:operand-guard operand-guard
#:properties properties
#:comparison-marks marks
#:chaperone? chaperone?])
→ comparator?
  comparator : comparator?
  operand-guard : (or/c (-> any/c any/c #false)) = #false
   properties : (hash/c impersonator-property? any/c #:immutable #true)
= empty-hash
  marks : immutable-hash? = empty-hash
  chaperone? : boolean? = (false? operand-guard)

Returns an impersonator of comparator. Whenever the impersonator comparator is used to compare two values, if operand-guard is not false, it is applied once to each value. The application of the comparator’s comparison function to those two values is wrapped in the continuation marks given by marks. Additionally, the returned impersonator includes an impersonator property for each property and value entry within properties. The returned impersonator is equal? to comparator.

If chaperone? is true, the returned impersonator is a chaperone. In that case, operand-guard must always return a value equal to the one it is given. Furthermore, any impersonators returned from operand-guard must be chaperones.

Examples:

(define printing-real<=>
  (comparator-impersonate real<=>
                          #:operand-guard (λ (x) (printf "Got ~a\n" x) x)
                          #:chaperone? #true))

> (compare printing-real<=> 4 8)
Got 4
Got 8
#<lesser>
> (chaperone-of? printing-real<=> real<=>)
#t

1	Base Libraries
2	Data Types
3	Streaming Computations
4	Collections
5	Concurrency
6	Binary Data
7	Module Utilities
8	Other Libraries

1.1	Generative Tokens
1.2	Immutable Strings
1.3	Uncallable Functions
1.4	Option Values
1.5	Pairs
1.6	Results
1.7	Symbols
1.8	Variants
1.9	Converters
1.10	Comparators
1.11	Equivalence Relations
1.12	Ranges

1.10.1	Constructing Comparators
1.10.2	Predefined Comparators
1.10.3	Comparison Constants
1.10.4	Comparator Contracts
1.10.5	Comparator Chaperones and Impersonators