common-lisp Equality and other comparison predicates Structural equality with EQUAL, EQUALP, TREE-EQUAL

Example

These three operators implement structural equivalence, that is they check if different, complex objects have equivalent structure with equivalent component.

EQUAL behaves like EQL for non-structured data, while for structures built by conses (lists and trees), and the two special types of arrays, strings and bit vectors, it performs structural equivalence, returning true on two structures that are isomorphic and whose elementary components are correspondingly equal by EQUAL. For instance:

(equal (list 1 (cons 2 3)) (list 1 (cons 2 (+ 2 1))))
T ;; => since the two arguments are both equal to (1 (2 . 3))
(equal "ABC" "ABC")
T ;; => equality on strings
(equal "Abc" "ABC")
NIL ;; => case sensitive equality on strings
(equal '(1 . "ABC") '(1 . "ABC"))
T ;; => equal since it uses EQL on 1 and 1, and EQUAL on "ABC" and "ABC"
(let* ((a (make-array 3 :initial-contents '(1 2 3)))
       (b (make-array 3 :initial-contents '(1 2 3)))
       (c a))
  (values (equal a b)
          (equal a c)))
NIL ;; => the structural equivalence is not used for general arrays
T   ;; => a and c are alias for the same object, so it is like EQL

EQUALP returns true on all cases in which EQUAL is true, but it uses also structural equivalence for arrays of any kind and dimension, for structures and for hash tables (but not for class instances!). Moreover, it uses case insensitive equivalence for strings.

(equalp "Abc" "ABC")
T ;; => case insensitive equality on strings
(equalp (make-array 3 :initial-contents '(1 2 3))
        (make-array 3 :initial-contents (list 1 2 (+ 2 1))))
T ;; => the structural equivalence is used also for any kind of arrays
(let ((hash1 (make-hash-table))
      (hash2 (make-hash-table)))
      (setf (gethash 'key hash1) 42)
      (setf (gethash 'key hash2) 42)
      (print (equalp hash1 hash2))
      (setf (gethash 'another-key hash1) 84)
      (equalp hash1 hash2))   
T   ;; => after the first two insertions, hash1 and hash2 have the same keys and values
NIL ;; => after the third insertion, hash1 and hash2 have different keys and values
(progn (defstruct s) (equalp (make-s) (make-s)))
T ;; => the two values are structurally equal
(progn (defclass c () ()) (equalp (make-instance 'c) (make-instance 'c)))
NIL ;; => two structurally equivalent class instances returns NIL, it's up to the user to
    ;;    define an equality method for classes

Finally, TREE-EQUAL can be applied to structures built through consand checks if they are isomorphic, like EQUAL, but leaving to the user the choice of which function to use to compare the leafs, i.e. the non-cons (atom) encountered, that can be of any other data type (by default, the test used on atom is EQL). For instance:

(let ((l1 '(1 . ("A" . 2)))
      (l2 '(1 . ("A" . 2))))
  (tree-equal l1 l2 :test #'eql))
NIL ;; => since (eql "A" "A") gives NIL
(let ((l1 '(1 . ("A" . 2)))
      (l2 '(1 . ("A" . 2))))
  (tree-equal l1 l2 :test #'equal))
T ;; since (equal "A" "A") gives T