SICP Exercise 2.54

2023-01-22

Question

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.

Answer

The following procedure works:

(define (equal? list_1 list_2)
  (cond ((and (null? list_1) (null? list_2)) true)
        ((or (null? list_1) (null? list_2)) false)
        ((eq? (car list_1) (car list_2))
         (equal? (cdr list_1) (cdr list_2)))
        (else false)))

This checks first if both lists are null, in which case they are either null in the first place or we passed the final iteration. In both cases, we can return true. If only one of the lists is null, the lengths must be different and therefore the lists are not equal, so false is returned.

Then we compare the car of both lists and if they are the same, recursively call the function on the cdrs.