sicp-ex-2.54

 ;; 2.54 
  
  
 ;; a equal? b if, and only if: 
 ;; either eq? a and b, or  
 ;; a and b are both pairs or they are both nil,  
         ;; and (car a) equal? (car b), and (cdr a) equal? (cdr b) 
 (define (equal? a b) 
     (if (or 
             (eq? a b) 
             (and  
                 (or  
                     (and  
                         (pair? a)  
                         (pair? b))  
                     (and  
                         (null? a)  
                         (null? b))) 
                 (and  
                     (equal? (car a) (car b))  
                     (equal? (cdr a) (cdr b)))))  
         #t #f)) 
  

 ;; 2.54 
  
 ;;; the above solution works, but a good rule of thumb is that any time you have  
 ;;; the pattern "if <a> then <true> else <false>", you can replace the whole 
 ;;; thing by <a>, so andras' solution becomes: 
  
 (define (equal2? a b) 
     (or 
      (eq? a b) 
      (and  
       (or  
        (and  
         (pair? a)  
         (pair? b))  
        (and  
         (null? a)  
         (null? b))) 
       (and  
        (equal? (car a) (car b))  
        (equal? (cdr a) (cdr b))))))  
  
 ;;; I also coded a version which is a little less booleany -- it seems clearer to me,  
 ;;; but perhaps that's just because I wrote it.  ;-) 
  
 (define (equal3? l1 l2) 
   (if (and (pair? l1) (pair? l2)) 
       (cond ((null? l1) (null? l2)) 
             ((null? l2) false) 
             ((equal2? (car l1) (car l2)) (equal2? (cdr l1) (cdr l2))) 
             (else false)) 
       (eq? l1 l2))) 
           

 ;; 2.54 
  
 ;whilst the above two solutions are correct, I find them rather counterintuitive 
 ;at first sight 
 ;it seems like eq? actually handles the cases where: 
 ; one of the operands is '() or nill, as well as only one of the operands being a pair 
 ; thus checking for these cases is unnecessary 
  
 (define (equal2? a b) 
   (if (and (pair? a) (pair? b)) 
       (and (equal2? (car a) (car b)) (equal2? (cdr a) (cdr b))) 
       (eq? a b))) 

The answer is relevant the to the procedure eq? In my IDE: DrRacket 5.1. eq? can do everything described by the question 2.54, so we can use (eq? list1 list2) to solve the problem. If we just think eq? is used to check symbols. the following code works.

 (define (equal1? x y) 
   (cond ((and (null? x) (null? y)) #t) 
         ((and (symbol? x) (symbol? y)) (eq? x y)) 
         ((and (pair? x) (pair? y)  
               (equal1? (car x) (car y)) (equal1? (cdr x ) (cdr y))) #t) 
         (else #f))) 

I find the following easier to follow...

  
 (define (equal? list1 list2) 
   (cond ((and (null? list1) (null? list2)) true) 
         ((or (null? list1) (null? list2)) false) 
         ((not (eq? (car list1) (car list2))) false) 
         (else (equal? (cdr list1) (cdr list2))))) 

I thought the following would work, but it triggers an error related to use of macro name as a variable on Gambit Scheme:

 (define (equal1? list1 list2) 
   (accumulate and #t (map eq? list1 list2))) 

So I settled with this, which I find more concise, albeit not the most efficient:

 (define (equal1? list1 list2) 
   (accumulate (lambda (x y) (and x y)) #t (map eq? list1 list2))) 

 
 Interesting exercise.

 (define (equal? L1 L2) 
   (cond ((and (pair? L1) 
               (pair? L2)) (if (eq? (car L1) (car L2)) 
                                (equal? (cdr L1) (cdr L2)) 
                                false)) 
         ((and (not (pair? L1)) 
               (not (pair? L2))) (eq? L1 L2)) 
         (else false))) 
  
 (equal? '(this is a list) '(this is a list)) ;; true 
 (equal? '(this is a list) '(this (is a) list)) ;; false 

this shouldn't be used to compare lists containing numbers

 (define (my-equal? a b)   
   (if (and (pair? a) (pair? b) (eq? (car a) (car b))) 
       (my-equal? (cdr a) (cdr b)) 
       (eq? a b))) 

@palatin 's solution is wrong.

e.g. (equal1? '(1 2 3) '(1 2 3 4)) => #t

which is obviously incorrect.

I find this solution to be much easier to understand.

  
 (define (equal? lat1 lat2) 
   (define (lists-empty?) 
     (and (null? lat1) (null? lat2))) 
  
   (define (either-list-empty?) 
     (or (null? lat1) (null? lat2))) 
  
   (cond ((lists-empty?) #t) 
         ((either-list-empty?) #f) 
         ((eq? (car lat1) (car lat2)) (equal? (cdr lat1) (cdr lat2))))) 

Naturally, I find my solution easiest to understand

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

Reduce more lines

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