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.