Common Lisp the Language, 2nd Edition

Next: Logical Operators Up: Predicates Previous: Specific Data Type

# 6.3. Equality Predicates

Common Lisp provides a spectrum of predicates for testing for equality of two objects: `eq` (the most specific), `eql`, `equal`, and `equalp` (the most general). `eq` and `equal` have the meanings traditional in Lisp. `eql` was added because it is frequently needed, and `equalp` was added primarily in order to have a version of `equal` that would ignore type differences when comparing numbers and case differences when comparing characters. If two objects satisfy any one of these equality predicates, then they also satisfy all those that are more general.

[Function]
`eq` `x` `y`

`(eq x y)` is true if and only if x and y are the same identical object. (Implementationally, x and y are usually `eq` if and only if they address the same identical memory location.)

It should be noted that things that print the same are not necessarily `eq` to each other. Symbols with the same print name usually are `eq` to each other because of the use of the `intern` function. However, numbers with the same value need not be `eq`, and two similar lists are usually not `eq`. For example:

    (eq 'a 'b) is false.
    (eq 'a 'a) is true.
    (eq 3 3) might be true or false, depending on the implementation.
    (eq 3 3.0) is false.
    (eq 3.0 3.0) might be true or false, depending on the implementation.
    (eq #c(3 -4) #c(3 -4))
      might be true or false, depending on the implementation.
    (eq #c(3 -4.0) #c(3 -4)) is false.
    (eq (cons 'a 'b) (cons 'a 'c)) is false.
    (eq (cons 'a 'b) (cons 'a 'b)) is false.
    (eq '(a . b) '(a . b)) might be true or false.
    (progn (setq x (cons 'a 'b)) (eq x x)) is true.
    (progn (setq x '(a . b)) (eq x x)) is true.
    (eq #\A #\A) might be true or false, depending on the implementation.
    (eq "Foo" "Foo") might be true or false.
    (eq "Foo" (copy-seq "Foo")) is false.
    (eq "FOO" "foo") is false.

In Common Lisp, unlike some other Lisp dialects, the implementation is permitted to make ``copies'' of characters and numbers at any time. (This permission is granted because it allows tremendous performance improvements in many common situations.) The net effect is that Common Lisp makes no guarantee that `eq` will be true even when both its arguments are ``the same thing'' if that thing is a character or number. For example:

    (let ((x 5)) (eq x x)) might be true or false.

The predicate `eql` is the same as `eq`, except that if the arguments are characters or numbers of the same type then their values are compared. Thus `eql` tells whether two objects are conceptually the same, whereas `eq` tells whether two objects are implementationally identical. It is for this reason that `eql`, not `eq`, is the default comparison predicate for the sequence functions defined in chapter 14.

Implementation note: `eq` simply compares the two given pointers, so any kind of object that is represented in an ``immediate'' fashion will indeed have like-valued instances satisfy `eq`. In some implementations, for example, fixnums and characters happen to ``work.'' However, no program should depend on this, as other implementations of Common Lisp might not use an immediate representation for these data types.

An additional problem with `eq` is that the implementation is permitted to ``collapse'' constants (or portions thereof) appearing in code to be compiled if they are `equal`. An object is considered to be a constant in code to be compiled if it is a self-evaluating form or is contained in a `quote` form. This is why `(eq "Foo" "Foo")` might be true or false; in interpreted code it would normally be false, because reading in the form `(eq "Foo" "Foo")` would construct distinct strings for the two arguments to `eq`, but the compiler might choose to use the same identical string or two distinct copies as the two arguments in the call to `eq`. Similarly, `(eq '(a . b) '(a . b))` might be true or false, depending on whether the constant conses appearing in the `quote` forms were collapsed by the compiler. However, `(eq (cons 'a 'b) (cons 'a 'b))` is always false, because every distinct call to the `cons` function necessarily produces a new and distinct cons.

X3J13 voted in March 1989 (QUOTE-SEMANTICS) to clarify that `eval` and `compile` are not permitted either to copy or to coalesce (``collapse'') constants (see `eq`) appearing in the code they process; the resulting program behavior must refer to objects that are `eql` to the corresponding objects in the source code. Only the `compile-file`/`load` process is permitted to copy or coalesce constants (see section 25.1).

[Function]
`eql` `x` `y`

The `eql` predicate is true if its arguments are `eq`, or if they are numbers of the same type with the same value, or if they are character objects that represent the same character. For example:

    (eql 'a 'b) is false.
    (eql 'a 'a) is true.
    (eql 3 3) is true.
    (eql 3 3.0) is false.
    (eql 3.0 3.0) is true.
    (eql #c(3 -4) #c(3 -4)) is true.
    (eql #c(3 -4.0) #c(3 -4)) is false.
    (eql (cons 'a 'b) (cons 'a 'c)) is false.
    (eql (cons 'a 'b) (cons 'a 'b)) is false.
    (eql '(a . b) '(a . b)) might be true or false.
    (progn (setq x (cons 'a 'b)) (eql x x)) is true.
    (progn (setq x '(a . b)) (eql x x)) is true.
    (eql #\A #\A) is true.
    (eql "Foo" "Foo") might be true or false.
    (eql "Foo" (copy-seq "Foo")) is false.
    (eql "FOO" "foo") is false.

Normally `(eql 1.0s0 1.0d0)` would be false, under the assumption that `1.0s0` and `1.0d0` are of distinct data types. However, implementations that do not provide four distinct floating-point formats are permitted to ``collapse'' the four formats into some smaller number of them; in such an implementation `(eql 1.0s0 1.0d0)` might be true. The predicate `=` will compare the values of two numbers even if the numbers are of different types.

If an implementation supports positive and negative zeros as distinct values (as in the IEEE proposed standard floating-point format), then `(eql 0.0 -0.0)` will be false. Otherwise, when the syntax `-0.0` is read it will be interpreted as the value `0.0`, and so `(eql 0.0 -0.0)` will be true. The predicate `=` differs from `eql` in that `(= 0.0 -0.0)` will always be true, because `=` compares the mathematical values of its operands, whereas `eql` compares the representational values, so to speak.

Two complex numbers are considered to be `eql` if their real parts are `eql` and their imaginary parts are `eql`. For example, `(eql #C(4 5) #C(4 5))` is true and `(eql #C(4 5) #C(4.0 5.0))` is false. Note that while `(eql #C(5.0 0.0) 5.0)` is false, `(eql #C(5 0) 5)` is true. In the case of `(eql #C(5.0 0.0) 5.0)` the two arguments are of different types and so cannot satisfy `eql`; that's all there is to it. In the case of `(eql #C(5 0) 5)`, however, `#C(5 0)` is not a complex number but is always automatically reduced by the rule of complex canonicalization to the integer `5`, just as the apparent ratio `20/4` is always simplified to `5`.

The case of `(eql "Foo" "Foo")` is discussed above in the description of `eq`. While `eql` compares the values of numbers and characters, it does not compare the contents of strings. To compare the characters of two strings, one should use `equal`, `equalp`, `string=`, or `string-equal`.

Compatibility note: The Common Lisp function `eql` is similar to the Interlisp function `eqp`. However, `eql` considers `3` and `3.0` to be different, whereas `eqp` considers them to be the same; `eqp` behaves like the Common Lisp `=` function, not like `eql`, when both arguments are numbers.

[Function]
`equal` `x` `y`

The `equal` predicate is true if its arguments are structurally similar (isomorphic) objects. A rough rule of thumb is that two objects are `equal` if and only if their printed representations are the same.

Numbers and characters are compared as for `eql`. Symbols are compared as for `eq`. This method of comparing symbols can violate the rule of thumb for `equal` and printed representations, but only in the infrequently occurring case of two distinct symbols with the same print name.

Certain objects that have components are `equal` if they are of the same type and corresponding components are `equal`. This test is implemented in a recursive manner and may fail to terminate for circular structures.

For conses, `equal` is defined recursively as the two car's being `equal` and the two cdr's being `equal`.

Two arrays are `equal` only if they are `eq`, with one exception: strings and bit-vectors are compared element-by-element. If either argument has a fill pointer, the fill pointer limits the number of elements examined by `equal`. Uppercase and lowercase letters in strings are considered by `equal` to be distinct. (In contrast, `equalp` ignores case distinctions in strings.)

Compatibility note: In Lisp Machine Lisp, `equal` ignores the difference between uppercase and lowercase letters in strings. This violates the rule of thumb about printed representations, however, which is very useful, especially to novices. It is also inconsistent with the treatment of single characters, which in Lisp Machine Lisp are represented as fixnums.

Two pathname objects are `equal` if and only if all the corresponding components (host, device, and so on) are equivalent. (Whether or not uppercase and lowercase letters are considered equivalent in strings appearing in components depends on the file name conventions of the file system.) Pathnames that are `equal` should be functionally equivalent.

X3J13 voted in June 1989 (EQUAL-STRUCTURE) to clarify that `equal` never recursively descends any structure or data type other than the ones explicitly described above: conses, bit-vectors, strings, and pathnames. Numbers and characters are compared as if by `eql`, and all other data objects are compared as if by `eq`.

    (equal 'a 'b) is false.
    (equal 'a 'a) is true.
    (equal 3 3) is true.
    (equal 3 3.0) is false.
    (equal 3.0 3.0) is true.
    (equal #c(3 -4) #c(3 -4)) is true.
    (equal #c(3 -4.0) #c(3 -4)) is false.
    (equal (cons 'a 'b) (cons 'a 'c)) is false.
    (equal (cons 'a 'b) (cons 'a 'b)) is true.
    (equal '(a . b) '(a . b)) is true.
    (progn (setq x (cons 'a 'b)) (equal x x)) is true.
    (progn (setq x '(a . b)) (equal x x)) is true.
    (equal #\A #\A) is true.
    (equal "Foo" "Foo") is true.
    (equal "Foo" (copy-seq "Foo")) is true.
    (equal "FOO" "foo") is false.

To compare a tree of conses using `eql` (or any other desired predicate) on the leaves, use `tree-equal`.

[Function]
`equalp` `x` `y`

Two objects are `equalp` if they are `equal`; if they are characters and satisfy `char-equal`, which ignores alphabetic case and certain other attributes of characters; if they are numbers and have the same numerical value, even if they are of different types; or if they have components that are all `equalp`.

Objects that have components are `equalp` if they are of the same type and corresponding components are `equalp`. This test is implemented in a recursive manner and may fail to terminate for circular structures. For conses, `equalp` is defined recursively as the two car's being `equalp` and the two cdr's being `equalp`.

Two arrays are `equalp` if and only if they have the same number of dimensions, the dimensions match, and the corresponding components are `equalp`. The specializations need not match; for example, a string and a general array that happens to contain the same characters will be `equalp` (though definitely not `equal`). If either argument has a fill pointer, the fill pointer limits the number of elements examined by `equalp`. Because `equalp` performs element-by-element comparisons of strings and ignores the alphabetic case of characters, case distinctions are therefore also ignored when `equalp` compares strings.

Two symbols can be `equalp` only if they are `eq`, that is, the same identical object.

X3J13 voted in June 1989 (EQUAL-STRUCTURE) to specify that `equalp` compares components of hash tables (see below), and to clarify that otherwise `equalp` never recursively descends any structure or data type other than the ones explicitly described above: conses, arrays (including bit-vectors and strings), and pathnames. Numbers are compared for numerical equality (see `=`), characters are compared as if by `char-equal`, and all other data objects are compared as if by `eq`.

Two hash tables are considered the same by `equalp` if and only if they satisfy a four-part test:

- They must be of the same kind; that is, equivalent `:test` arguments were given to `make-hash-table` when the two hash tables were created.

- They must have the same number of entries (see `hash-table-count`).

- For every entry (key1, value1) in one hash table there must be a corresponding entry (key2, value2) in the other, such that key1 and key2 are considered to be the same by the `:test` function associated with the hash tables.

- For every entry (key1, value1) in one hash table and its corresponding entry (key2, value2) in the other, such that key1 and key2 are the same, `equalp` must be true of value1 and value2.

The four parts of this test are carried out in the order shown, and if some part of the test fails, `equalp` returns `nil` and the other parts of the test are not attempted.

If `equalp` must compare two structures and the `defstruct` definition for one used the `:type` option and the other did not, then `equalp` returns `nil`.

If `equalp` must compare two structures and neither `defstruct` definition used the `:type` option, then `equalp` returns `t` if and only if the structures have the same type (that is, the same `defstruct` name) and the values of all corresponding slots (slots having the same name) are `equalp`.

As part of the X3J13 discussion of this issue the following observations were made. Object equality is not a concept for which there is a uniquely determined correct algorithm. The appropriateness of an equality predicate can be judged only in the context of the needs of some particular program. Although these functions take any type of argument and their names sound very generic, `equal` and `equalp` are not appropriate for every application. Any decision to use or not use them should be determined by what they are documented to do rather than by any abstract characterization of their function. If neither `equal` nor `equalp` is found to be appropriate in a particular situation, programmers are encouraged to create another operator that is appropriate rather than blame `equal` or `equalp` for ``doing the wrong thing.''

Note that one consequence of the vote to change the rules of floating-point contagion (CONTAGION-ON-NUMERICAL-COMPARISONS) (described in section 12.1) is to make `equalp` a true equivalence relation on numbers.

    (equalp 'a 'b) is false.
    (equalp 'a 'a) is true.
    (equalp 3 3) is true.
    (equalp 3 3.0) is true.
    (equalp 3.0 3.0) is true.
    (equalp #c(3 -4) #c(3 -4)) is true.
    (equalp #c(3 -4.0) #c(3 -4)) is true.
    (equalp (cons 'a 'b) (cons 'a 'c)) is false.
    (equalp (cons 'a 'b) (cons 'a 'b)) is true.
    (equalp '(a . b) '(a . b)) is true.
    (progn (setq x (cons 'a 'b)) (equalp x x)) is true.
    (progn (setq x '(a . b)) (equalp x x)) is true.
    (equalp #\A #\A) is true.
    (equalp "Foo" "Foo") is true.
    (equalp "Foo" (copy-seq "Foo")) is true.
    (equalp "FOO" "foo") is true.

Next: Logical Operators Up: Predicates Previous: Specific Data Type