SICP Exercise 2.54: Equal Lists

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.

The footnote in this exercise indicates that eq? may not be a reliable test of whether two numbers are equal. I.e. even if (= a b) evaluates to #t, you're not guaranteed that (eq? a b) will also evaluate to #t. Let's try to produce a solution that will not just cope with symbols correctly, but also numbers.

If we sneak a peak at the next sections in the book we're told about the predicates:

• number?, which identifies numbers ("The differentiation program with abstract data")
• symbol?, which identifies symbols ("Representing algebraic expressions")

If we extend the definition of equal? above so that it also includes the condition that if a and b are both numbers then a and b are equal? if the numbers are = then this should give us what we want.

We can then implement equal? as a cond expression, with a clause for each of the conditions we need to test for. Each clause's predicate needs to test that both a and b are of the same type and, if so, apply the appropriate logic to determine whether they're equal or not. We'll also need a final else clause that will catch all the cases where a and b are of different types - in these cases we know that a and b are not equal?, and so we can return #f.

Here's the procedure I produced:

(define (equal? a b)
  (cond ((and (pair? a) (pair? b))
           (and (equal? (car a) (car b)) (equal? (cdr a) (cdr b))))
        ((and (null? a) (null? b)) #t)
        ((and (number? a) (number? b)) (= a b))
        ((and (symbol? a) (symbol? b)) (eq? a b))
        (else #f)))

Let's give it a spin:

> (equal? '(this is a list) '(this is a list))
#t
> (equal? '(this is a list) '(this (is a) list))
#f
> (equal? (list 1 2 3 4) '(1 2 3 4))
#t
> (equal? (list 'a 'b 'c) '(a b c))
#t
> (equal? (list 1 2 'a 4) '(1 2 3 4))
#f