3 Equivalence Relations
| (require relation/equivalence) | package: relation-lib |
A unified equality relation = together with derived utilities for comparing data.
Traditionally, in Lisp, a distinction is made between object "identity" and object "equality." The former represents that two references indicate the same object, while the latter means that the references indicate objects that are "indistinguishable," without necessarily asserting that they refer to a singular object.
Racket provides eq? to check for object identity, but for equality, there are several interfaces to choose from: we have = (for numbers), eqv? (for numbers and other types), and equal? (the broadest notion of equality covering most cases). None of these can be used exclusively to represent the idea of "equality" in practice, since cases exist where each is preferable to the others. For instance, = reports that 1 is equal to 1.0 – a behavior that is desirable in many cases – whereas equal? sees them as unequal.
Yet, mathematically, any notion of equality may be represented using only (1) a minimally expressive elementary notion of equality and (2) a "projection" function mapping the inputs to a form amenable to elementary comparison. In Racket, this could be represented by the simple interface (= #:key ...), where the projection function is provided via the key argument.
The present module therefore provides such an interface, overriding the standard = operator to allow its use with any type, delegating to built-in equality checks to perform the most appropriate comparison depending on the type of the values being compared, leveraging the key argument to express broader notions of equivalence than simple equality – since, indeed, any idea of equality presupposes a definition in relation to which two objects are indistinguishable.
The = relation provided in this module is intended to express the notion of "equality" in all cases, but, at least for the moment, does not usually differentiate between mutable and immutable versions of a data type. For that, consider using egal?.
3.1 Interface
value
> (= 1 1) #t
> (= 1 2) #f
> (= 1 (void)) #f
> (= "apple" "APPLE") #f
> (= #:key string-upcase "apple" "APPLE") #t
> (= #:key ->number "42.0" "42/1") #t
procedure
(comparable? v) → boolean?
v : any/c
> (comparable? 3) #t
> (comparable? #\a) #t
> (comparable? "cherry") #t
> (comparable? (set)) #t
> (comparable? (hash)) #t
procedure
v : comparable?
procedure
(secondary-hash-code v) → fixnum?
v : comparable?
> (hash-code 3) 288371113640067072
> (hash-code #\a) 97
> (hash-code 'abc) 425937936755061829
> (hash-code "cherry") 680675407862930294
In order to implement this interface in custom types, all that is needed is to implement the gen:equal+hash interface. gen:comparable itself should not be implemented directly, since there is never a case where both of these interfaces would need to be implemented. To avoid any possibility of conflicting notions of equality, gen:comparable simply defers to the built-in equal? for the definition of equality for custom types.
All Racket types are gen:comparable, so = may be treated as a drop-in replacement for equal?.
3.2 Utilities
The following equivalence-related utilities are universally applicable, since all types are gen:comparable.
procedure
key : (-> comparable? comparable?) = #f v : comparable?
> (= 1 1 1) #t
> (= 1 2) #f
> (= "apple" "apple" "apple") #t
> (= 3/2 1.5) #t
> (= (list 1 3/2 2.0) (list 1.0 1.5 2)) #t
> (= (list 1 3/2 2.0) #(1.0 1.5 2)) #f
> (= #:key string-upcase "apple" "Apple" "APPLE") #t
> (= #:key ->number "42.0" "42/1" "42") #t
> (= #:key ->number "42" "42.1") #f
> (= #:key even? 12 20) #t
> (= #:key odd? 12 20) #t
> (= #:key first (list 1.5 4 7) (list 3/2 2 3)) #t
> (= #:key (~ even? ->number) "12" "20") #t
procedure
key : (-> comparable? comparable?) = #f v : comparable?
procedure
key : (-> comparable? comparable?) = #f v : comparable?
procedure
key : (-> comparable? comparable?) = #f v : comparable?
> (≠ 1 1 2) #t
> (≠ 1 1) #f
> (≠ "apple" "Apple") #t
> (≠ 3/2 1.5) #f
> (≠ #:key length "cherry" "banana" "avocado") #t
procedure
key : (-> comparable? comparable?) vs : (listof comparable?)
procedure
key : (-> comparable? comparable?) vs : (listof comparable?)
> (group-by identity (list 1 1 2 2 3 3 3)) '((1 1) (2 2) (3 3 3))
> (group-by identity (list 1 1 1)) '((1 1 1))
> (group-by odd? (list 1 1 2 3 4 8 12)) '((1 1 3) (2 4 8 12))
> (group-by identity (list "cherry" "banana" "apple")) '(("cherry") ("banana") ("apple"))
> (group-by length (list "apple" "banana" "cherry")) '(("apple") ("banana" "cherry"))
procedure
(generic-set [#:key key] v ...) → list?
key : (-> comparable? comparable?) = #f v : comparable?
> (generic-set 1 2 3) (gset '(1 2 3) #<procedure:identity>)
> (generic-set 1 1 2 2 3 3 3) (gset '(1 2 3) #<procedure:identity>)
> (generic-set "cherry" "banana" "apple") (gset '("cherry" "banana" "apple") #<procedure:identity>)
> (generic-set #:key odd? 1 2 3 4 5) (gset '(1 2) #<procedure:odd?>)
> (generic-set #:key string-upcase "apple" "Apple" "APPLE" "banana" "Banana" "cherry") (gset '("apple" "banana" "cherry") #<procedure:string-upcase>)
> (define my-set (generic-set #:key string-upcase "cherry" "banana" "apple")) > (set-add my-set "APPLE") (gset '("APPLE" "cherry" "banana") #<procedure:string-upcase>)
procedure
key : (-> comparable? comparable?) = #f elem : comparable? col : sequence?
> (tail 4 (list 1 2 3)) '()
> (tail 4 (list 1 4 3)) '(4 3)
> (->list (tail "cherry" (stream "apple" "banana" "cherry"))) '("cherry")
> (tail "BANANA" (list "apple" "banana" "cherry")) '()
> (tail #:key string-upcase "BANANA" (list "apple" "banana" "cherry")) '("banana" "cherry")
procedure
key : (-> comparable? comparable?) = #f elem : comparable? col : sequence?
procedure
key : (-> comparable? comparable?) = #f elem : comparable? col : sequence?
in? is a right-curried version of member?, useful in cases where we may want to pre-specify the collection and apply the predicate to candidate elements.
> (member? 4 (list 1 2 3)) #f
> (member? 4 (list 1 4 3)) #t
> (member? "cherry" (stream "apple" "banana" "cherry")) #t
> (member? "BANANA" (list "apple" "banana" "cherry")) #f
> (member? #:key string-upcase "BANANA" (list "apple" "banana" "cherry")) #t
> (member? "BANANA" (generic-set #:key string-upcase "apple" "banana" "cherry")) #t
> (member? "tomato" (generic-set #:key length "apple" "banana" "grape")) #t
> ((in? (list 1 2 3)) 3) #t
> ((in? (list 1 2 3)) "2") #f
> ((in? #:key ->number (list 1 2 3)) "2") #t
procedure
key : (-> comparable? comparable?) = #f assoc-key : comparable? col : (sequenceof pair?)