scheme word lists eq?

Question

i've got a problem: I need to find if list equal to the second one, for example:

(set%eq? '(1 2 3) '(1 2 3))     ===> #t

(set%eq? '(1 2 3) '(2 3 4))     ===> #f

That examples are correct in my program, but this one is not:

(set%eq? (quote ((quote one) (quote two) (quote three))) (quote ((quote one) (quote two) 
(quote three))))    ====> #f but i need #t

what's wrong? this is my program:

(define (set-eq? xs ys) 

(cond ((and (null? xs) (null? ys)) #t) 
       ((null? ys) #f) 
       ((eq? (car xs) (car ys)) (set-eq? (cdr xs) (cdr ys)))
       ((eq? (car xs) (car (reverse ys))) (set-eq? (cdr xs) (cdr (reverse ys))))
       (else #f)))

Answer 1

There are a couple of mistakes in the posted code, and FYI, the procedure tests whether two lists are equal, it's not really testing for equality between two sets:

(define (set-eq? xs ys)
  (cond ((and (null? xs) (null? ys)) #t)
        ((or (null? xs) (null? ys))  #f) ; missing case
        ((equal? (car xs) (car ys)) (set-eq? (cdr xs) (cdr ys))) ; use equal?
        ; deleted unnecessary case here. Anyway, why are you reversing the list?
        (else #f)))

Now this will work:

(set-eq? '(1 2 3) '(1 2 3))
=> #t

(set-eq? '(1 2 3) '(2 3 4))
=> #f

(set-eq? (quote ((quote one) (quote two) (quote three)))
         (quote ((quote one) (quote two) (quote three))))
=> #t

In fact, this will work, too:

(equal? '(1 2 3) '(1 2 3))
=> #t

(equal? '(1 2 3) '(2 3 4))
=> #f

(equal? (quote ((quote one) (quote two) (quote three)))
        (quote ((quote one) (quote two) (quote three))))
=> #t

...But this won't work, the lists are clearly different:

(set-eq? '(1 2 3 4) '(4 1 2 3)) 
=> #f

If you intended to test for equality between two sets, you have to completely rethink the algorithm. Here's an idea: write asubset? procedure that tests if a list is a subset of another list (that is: if all the elements in one list are contained in the other list), and then test whether (and (subset? l1 l2) (subset? l2 l1)) is true, if that happens, then they're equal according to the set definition of equality.

Answer 2

Base on the comments from OP it's clear that these are set-eq?

(set-eq? '(a b c) '(c b a)) ; ==> #t
(set-eq? '(a b c) '(b c a)) ; ==> #t
(set-eq? '() '())           ; ==> #t
(set-eq? '(a b) '(a b c))   ; ==> #f
(set-eq? '(a b c) '(a c))   ; ==> #f

If the lists are without duplicates one could iterate the first list and try to find it in the second. If found we recurse with the two lists without the match.

#!r6rs
(import (rnrs)
        (rnrs lists))

(define (set-eq? xs ys)
  (if (null? xs) 
      (null? ys) ; #t if both sets are empty, otherwise #f
      (let ((cur (car xs)))        
        (and (memq cur ys) ; first element is found 
             (set-eq? <??> (remq <??> <??>)))))) ; recurse without first in both lists

There are ways to get this faster. E.q. Hash the first list and iterate the second. If all matches and hashtable-size is the same as the number of iterations it's #t.