1

I am using this script from The little schemer, to get intersection of two sets. But I am getting unbound identifier error at 'member?', can anyone please tell what's wrong with it:

(define intersect
  (lambda (set1 set2)
    (cond ((null? set1) (quote ()))
          ((member? (car set1) set2)
           (cons (car setl)
                 (intersect (cdr set1) set2)))
          (else (intersect (cdr setl) set2)))))

I was missing this function above:

(define member?
  (lambda (a lat)
    (cond ((null? lat) #f)
          (else (or (eq? (car lat) a)
                    (member? a (cdr lat)))))))

Also, I want to intersect two lists like: '((1 2)(2 7)) '((1 3)(4 5)) = '((1 5)), any suggestions on how to go about it? I am looking up the answers from this post: How to write a scheme function that takes two lists and returns four lists

Community
  • 1
  • 1
far_kurt
  • 39
  • 2
  • 6
  • It's not clear how those two lists "intersect" to produce `'((1 5))` – Óscar López Aug 08 '13 at 15:36
  • I am thinking to compare first element of each pair in 1st list w/ the first element of each pair in 2nd list and then add their 2nd element if match happens. :/ – far_kurt Aug 08 '13 at 15:40
  • 1
    You are sure about that behavior. (1 5) is neither in the first nor the second list.. `(intersect '((1 2)(3 4)(5 6)) '((9 10) (7 8) (5 6))) ==> ((5 6))` is correct understanding of intersection and the behaviour of your procedure. Your `member?` only need to use `equal?` instead of `eq?` and you are good to go. – Sylwester Aug 08 '13 at 15:43
  • Yes. I need to add the sec elements for pairs with same first element in the lists, and generate an output list accordingly. – far_kurt Aug 08 '13 at 15:47
  • Note: this function exists in the list SRFI library: http://docs.racket-lang.org/srfi-std/srfi-1.html#lset-intersection. For a production-quality set intersection, you'll probably want to use the dedicated set datatype instead of lists. http://docs.racket-lang.org/reference/sets.html#%28def._%28%28lib._racket%2Fset..rkt%29._set-intersect%29%29 – dyoo Aug 08 '13 at 18:11

2 Answers2

1

You have a typo in intersect where you have switched 1 with as lower case L. If you fix that your intersect seems fine by me if you are comparing symbols. Eg.

(define intersect
  (lambda (set1 set2)
    (cond
      ((null? set1)(quote ()))
      ((member? (car set1) set2)
       (cons (car set1)
             (intersect (cdr set1) set2)))
      (else (intersect (cdr set1) set2)))))

(intersect '(a b c d) '(c d e f)) ; ==> (c d)

To make it compare other things than symbols, you need to change your member? so that it uses equal? instead of eq?. It will be like this:

(define member?
  (lambda (a lat)
    (cond
      ((null? lat) #f)
      (else (or (equal? (car lat) a) ; changed eq? to equal? 
                (member? a (cdr lat)))))))

(intersect '((1 2)(3 4)(5 6)) '((9 10) (7 8) (5 6))) ; ==> ((5 6))

Even after this. The symbol version above still works. In any LISP (Common Lisp and Scheme at least) you have member. It uses equal and evaluate to false (whatever is false in the implementation) when it's not found and if it's found it evaluates to the rest of the argument list starting from where the element was found (which is considered true):

(member 'a '(x y a c)) ; ==> (a c)

Using standard member instead of your own predicate:

(define intersect
  (lambda (set1 set2)
    (cond
      ((null? set1)(quote ()))
      ((member (car set1) set2)
       (cons (car set1)
             (intersect (cdr set1) set2)))
      (else (intersect (cdr set1) set2)))))

(intersect '((1 2)(3 4)(5 6)) '((9 10) (7 8) (5 6))) ; ==> ((5 6))
(intersect '(a b c d) '(c d e f)) ; ==> (c d)

EDIT 1

It seems you are not searching for intersection but a special alist merge:

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

;; if you dont have r6rs remove the above and
;; uncomment this rnrs/lists-6 memp
#;(define (memp predicate? lst)
  (cond ((null? lst) #f)
        ((predicate? lst) lst)
        (else (memp predicate? (cdr lst)))))


(define (alist-merge merge-proc alist-1 alist-2)
  (if (null? alist-1) 
      '()
      (let* ((name (caar alist-1))
             (found (memp (lambda (x) (equal? (car x) name)) alist-2)))
        (if found
            (cons (merge-proc (car alist-1) (car found))
                  (alist-merge merge-proc
                               (cdr alist-1)
                               alist-2))
            (alist-merge merge-proc
                         (cdr alist-1)
                         alist-2)))))

(define (alist-merge-add alist-1 alist-2)
  (alist-merge (lambda (x y)
                 (list (car x)
                       (+ (cadr x) (cadr y))))
               alist-1
               alist-2))

(alist-merge-add '((1 2)(2 7)) '((1 3)(4 5))) ; ==> ((1 5))
Sylwester
  • 47,942
  • 4
  • 47
  • 79
  • This checks for the exact pair. :/ I need to check first elements of pairs and add 2nd elements if true. Thanks. – far_kurt Aug 08 '13 at 16:04
  • 1
    @user2662909 That is **not** intersection. I've added a generic `alist-merge` and a `alist-merge-add` that does what you want. – Sylwester Aug 08 '13 at 17:10
0

My intersection solution:

#lang racket
(define (intersect set1 set2)
  (cond [(empty? set1) '()]
        [(empty? set2) '()]

        [(= (caar set1) (caar set2)) (cons (list (caar set1)
                                                 (+ (cadar set1)
                                                    (cadar set2)))
                                           (intersect (cdr set1) (cdr set2)))]
        [(< (caar set1) (caar set2)) (intersect (cdr set1) set2)]
        [else (intersect set1 (cdr set2))]))
far_kurt
  • 39
  • 2
  • 6