On this page:
3.1 Interface
gen:  comparable
comparable?
hash-code
secondary-hash-code
3.2 Utilities
=
/  =
!=
group-by
=/  classes
generic-set
tail
member?
in?
assoc

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🔗ℹ

A generic interface that represents any object that can be compared with other objects of the same type in terms of equivalence, that is, in cases where we seek to know, "are these values equal, for some definition of equality?" All built-in as well as custom types are gen:comparable. For all custom types, the implementation defers to the built-in equal?.

Examples:
> (= 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
Predicate to check if a value is comparable via the generic equivalence operators = and /=.

Examples:
> (comparable? 3)

#t

> (comparable? #\a)

#t

> (comparable? "cherry")

#t

> (comparable? (set))

#t

> (comparable? (hash))

#t

procedure

(hash-code v)  fixnum?

  v : comparable?

procedure

(secondary-hash-code v)  fixnum?

  v : comparable?
Similar to equal-hash-code and equal-secondary-hash-code, but these yield the hash code reported by the underlying operation used to perform the equality check. For example, for numbers, hash-code is equivalent to the eqv-hash-code of the inexact representation of the number, while for strings, it evaluates to the hash code reported by equal-hash-code. Likewise, for symbols, it evaluates to the hash code reported by eq-hash-code since eq? is the check employed for symbol comparisons.

Examples:
> (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 key] v ...)  boolean?

  key : (-> comparable? comparable?) = #f
  v : comparable?
True if the v’s are equal. This uses the most appropriate equality check for the type. For instance, it uses the built-in = operator for numeric data, and equal? for some other types such as structures. If a transformation is provided via the #:key argument, then this transformation is applied to the input values first, prior to performing the equality check. For sequences, the types of the values are compared prior to recursively applying the equality relation on the contents.

Examples:
> (= 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 key] v ...)  boolean?

  key : (-> comparable? comparable?) = #f
  v : comparable?

procedure

( [#:key key] v ...)  boolean?

  key : (-> comparable? comparable?) = #f
  v : comparable?

procedure

(!= [#:key key] v ...)  boolean?

  key : (-> comparable? comparable?) = #f
  v : comparable?
True if the v’s are not equal. This is simply a negation of the generic =. If a transformation is provided via the #:key argument, then it is applied to the arguments prior to comparing them.

Examples:
> ( 1 1 2)

#t

> ( 1 1)

#f

> ( "apple" "Apple")

#t

> ( 3/2 1.5)

#f

> ( #:key length "cherry" "banana" "avocado")

#t

procedure

(group-by key vs)  (listof list?)

  key : (-> comparable? comparable?)
  vs : (listof comparable?)

procedure

(=/classes key vs)  (listof list?)

  key : (-> comparable? comparable?)
  vs : (listof comparable?)
Like group-by, groups input values into equivalence classes under the equivalence relation induced by key. Values that are = after the application of key are grouped together to form the classes.

Examples:
> (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?
Returns a set containing deduplicated input values using the provided equivalence relation as the test for equality (by default, = is applied directly unless a key is specified).

Examples:
> (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

(tail [#:key key] elem col)  sequence?

  key : (-> comparable? comparable?) = #f
  elem : comparable?
  col : sequence?
A generic version of member that operates on any sequence rather than lists specifically, and employs the generic = relation rather than the built-in equal?. The result of invocation is the tail of the sequence beginning at the value that is = to elem, under the transformation key (if provided), or the empty list if elem isn’t found. If a boolean value is desired, use member? instead. If a tail by position is desired, use drop.

Examples:
> (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

(member? [#:key key] elem col)  boolean?

  key : (-> comparable? comparable?) = #f
  elem : comparable?
  col : sequence?

procedure

(in? [#:key key] elem col)  boolean?

  key : (-> comparable? comparable?) = #f
  elem : comparable?
  col : sequence?
A generic version of member similar to tail that checks if a value is present in a collection. Unlike tail, this returns a boolean value and supports non-ordered collections like sets where a tail is not well-defined. In the special case where col is a generic-set, the key provided to member?, if any, is ignored as it may conflict with the existing key defining the equivalence relation in the generic set.

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.

Examples:
> (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

(assoc [#:key key] assoc-key col)  pair?

  key : (-> comparable? comparable?) = #f
  assoc-key : comparable?
  col : (sequenceof pair?)
A generic version of assoc, this checks if a value keyed by assoc-key is present in a collection structured as an association list. The first item in each element of col is compared against assoc-key using = after first applying the transformation key to both values.

Examples:
> (assoc 'b (list '(a 1) '(b 2)))

'(b 2)

> (assoc 2 (list '(1 a) '(2 b) '(3 c)))

'(2 b)

> (assoc 2 (list '(1 a) '(2.0 b) '(3 c)))

'(2.0 b)

> (assoc #:key string-upcase "cherry" (list '("Apple" a) '("Banana" b) '("Cherry" c)))

'("Cherry" c)