2 Order Relations
(require relation/order) | package: Relation |
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
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.
> (< 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
> (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?
Every implementation of gen:orderable must provide an implementation of less-than?.
procedure
(greater-than? a b) → boolean?
a : orderable? b : orderable?
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?
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?
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 : (-> orderable? orderable?) = #f v : orderable?
> (< 1 2 3) #t
> (< 2 1) #f
> (< "apple" "banana" "cherry") #t
> (< #:key length "cherry" "blueberry" "abyssinian gooseberry") #t
procedure
key : (-> orderable? orderable?) = #f v : orderable?
procedure
key : (-> orderable? orderable?) = #f v : orderable?
> (≤ 1 1 3) #t
> (≤ 2 1) #f
> (≤ "apple" "apple" "cherry") #t
> (≤ #:key length "cherry" "banana" "avocado") #t
procedure
key : (-> orderable? orderable?) = #f v : orderable?
procedure
key : (-> orderable? orderable?) = #f v : orderable?
> (≥ 3 1 1) #t
> (≥ 1 2) #f
> (≥ "banana" "apple" "apple") #t
> (≥ #:key length "banana" "cherry" "apple") #t
procedure
key : (-> orderable? orderable?) = #f v : orderable?
> (> 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?
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.
> (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?
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.
> (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?)
> (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")