Is my solution to sicp exercise 2.54 right?

Question

I find this exercise is interesting. Here's my solution:

(define (my-equal? a b)
  (cond ((eq? a b) #t)
        ((and (pair? a) (pair? b))
         (and (my-equal? (car a) (car b)) (my-equal? (cdr a) (cdr b))))
        (else #f)))

Is it right ? I wonder if (eq? a b) is true, (equal? a b) should be always true.

"I wonder if (eq? a b) is true, (equal? a b) should be always true." Yes, that is correct. — leppie, Jun 25 '15 at 06:22
@leppie not necessarily, as argued in the link at the end of my answer — Óscar López, Jun 25 '15 at 16:07
@ÓscarLópez: Can you show an example where something is `eq?` but not `equal?` ? — leppie, Jun 25 '15 at 16:42
@leppie it depends on the interpreter, it's covered in the linked answer — Óscar López, Jun 25 '15 at 16:54
@ÓscarLópez: I cant see anything that would imply that. I know it is not required, but I would find it extremely odd if the implementor decided to not do it like that. — leppie, Jun 25 '15 at 16:58
@ÓscarLópez: Rereading the spec I found one :) It seems it is unspecified as `(let ((n (+ 2 3))) (eq? n n))` is unspecified and can be false due to optimizations, but it would be `equal?`. The compiler is free to turn it into `(eq? (+ 2 3) (+ 2 3))` which would be `#f` or `#t` depending on further optimizations (interning, constant folding). — leppie, Jun 25 '15 at 17:15
@ÓscarLópez: I would still find it odd for any implementation to return false for that — leppie, Jun 25 '15 at 17:23
@ÓscarLópez: The spec says if `eqv?` is false, `eq?` must be false too. If you flip that around (using simple boolean logic), it implies that if `eq?` is true, `eqv?` cannot be false. But `eq?` can be false where `eqv?` is true. (Scheme is hard! ;p) — leppie, Jun 25 '15 at 17:42

score 2 · Accepted Answer · edited May 23 '17 at 12:22

2

I think we can give a more accurate answer by considering other data types, and recursively testing the elements in proper/improper lists. Here's my shot:

(define (same-type? a b)
  (or (and (number? a) (number? b))
      (and (symbol? a) (symbol? b))
      (and (string? a) (string? b))
      (and (list? a) (list? b))
      (and (pair? a) (pair? b))))

(define (my-equal? a b)
  (cond ((not (same-type? a b)) #f)
        ((or (symbol? a) (null? a) (null? b))
         (eq? a b))
        ((list? a)
         (if (not (= (length a) (length b)))
             #f
             (and (my-equal? (car a) (car b))
                  (my-equal? (cdr a) (cdr b)))))
        ((pair? a)
         (and (my-equal? (car a) (car b))
              (my-equal? (cdr a) (cdr b))))
        ((string? a) (string=? a b))
        ((number? a) (= a b))))

For the last part of your question, I suggest you take a look at this very detailed answer.

edited May 23 '17 at 12:22

Community

1
1

answered Jun 25 '15 at 04:22

Óscar López

232,561
37
312
386

1

I see, but why compare types ? I think `eq?` will do it. – Zakilo Jun 25 '15 at 05:16
I mean I'm wondering the advantages of using `same-type?` here . Will it speed up the program or something ? – Zakilo Jun 25 '15 at 05:45
@Zakilo I'm comparing types because each data type has a different way of comparing for equality. And beware of using `eq?`, read the link at the end... – Óscar López Jun 25 '15 at 16:07
I got it . Besides, after `(define x 1) (define y x)`, I tested `(eq? x y)` return true, but `(my-equal? x y)` got an error. Your solution is still right. Thanks. – Zakilo Jun 26 '15 at 02:40

Is my solution to sicp exercise 2.54 right?

1 Answers1