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
eqv?
,
or
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, equal?
considers
two strings with the same character sequence to be "the same," 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).