0

In continuation to my previous post on intersection(How to take intersection of pairs from two lists in scheme?), I have written a small code for union along the same lines. The output should be like: (union '((1 2)(2 1)) '((1 3)(3 4))) -- '((1 5)(2 1)(3 4)). However, the output of my program is not exactly what I want. I think my recursion or conditions need some guidance. Please help. Thanks.

(define union
  (lambda (set1 set2)
    (let ((newlist '()))
      (cond ((null? set1) set2)
            ((null? set2) set1)
            ((eq? (caar set1) (caar set2))
             (append newlist (cons (caar set1) (+ (cadr (car set1))(cadr (car set2))))))
            (else 
             (if (> (caar set1) (caar set2))(append newlist (car set1)) (union (cdr set1) set2))
             (union set1 (cdr set2)))))))
Community
  • 1
  • 1
far_kurt
  • 39
  • 2
  • 6

1 Answers1

1

1) eq? only returns true if the two arguments are the exact same object. You'll want to use equal?, or = if you're only comparing numbers.

2) Even with your recursion, newlist is constantly empty, no matter what you do. You're just appending an empty list in the last two cases.

3) This isn't actually union. You're looking for some special behavior when '(1 2) and '(1 3) become '(1 5).

This is what you want, however. We are operating based on the assumption that your list is presorted, considering you threw in < and > and that there were no duplicates within the individual sets (e.g. '((1 2) (1 2) (3 4)):

(define (union set1 set2)
  (cond [(empty? set1) set2]
        [(empty? set2) set1]
        [(equal? (car set1) (car set2)) (cons (car set1) 
                                              (union (cdr set1) (cdr set2)))]
        [(= (caar set1) (caar set2)) (cons (list (caar set1)
                                                 (+ (cadar set1)
                                                    (cadar set2)))
                                           (union (cdr set1) (cdr set2)))]
        [(< (caar set1) (caar set2)) (cons (car set1) (union (cdr set1)
                                                             set2))]
        [else (cons (car set2) (union set1
                                      (cdr set2)))]))

Logic:

1) Is one or the other empty? If so, return the appropriate set.

2) Is the first list in one set equal to the first list in the other set? If so, (cons) the shared list onto the result of passing the rest of both sets back into union.

3) Is the first element in the first list of both sets equal? If so, (cons) the list containing the common first element and the summed second elements onto the result of passing the rest of both sets back into the union.

4) The last two steps perform similar actions as the first. Take the set with the lesser first element, (cons) it onto the result of passing the two sets, minus the list you just extracted, back into union.

You can optimize with binding local definitions on repeats, but hopefully this allows you to understand your issues and where you may have gone wrong.

ಠ_ಠ
  • 3,060
  • 28
  • 43
  • this doesn't work when two pairs are exactly equal. (union '((1 2)(2 1)) '((2 1))) -- '((1 2)(2 1)), should be '((1 2)(2 2)). Thanks a lot. – far_kurt Aug 08 '13 at 19:58
  • 1
    Why? The logic for the problem you have is strange. Regardless, you should be able to modify and remove cases as necessary. I wrote the code to be easy to modify. – ಠ_ಠ Aug 08 '13 at 20:01
  • yea. :) i think equal? statement need to compare first elements of the pairs than the exact pairs. Thanks. – far_kurt Aug 08 '13 at 20:05
  • They probably didn't understand the strange logic required for these unions and intersections. Try updating the post with specific examples (aka these inputs should produce this output) for all the different cases so that there is a full understanding. – ಠ_ಠ Aug 09 '13 at 00:17
  • thanks much. I got it. :D just needed a condition correction. Thanks a lot. :) – far_kurt Aug 09 '13 at 00:23
  • @user2662909 now try and optimize it! – ಠ_ಠ Aug 09 '13 at 00:42