How to write a “set-equal?” predicate?

Question

How do I build a same? predicate that returns #t with (same? '(4 6) '(6 4))? I'm stuck with writing a (same? a b)-predicate that returns #t if a and b are equal sets and #f otherwise. Also a similar predicate (element? el set) that determines if el is a element of set.

(And yes, this is homework so I'm not after a completely finished solution. I just need to get a bump or a few, in the right direction since there's almost no help to be found from our teachers.)

We are representing sets using lists. We are asked to build everything we need for this our selves. Higher order functions like map etc are pretty much banned.

The problem is that my element? and same? doesn't work with:

(same? '(4 6) '(6 4))<br/>
(element? '(2 3) '(1 8 5 '(3 2) 4))

These should return #t, which they don't and I understand why but I still can't fix it.

my element? looks like this, and I kind of knew it would only work for lists of the same order but the question is how I can improve it? (setEmpty, setFirst, setRest are defined as null?, car and cdr. We've been asked to make our own for some reason.)

(define element?
  (lambda (x set)
     (cond ((setEmpty? set) #f)
      ((equal? x (setFirst set)) #t)
      (else (element? x (setRest set)))
      )
   )
)

I have a working set?-predicate that looks like this, that might be of use:

(define set?
  (lambda (set)
    (cond ((setEmpty? set) #t)
          ((list? (setFirst set))
            (if (element? (setFirst set) (setRest set))
             #f
             (set? (setFirst set))))
          (else (if (element? (setFirst set) (setRest set))
                #f
                (set? (setRest set))
                )
            )
        )
     )
 )

This returns #t if a list and its "sublists" are without duplicates. I also have a procedure that makes a true set out of a list with duplicates that works fine.

Answer 1

My lab is actually running along smoothly now. I want to thank everyone that made a comment and mention a few things to others struggling with the same kind of implementation.

Pointers from my perspective: -Think abstractly. Read a quick intro to set theory. Just enough to know the defenitions of sets, subsets, the empty set, union etc.

-Write down all the procedures on a paper and think about what procedure that needs what other procedure.

-When thinking about how to write same? for example, imagine you have a procedure subset that already works. As a matter of fact, you already have alot of procedures that work, (even though you don't have them yet =) ) don't worry, just try and think what procedures same? would need to make it as neatly as possible. Continue like this for all your procedures.

-You might run in to problems with procedures just sending things back and forth between them and your program goes in to an infinite loop. If you're careful from the beginning and recognize when this prob could arise, you shouldn't run in to it. But occasionally you have to rethink some procedures. Maybe they can use other procedures to accomplish the same thing?

I'll also share a couple of procedures to see what you think. Feel free to butcher them, they work so far =) ..and it's due this friday anyway. ps. my proc makeSet basically does what it sounds like. It removes all duplicate elements in all "levels".

;;; predicate that returns #t if a list is a set and #f otherwise
(define set?
  (lambda (set)
    (cond ((setEmpty? set) #t)
      ((not (list? set)) #f)
      ((equal? (makeSet set) set) #t)
      (else #f))
  )
)

;;; diff returns the difference between set1 and set2
(define diff
  (lambda (set1 set2)
    (cond ((null? set1) '())
       ((null? set2) set1)
       ((not (member? (car set1) set2))
        (cons (car set1) (diff (cdr set1) set2)))
       (else (diff (cdr set1) set2)))
  )
)

Oh, and I haven't changed all the car, cdr and cons to our "abstracted" equals setFirst etc, I will. Also I might make diff return a "makeSet-version" of its return value to make sure I always get a set as a return.

Thanks again everyone! /rem

Answer 2

Note for Racket programmers: avoid reinventing the wheel if you can. If it's appropriate, use the standard library's racket/set, which provides a good set implementation.

Answer 3

A few pointers, to get you in the right direction.

The element? procedure is mostly right, except that it shouldn't use equal? for the key comparison - it should use same?, and same? should differentiate between two cases: whether the elements compared are atoms, or sets.

So it's not hard to imagine that the correctness of the whole exercise depends on the implementation of same?. And that in turn, depends on the chosen set representation. There's a whole chapter on representing sets in the wonderful book SICP (including representing sets as lists), you should start by reading it, to get your bearings.

Once you have implemented the primitive procedures for sets, it's easy to check if two sets are equal, I'll leave it to you to implement setSize and setUnion:

(= (setSize a) (setSize b) (setSize (setUnion a b)))

Or alternatively, as pointed by @sds in his answer, you can determine if two sets are the same if they're subsets of each other - and you should implement the subset? procedure on your own:

(and (subset? a b) (subset? b a))

Answer 4

Your problem seems to be that you are using equal? to compare set elements in element?.

You need to write your own element-equal? which would take into account that set elements may be lists and not atoms and use it instead of equal?.

As for same? - I think it would be easiest to implement it like this:

(define same? 
  (lambda (a b) 
    (and (subset? a b)
         (subset? b a))))

and

(define subset? 
  (lambda (a b)
    (or (isEmpty a)
        (and (element? (first a) b) 
             (subset? (rest a) b)))))