scribblings/reference/equality.scrbl

#lang scribble/manual
@(require "mz.rkt")


@title{Equality}


Equality is the concept of whether two values are ``the same.'' Racket supports
a few different kinds of equality by default, though @racket[equal?] is
preferred for most use cases.

@defproc[(equal? [v1 any/c] [v2 any/c]) boolean?]{

 Two values are @racket[equal?] if and only if they are @racket[eqv?],
 unless otherwise specified for a particular datatype.

 Datatypes with further specification of @racket[equal?] include
 strings, byte strings, pairs, mutable pairs, vectors, boxes, hash
 tables, and inspectable structures. In the last six cases, equality
 is recursively defined; if both @racket[v1] and @racket[v2] contain
 reference cycles, they are equal when the infinite unfoldings of the
 values would be equal. See also @racket[gen:equal+hash] and
 @racket[prop:impersonator-of].

 @(examples
   (equal? 'yes 'yes)
   (equal? 'yes 'no)
   (equal? (* 6 7) 42)
   (equal? (expt 2 100) (expt 2 100))
   (equal? 2 2.0)
   (let ([v (mcons 1 2)]) (equal? v v))
   (equal? (mcons 1 2) (mcons 1 2))
   (equal? (integer->char 955) (integer->char 955))
   (equal? (make-string 3 #\z) (make-string 3 #\z))
   (equal? #t #t))}


@defproc[(eqv? [v1 any/c] [v2 any/c]) boolean?]{

 Two values are @racket[eqv?] if and only if they are @racket[eq?],
 unless otherwise specified for a particular datatype.

 The @tech{number} and @tech{character} datatypes are the only ones for which
 @racket[eqv?] differs from @racket[eq?]. Two numbers are @racket[eqv?] when
 they have the same exactness, precision, and are both equal and non-zero, both
 @racketvalfont{+0.0}, both @racketvalfont{+0.0f0}, both @racketvalfont{-0.0},
 both @racketvalfont{-0.0f0}, both @racketvalfont{+nan.0}, or both
 @racketvalfont{+nan.f}---considering real and imaginary components separately
 in the case of @tech{complex numbers}. Two characters are @racket[eqv?] when
 their @racket[char->integer] results are equal.

 Generally, @racket[eqv?] is identical to @racket[equal?] except that the former
 cannot recursively compare the contents of compound data types (such as lists
 and structs) and cannot be customized by user-defined data types. The use of
 @racket[eqv?] is lightly discouraged in favor of @racket[equal?].

 @(examples
   (eqv? 'yes 'yes)
   (eqv? 'yes 'no)
   (eqv? (* 6 7) 42)
   (eqv? (expt 2 100) (expt 2 100))
   (eqv? 2 2.0)
   (let ([v (mcons 1 2)]) (eqv? v v))
   (eqv? (mcons 1 2) (mcons 1 2))
   (eqv? (integer->char 955) (integer->char 955))
   (eqv? (make-string 3 #\z) (make-string 3 #\z))
   (eqv? #t #t))}


@defproc[(eq? [v1 any/c] [v2 any/c]) boolean?]{

 Return @racket[#t] if @racket[v1] and @racket[v2] refer to the same
 object, @racket[#f] otherwise. As a special case among @tech{numbers},
 two @tech{fixnums} that are @racket[=] are also the same according
 to @racket[eq?]. See also @secref["model-eq"].

 @(examples
   (eq? 'yes 'yes)
   (eq? 'yes 'no)
   (eq? (* 6 7) 42)
   (eq? (expt 2 100) (expt 2 100))
   (eq? 2 2.0)
   (let ([v (mcons 1 2)]) (eq? v v))
   (eq? (mcons 1 2) (mcons 1 2))
   (eq? (integer->char 955) (integer->char 955))
   (eq? (make-string 3 #\z) (make-string 3 #\z))
   (eq? #t #t))}


@defproc[
 (equal?/recur [v1 any/c] [v2 any/c] [recur-proc (any/c any/c -> any/c)])
 boolean?]{

 Like @racket[equal?], but using @racket[recur-proc] for recursive
 comparisons (which means that reference cycles are not handled
 automatically). Non-@racket[#f] results from @racket[recur-proc] are
 converted to @racket[#t] before being returned by
 @racket[equal?/recur].

 @(examples
   (equal?/recur 1 1 (lambda (a b) #f))
   (equal?/recur '(1) '(1) (lambda (a b) #f))
   (equal?/recur '#(1 1 1) '#(1 1.2 3/4)
                 (lambda (a b) (<= (abs (- a b)) 0.25))))}


@section[#:tag "model-eq"]{Object Identity and Comparisons}


The @racket[eq?] operator compares two @tech{values}, returning
@racket[#t] when the values refer to the same @tech{object}. This form
of equality is suitable for comparing objects that support imperative
update (e.g., to determine that the effect of modifying an object
through one reference is visible through another reference). Also, an
@racket[eq?] test evaluates quickly, and @racket[eq?]-based hashing
is more lightweight than @racket[equal?]-based hashing in hash tables.

In some cases, however, @racket[eq?] is unsuitable as a comparison
operator, because the generation of @tech{objects} is not clearly
defined. In particular, two applications of @racket[+] to the same two
exact integers may or may not produce results that are @racket[eq?],
although the results are always @racket[equal?]. Similarly, evaluation
of a @racket[lambda] form typically generates a new procedure
@tech{object}, but it may re-use a procedure @tech{object} previously
generated by the same source @racket[lambda] form.

The behavior of a datatype with respect to @racket[eq?] is generally
specified with the datatype and its associated procedures.


@section{Equality and Hashing}


All comparable values have at least one @deftech{hash code} --- an arbitrary
integer (more specifically a @tech{fixnum}) computed by applying a hash function
to the value. The defining property of these hash codes is that @bold{equal
 values have equal hash codes}. Note that the reverse is not true: two unequal
values can still have equal hash codes. Hash codes are useful for various
indexing and comparison operations, especially in the implementation of
@tech{hash tables}. See @secref["hashtables"] for more information.


@defproc[(equal-hash-code [v any/c]) fixnum?]{

 Returns a @tech{hash code} consistent with @racket[equal?]. For any two calls
 with @racket[equal?] values, the returned number is the same. A hash code is
 computed even when @racket[v] contains a cycle through pairs, vectors, boxes,
 and/or inspectable structure fields. Additionally, user-defined data types can
 customize how this hash code is computed by implementing
 @racket[gen:equal+hash].

 For any @racket[v] that could be produced by @racket[read], if @racket[v2] is
 produced by @racket[read] for the same input characters, the
 @racket[(equal-hash-code v)] is the same as @racket[(equal-hash-code v2)] ---
 even if @racket[v] and @racket[v2] do not exist at the same time (and therefore
 could not be compared by calling @racket[equal?]).

 @history[
 #:changed "6.4.0.12"
 @elem{Strengthened guarantee for @racket[read]able values.}]}


@defproc[(equal-secondary-hash-code [v any/c]) fixnum?]{

 Like @racket[equal-hash-code], but computes a secondary @tech{hash code}
 suitable for use in double hashing.}


@defproc[(eq-hash-code [v any/c]) fixnum?]{

 Returns a @tech{hash code} consistent with @racket[eq?]. For any two calls with
 @racket[eq?] values, the returned number is the same.

 @margin-note{Equal @tech{fixnums} are always @racket[eq?].}}


@defproc[(eqv-hash-code [v any/c]) fixnum?]{

 Returns a @tech{hash code} consistent with @racket[eqv?]. For any two calls
 with @racket[eqv?] values, the returned number is the same.}


@section{Implementing Equality for Custom Types}


@defthing[gen:equal+hash any/c]{
 A @tech{generic interface} (see @secref["struct-generics"]) for types that can
 be compared for equality using @racket[equal?]. The following methods must be
 implemented:

 @itemize[

 @item{@racket[_equal-proc :
               (any/c any/c (any/c any/c . -> . boolean?)  . -> . any/c)] ---
   tests whether the first two arguments are equal, where both values are
   instances of the structure type to which the generic interface is associated
   (or a subtype of the structure type).

   The third argument is an @racket[equal?]  predicate to use for
   recursive equality checks; use the given predicate instead of
   @racket[equal?] to ensure that data cycles are handled
   properly and to work with @racket[equal?/recur] (but beware
   that an arbitrary function can be provided to
   @racket[equal?/recur] for recursive checks, which means that
   arguments provided to the predicate might be exposed to
   arbitrary code).

   The @racket[_equal-proc] is called for a pair of structures
   only when they are not @racket[eq?], and only when they both
   have a @racket[gen:equal+hash] value inherited from the same
   structure type. With this strategy, the order in which
   @racket[equal?] receives two structures does not matter. It
   also means that, by default, a structure sub-type inherits the
   equality predicate of its parent, if any.}

 @item{@racket[_hash-proc :
               (any/c (any/c . -> . exact-integer?) . -> . exact-integer?)] ---
   computes a hash code for the given structure, like @racket[equal-hash-code].
   The first argument is an instance of the structure type (or one of its
   subtypes) to which the generic interface is associated.

   The second argument is an @racket[equal-hash-code]-like procedure to use for
   recursive hash-code computation; use the given procedure instead of
   @racket[equal-hash-code] to ensure that data cycles are handled properly.

   Although the result of @racket[_hash-proc] can be any exact
   integer, it will be truncated for most purposes to a @tech{fixnum}
   (e.g., for the result of @racket[equal-hash-code]). Roughly,
   truncation uses @racket[bitwise-and] to take the lower bits of the
   number. Thus, variation in the hash-code computation should be
   reflected in the fixnum-compatible bits of @racket[_hash-proc]'s
   result. Consumers of a hash code are expected to use variation
   within the fixnum range appropriately, and producers are @emph{not}
   responsible to reflect variation in hash codes across the full
   range of bits that fit within a fixnum.}

 @item{@racket[_hash2-proc :
               (any/c (any/c . -> . exact-integer?) . -> . exact-integer?)] ---
   computes a secondary hash code for the given structure. This procedure is
   like @racket[_hash-proc], but analogous to
   @racket[equal-secondary-hash-code].}]

 Take care to ensure that @racket[_hash-proc] and @racket[_hash2-proc]
 are consistent with @racket[_equal-proc]. Specifically,
 @racket[_hash-proc] and @racket[_hash2-proc] should produce the same
 value for any two structures for which @racket[_equal-proc] produces a
 true value.

 When a structure type has no @racket[gen:equal+hash] implementation, then
 transparent structures (i.e., structures with an @tech{inspector} that
 is controlled by the current @tech{inspector}) are @racket[equal?]
 when they are instances of the same structure type (not counting
 sub-types), and when they have @racket[equal?] field values.  For
 transparent structures, @racket[equal-hash-code] and
 @racket[equal-secondary-hash-code] derive hash code using the field
 values. For opaque structure types, @racket[equal?] is the same as
 @racket[eq?], and @racket[equal-hash-code] and
 @racket[equal-secondary-hash-code] results are based only on
 @racket[eq-hash-code]. If a structure has a @racket[prop:impersonator-of]
 property, then the @racket[prop:impersonator-of] property takes precedence over
 @racket[gen:equal+hash] if the property value's procedure returns a
 non-@racket[#f] value when applied to the structure.

 @(examples
   (eval:no-prompt
    (define (farm=? farm1 farm2 recursive-equal?)
      (and (= (farm-apples farm1)
              (farm-apples farm2))
           (= (farm-oranges farm1)
              (farm-oranges farm2))
           (= (farm-sheep farm1)
              (farm-sheep farm2))))

    (define (farm-hash-code farm recursive-equal-hash)
      (+ (* 10000 (farm-apples farm))
         (* 100 (farm-oranges farm))
         (* 1 (farm-sheep farm))))

    (define (farm-secondary-hash-code farm recursive-equal-hash)
      (+ (* 10000 (farm-sheep farm))
         (* 100 (farm-apples farm))
         (* 1 (farm-oranges farm))))

    (struct farm (apples oranges sheep)
      #:methods gen:equal+hash
      [(define equal-proc farm=?)
       (define hash-proc  farm-hash-code)
       (define hash2-proc farm-secondary-hash-code)])

    (define eastern-farm (farm 5 2 20))
    (define western-farm (farm 18 6 14))
    (define northern-farm (farm 5 20 20))
    (define southern-farm (farm 18 6 14)))

   (equal? eastern-farm western-farm)
   (equal? eastern-farm northern-farm)
   (equal? western-farm southern-farm))}


@defthing[prop:equal+hash struct-type-property?]{

 A @tech{structure type property} (see @secref["structprops"])
 that supplies an equality predicate and hashing functions for a structure
 type. Using the @racket[prop:equal+hash] property is discouraged; the
 @racket[gen:equal+hash] @tech{generic interface} should be used instead.
 A @racket[prop:equal+hash] property value is a list of three procedures
 that correspond to the methods of @racket[gen:equal+hash]:

 @itemize[
 @item{@racket[_equal-proc :
               (any/c any/c (any/c any/c . -> . boolean?)  . -> . any/c)]}

 @item{@racket[_hash-proc :
               (any/c (any/c . -> . exact-integer?) . -> . exact-integer?)]}

 @item{@racket[_hash2-proc :
               (any/c (any/c . -> . exact-integer?) . -> . exact-integer?)]}]}