2 Order Relations

A generic interface and utilities for defining and working with orderable data.

By default, the built-in comparison operators <, <=, =, >= and > operate on numbers specifically, while other comparable types like characters and strings have their own type-specific comparison operators, for instance char<? and string<?.

This module provides a generic interface that overrides these standard operators to allow their use with any orderable type and not only numbers, and also provides additional utilities to support working with orderable data in a type-agnostic way. You can also provide an implementation for the interface in custom types so that they can be compared and reasoned about by using the same standard operators as well as the generic utilities provided here.

2.1 Interface

value
gen:orderable : any/c

A generic interface that represents any object that can be compared with other objects of the same type in terms of order, that is, in cases where we seek to know, "is this value less than or greater than that value?" Any type implementing this interface must also implement gen:comparable unless the latter’s default fallback of equal? is adequate. The following built-in types have implementations for the order relations <, <=, >= and >:

Note that even if a type implements the order relations, some values may still be order-incomparable (see partial order), meaning that none of the relations would return true for them. For instance, the sets {1, 2} and {1, 3} are incomparable under their canonical order relation (i.e. subset?), while also not being equal.

Examples:

> (< 1 2 3)
#t
> (> #\c #\b #\a)
#t
> (< "apple" "banana" "cherry")
#t
> (< (set) (set 1) (set 1 2))
#t
> (< #:key string-upcase "apple" "APPLE")
#f
> (< #:key ->number "42.0" "53/1")
#t

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

Predicate to check if a value is comparable via the generic order operators <, <=, >= and > (and consequently also derived utilities such as min and max).

Examples:

> (orderable? 3)
#t
> (orderable? #\a)
#t
> (orderable? "cherry")
#t
> (orderable? (set))
#t
> (orderable? (hash))
#f

To implement this interface for custom types, the following generic methods need to be implemented. Note that the only required method is less-than? – the others will be inferred from it if an implementation isn’t explicitly specified:

procedure
(less-than? a b) → boolean?
a : orderable?
b : orderable?

A function taking two arguments that tests whether the first is less than the second. Both arguments must be instances of the structure type to which the generic interface is associated (or a subtype of the structure type). The function must return true if the first argument is less than the second, and false if not.

Every implementation of gen:orderable must provide an implementation of less-than?.

procedure
(greater-than? a b) → boolean?
a : orderable?
b : orderable?

Similar to less-than?, but tests whether the first argument is greater than the second one.

Providing an implementation of this method is optional, as one will be inferred for it from less-than? if none is specified.

procedure
(less-than-or-equal? a b) → boolean?
a : orderable?
b : orderable?

Similar to less-than?, but tests whether the first argument is either less than or equal to the second one.

Providing an implementation of this method is optional, as one will be inferred for it from less-than? and gen:comparable if none is specified.

procedure
(greater-than-or-equal? a b) → boolean?
a : orderable?
b : orderable?

Similar to less-than?, but tests whether the first argument is either greater than or equal to the second one.

Providing an implementation of this method is optional, as one will be inferred for it from greater-than? and gen:comparable if none is specified.

2.2 Utilities

The following utilities are provided which work with any type that implements the gen:orderable interface.

procedure
(< [#:key key] v ...) → boolean?
key : (-> orderable? orderable?) = #f
v : orderable?

True if the v’s are monotonically increasing according to the canonical order relation for the arguments, which is determined by their type. If a transformation is provided via the #:key argument, then it is applied to the arguments prior to comparing them.

Examples:

> (< 1 2 3)
#t
> (< 2 1)
#f
> (< "apple" "banana" "cherry")
#t
> (< #:key length "cherry" "blueberry" "abyssinian gooseberry")
#t

procedure
(<= [#:key key] v ...) → boolean?
  key : (-> orderable? orderable?) = #f
  v : orderable?
procedure
(≤ [#:key key] v ...) → boolean?
  key : (-> orderable? orderable?) = #f
  v : orderable?

True if the v’s are monotonically nondecreasing according to the canonical order relation for the arguments, which is determined by their type. If a transformation is provided via the #:key argument, then it is applied to the arguments prior to comparing them.

Examples:

> (≤ 1 1 3)
#t
> (≤ 2 1)
#f
> (≤ "apple" "apple" "cherry")
#t
> (≤ #:key length "cherry" "banana" "avocado")
#t

procedure
(>= [#:key key] v ...) → boolean?
  key : (-> orderable? orderable?) = #f
  v : orderable?
procedure
(≥ [#:key key] v ...) → boolean?
  key : (-> orderable? orderable?) = #f
  v : orderable?

True if the v’s are monotonically nonincreasing according to the canonical order relation for the arguments, which is determined by their type. If a transformation is provided via the #:key argument, then it is applied to the arguments prior to comparing them.

Examples:

> (≥ 3 1 1)
#t
> (≥ 1 2)
#f
> (≥ "banana" "apple" "apple")
#t
> (≥ #:key length "banana" "cherry" "apple")
#t

procedure
(> [#:key key] v ...) → boolean?
key : (-> orderable? orderable?) = #f
v : orderable?

True if the v’s are monotonically decreasing according to the canonical order relation for the arguments, which is determined by their type. If a transformation is provided via the #:key argument, then it is applied to the arguments prior to comparing them.

Examples:

> (> 3 2 1)
#t
> (> 1 1)
#f
> (> "cherry" "banana" "apple")
#t
> (> #:key length "abyssinian gooseberry" "blueberry" "apple")
#t

procedure
(min [#:key key] v ...) → orderable?
key : (-> orderable? orderable?) = #f
v : orderable?

Returns the minimum value according to the canonical order relation for the arguments, which is determined by their type. If key is provided, it is applied to the arguments prior to the comparison (this pattern is often referred to as "argmin" in math and programming literature). The values are compared using the canonical comparison for their type.

In the case of a nonlinear order (i.e. where there is no greatest or least element), min would return an arbitrary local minimum. You should typically only use this function when you know that a global minimum exists.

Examples:

> (min 3 2 1)
1
> (min "cherry" "banana" "apple")
"apple"
> (min (set 1 2) (set 1) (set 1 2 3))
(immutable-custom-set #f '#hash((1 . #t)))
> (min #:key length "apple" "banana" "cherry")
"apple"

procedure
(max [#:key key] v ...) → orderable?
key : (-> orderable? orderable?) = #f
v : orderable?

Returns the maximum value according to the canonical order relation for the arguments, which is determined by their type. If key is provided, it is applied to the arguments prior to the comparison (this pattern is often referred to as "argmax" in math and programming literature). The values are compared using the canonical comparison for their type.

In the case of a nonlinear order (i.e. where there is no greatest or least element), max would return an arbitrary local maximum. You should typically only use this function when you know that a global maximum exists.

Examples:

> (max 3 2 1)
3
> (max "cherry" "banana" "apple")
"cherry"
> (max (set 1 2) (set 1) (set 1 2 3))
(immutable-custom-set #f '#hash((1 . #t) (3 . #t) (2 . #t)))
> (max #:key length "apple" "banana" "cherry")
"banana"

procedure
(sort less-than? [#:key key] seq) → (sequenceof orderable?)
  less-than? : (one-of/c < >)
  key : (-> orderable? orderable?) = #f
  seq : (sequenceof orderable?)

Like sort but accepts arbitrary sequences as input, and employs a generic order relation (either < or >) as the comparison procedure.

Examples:

> (sort < (list 1 2 3))
'(1 2 3)
> (sort > (list 1 2 3))
'(3 2 1)
> (sort < (list "cherry" "banana" "apple"))
'("apple" "banana" "cherry")
> (map ->list (sort < (list (set 1 2) (set 1) (set 1 2 3))))
'((1) (2 1) (2 3 1))
> (sort < #:key length (list "apple" "avocado" "banana" "cherry"))
'("apple" "banana" "cherry" "avocado")

top ← prev up next →

1	Equivalence Relations
2	Order Relations
3	Type Transformers
4	Algebraic Operators