equal? predicate for lists

Question

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?

Answer 1

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.