equal? predicate for lists

Exercise 2.54


Two lists are said to
be equal? if they contain equal
elements arranged in the same order.


For example,

(equal? '(this is a list) '(this is a list))

is true, but

(equal? '(this is a list) '(this (is a) list))

is false. To be more precise, we can
define equal? recursively in terms of
the basic eq? equality of symbols by
saying that a and b are equal? if they
are both symbols and the symbols are
eq?, or if they are both lists such
that (car a) is equal? to (car b) and
(cdr a) is equal? to (cdr b). Using
this idea, implement equal? as a
procedure.

I wrote the following:

(define (equal? a b)
  (or (and (and (symbol? a) (symbol? b)) (eq? a b))
      (and (null? a) (null? b))
      (and (and (and (not (null? a)) 
                     (list? a))
                (and (not (null? b))
                     (list? b)))
           (and (equal? (car a) (car b))
                (equal? (cdr a) (cdr b))))))

Can this be improved?

Since the and operation is associative, one could write:

(and (and (symbol? a) (symbol? b)) (eq? a b))

as:

(and (symbol? a) (symbol? b) (eq? a b))

Similarly:

(and (and (and (not (null? a)) 
               (list? a))
          (and (not (null? b))
               (list? b)))
     (and (equal? (car a) (car b))
          (equal? (cdr a) (cdr b))))

is equivalent to:

(and (not (null? a))
     (not (null? b))
     (list? a)
     (list? b)
     (equal? (car a) (car b))
     (equal? (cdr a) (cdr b)))

One could extend the definition of equal? to work with both lists and pairs simply by changing the test list? to pair?. This also obviates the need to test for non-nullity within the same and clause.

Using the above guidelines, one may write a shorter definition thus:

(define (equal? a b)
  (or (and (symbol? a) (symbol? b) (eq? a b))
      (and (null? a) (null? b))
      (and (pair? a)
           (pair? b)
           (equal? (car a) (car b))
           (equal? (cdr a) (cdr b)))))

Conceptually, one may think of null, symbol, and pair as types. To test for equality of two objects, one needs to check that their types are the same and then test for equality in that type.

Thus, to test for equality, if we see that objects are symbols, test for eq?; if we see that objects are null, no further test is necessary so they're equal; if we see that objects are pairs, test for equality of car and cdr.

This insight allows one to extend the definition of equal? to other types (hash tables, vectors, etc.) if one should choose to do so in the future.

StackExchange Code Review Q#1996, answer score: 3