Using Equality Predicates

Suppose that Scheme didn't provide the predicate equal? to do structural comparisons. We could write our own, because we have other type and equality predicates.

Let's write a simplified version of equal that works for lists, including nested lists. We'll consider objects to be our-equal? if they are either

• exactly the same objects or equivalent numbers, i.e., they're eqv?, or
• if they're both pairs whose cars are our-equal? and whose cdrs are also our-equal?.

That is, we'll test lists recursively for structural equivalence, "bottoming out" when we hit something that's not a pair. This is pretty much what the standard Scheme predicate equal? does, except that it can handle structured data types besides pairs. (For example, it considers two strings with the same character sequence equal?, even if they're two different objects.)

Scheme>(define (our-equal? a b)
          (cond ((eqv? a b)
                 #t)
                ((and (pair? a)
                      (pair? b)
                      (our-equal? (car a) (car b))
                      (our-equal? (cdr a) (cdr b)))
                 #t)
                (else
                 #f)))

This procedure checks the easy case first (which is usually a good idea): if two objects are eqv?, they're also our-equal?.

Otherwise, they're only our-equal? if they're both pairs and their cars are equal and their cdrs are equal. Notice the use of and here. We first check to see that they're pairs, and then take their cars and cdrs and compare those. If they're not pairs, we won't ever take their cars and cdrs. (If we did, it would be an error, but we rely on the fact that and tests things sequentially and stops when one test fails.)

Try it out:

Scheme>(our-equal? '() '())
#t
Scheme>(our-equal? 1 1)
#t
Scheme>(our-equal? 1 2)
#f
Scheme>(our-equal? '(1) '(1))
#t
Scheme>(our-equal? '(1) '())
#f
Scheme>(our-equal? '(1 (2)) '(1 (2)))
#t
Scheme>(our-equal? '(((3) 2) 1) '(((3) 2) (1)))
#f
Scheme>(our-equal? '((#f . #t) . (#f . #t))
                   '((#f . #t) . (#f . #t)))
#t

==================================================================
This is the end of Hunk H

At this point, you should go back to the previous chapter and
read Hunk I before returning here and continuing this tutorial.
==================================================================

(Go BACK to read Hunk I, which starts at section Choosing Equality Predicates (Hunk I).