sicp-ex-2.54


 (define (equal? list1 list2) 
   (cond ((and (not (pair? list1)) (not (pair? list2))) 
          (eq? list1 list2)) 
         ((and (pair? list1) (pair? list2)) 
          (and (equal? (car list1) (car list2)) (equal? (cdr list1) (cdr list2)))) 
         (else false))) 
  
 (equal? '(1 2 3 (4 5) 6) '(1 2 3 (4 5) 6)) 
 ;Value: #t 
  
 (equal? '(1 2 3 (4 5) 6) '(1 2 3 (4 5 7) 6)) 
 ;Value: #f 

<< Previous exercise (2.53) | Index | Next exercise (2.55) >>


andras

 ;; 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)) 
  

miranda

 ;; 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))) 
           

vlad

 ;; 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))) 

meteorgan

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))) 

AMS

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))))) 

palatin

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))) 

Daniel-Amariei

 
 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 

atrika

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)))