Equality Testing

1. Built-In Equality Predicates
2. Egal Operator
3. References

1. Built-In Equality Predicates

There are 5 equality predicates in Common Lisp:

eq tests if its arguments point to the same ["identical"] object;
- there is no guarantee this works on numbers, e.g., (eq 3 3) may or may not be true (it's implementation dependent)
eql is like eq but handles numbers (of the same type) being equal, and characters being equal
- (eql x y) is true when (eq x y) is true
- (eql 3 3) is true
- (eql 3 3.0) is false because 3 and 3.0 belong to different types
- (eql #\A #\A) is true
- (eql #\a #\A) is false (because eql is case-sensitive)
- (eql "foo" "foo") may or may not be true, it depends on the implementation
equal tests if two objects represent "the same" value
- For numbers, equal defers to eql; so (equal 3 3.0) is false because it evaluates to (eql 3 3.0)
- For lists, it checks if the car are equal, then checks if the cdr are equal
- For arrays, it checks equality using eq (i.e., they are pointers to the same object)
- For objects, it checks equality using eq
equalp an even more lenient version of equal
- Two instances of the same class are tested by recursively checking if each slot are equalp to each other; Warning: this may fail to terminate!
- Arrays should be tested using equalp
= tests if numbers are equal, regardless of type

2. Egal Operator

Henry Baker wrote a paper offering a rather robust equality predicate, introducing a function EGAL. The basic template is as follows:

  (defun egal (x y)
    (and (egal (type-of x) (type-of y))
         (cond ((symbolp x) (eq x y))
               ((numberp x) (egal-number x y))
               ((consp x) (eq x y))
               ((vectorp x) (egal-vector x y))
               ((functionp x) (egal-function x y))
               ((hash-table-p x) (egal-hashtable x y))
               ((streamp x) (egal-stream x y))
               ((mutable-structure-p x)
                (eq x y))
               (t (every #'(lambda (component)
                             (egal (funcall component x)
                                   (funcall component y)))
                         (components (type-of x)))))))

2.1. Numbers

Equality of numbers is rather involved. The biggest caveat is that the types must agree.

  (defun egal-number (x y)
    (and (egal (type-of x) (type-of y))
         (cond ((complexp x)
                (and (egal-number (realpart x) (realpart y))
                     (egal-number (imagpart x) (imagpart y))))
               ((rationalp x)
                (and (egal-number (numerator x) (numerator y))
                     (egal-number (denominator x) (denominator y))))
               ((floatp x)
                (and (= (float-sign x) (float-sign y)) ; for IEEE-75415
                     (= x y)))
               ((and (fixnump x) (fixnump y)) (eq x y))
               ((and (bignump x) (bignump y))
                (every #'eq (digits x) (digits y)))
               (t nil))))

2.2. Vectors and Strings

Equality of vectors is just boiling down to two case:

Mutable vectors refer to the same object in memory
Immutable vectors have the same length, and iterating through each pair of entries testing if they are EGAL or not.

Otherwise, the predicate is false.

  (defun egal-vector (x y)
    (cond ((and (mutable-vector-p x) (mutable-vector-p y))
           (eq x y))
          ((and (immutable-vector-p x) (immutable-vector-p y))
           (and (= (length x) (length y))
                (dotimes (i (length x) t)
                  (unless (egal (aref x i) (aref y i))
                    (return nil)))))
          (t nil)))

2.3. Function Equality

This is a nightmare, and doesn't seem tractable as Baker outlines it. Therefore, pointer equality seems best.

(defun egal-function (x y)
  (eq x y))

The original implementation checked if x and y were simple-function-p (which is not a well-defined predicate) and in that case, checks pointer equality.

For closures (there is a not-well-defined closure-p predicate), Baker checks if the funtion and the environments are equal.

2.4. Hash Tables

I just implement this using:

(defun egal-hashtable (x y)
  (and (= (hash-table-count x) (hash-table-count y))
       (with-hash-table-iterator (iterator x)
         (loop (multiple-value-bind (entry-p key value) (iterator)
                 (if entry-p
                     (unless (egal (gethash key y) value)
                       (return))
                     (return t)))))))

This is probably not as good as equalp.

2.5. Streams

I must admit I am not terribly familiar with the sordid details about streams and their implementation in Common Lisp. Therefore I must defer to pointer equality.

(defun egal-stream (x y)
  (eq x y))

3. References

Common Lisp: The Language, chapter 6, section 3
Eli Bendersky, Equality in Lisp. Blog post dated August 8, 2004.
Henry G. Baker,
"Equal Rights for Functional Objects or, The More Things Change, The More They Are the Same".
ACM OOPS Messenger 4,4 (Oct. 1993), 2-27. PDF.