Scheme Set Implementation

So I made some progress through little schemer. I was reading through relationship chapter. It goes through Set implementation. I knew how Set works but have never actually written one. So this was a good opportunity to write one.

I needed some helper methods from previous chapters as well. Again it may not be the best implementation but I have tried to do my best. Also if you are reading book you may not find couple of implementations. One of them is diff between two sets.

Here is the code:

#|
  Helper functions.
|#
(define member?
    (lambda (x lat)
        (cond
         ((null? lat) #f)
         (else
            (or
            (equal? x (car lat))
            (member? x (cdr lat)))))))

(define atom?
    (lambda (x)
        (and
         (not (null? x))
         (not (pair? x)))))

(define filter
    (lambda (lat proc) 
        (cond
         ((null? lat) ())
         ((proc (car lat))(cons (car lat) (filter (cdr lat) proc)))
         (else
            (filter (cdr lat) proc)))))

(define join
    (lambda (l1 l2)
        (cond
         ((null? l2) l1)
         (else
            (join (cons (car l2) l1) (cdr l2))))))



#|
  Set Object with major functions of set theory
  Operations:
  (1) set?
  (2) create_set
  (2) union
  (3) intersect
  (4) diff
|#

(define set?
    (lambda (lat)
        (cond
         ((null? lat))
         ((atom? lat))
         ((member? (car lat) (cdr lat)))
         (else
            (set? (cdr lat))))))


(define create_set
    (lambda (lat)
        (cond 
         ((null? lat) ())
         ((member? (car lat) (cdr lat))
            (set (cdr lat)))
         (else 
            (cons (car lat)
              (set (cdr lat)))))))


(define subset?
    (lambda (s1 s2)
        (cond
            ((null? s1) #t)
            (else
             (cond
                ((member? (car s1) s2) (subset? (cdr s1) s2))
                (else #f))))))

(define intersect
    (lambda (s1 s2)
        (cond
         ((null? s1) (quote ()))
         ((member? (car s1) s2)
            (cons (car s1) (intersect (cdr s1) s2)))
         (else (intersect (cdr s1) s2)))))



(define union
    (lambda (s1 s2)
        (cond
         ((null? s1) s2)
         ((not (member? (car s1) s2))
                 (cons (car s1) (union (cdr s1) s2)))
         (else
            (union (cdr s1) s2)))))


#|
 (diff [1 2 3] [ 4 3 2]) => ( 1  4 )
|# 
(define diff
    (lambda (s1 s2)
        (join
          (filter s1 (lambda (ele)
                      (not (member? ele s2))))
          (filter s2 (lambda (ele)
                      (not (member? ele s1)))))))
Share on : Twitter, Facebook or Google+