sicp-ex-2.61


 (define (adjoin-set x set) 
   (cond ((null? set) (list x)) 
         ((= x (car set)) set) 
         ((< x (car set)) (cons x set)) 
         (else (cons (car set) (adjoin-set x (cdr set)))))) 

<< Previous exercise (2.60) | Index | Next exercise (2.62) >>


shyam

Exercise 2.61. Give an implementation of adjoin-set using the ordered representation. By analogy with element-of-set? show how to take advantage of the ordering to produce a procedure that requires on the average about half as many steps as with the unordered representation.

  
 (define (adjoin-set x set) 
   (cond ((or (null? set) (< x (car set))) (cons x set)) 
         ((= x (car set)) set) 
         (else (cons (car set) (adjoin-set x (cdr set)))))) 

>>>

AMS

An iterative version of "adjoin-set".

  
 (define (adjoin-set x set) 
   (define (adjoin-set-iter early rest) 
     (cond ((null? rest) (append early (list x))) 
           ((= x (car rest)) (append early rest)) 
           ((< x (car rest)) (append early (cons x rest))) 
           (else (adjoin-set-iter (append early (list (car rest))) 
                                  (cdr rest))))) 
   (adjoin-set-iter '() set)) 

This version runs in O(n²), as I believe append runs in O(n).>>>



m3tafunj

After doing exercise 2.61 it seemed like the exercise begged the question: how would you efficiently get all items that are not shared between sets, disjoin, or get all the items in set one that are not in set two, the difference? For anyone interested I wrote implementations for ordered lists that are O(n)

 (define (disjoin set1 set2) 
   ;numbers that are not in both sets 
   (cond((null? set1)set2) 
        ((null? set2)set1) 
        (else 
         (let((x1 (car set1))(x2 (car set2))) 
           (cond((= x1 x2) 
                (disjoin (cdr set1)(cdr set2))) 
                ((< x1 x2) 
                 (cons x1(disjoin(cdr set1)set2))) 
                (else(cons x2(disjoin set1 (cdr set2))))))))) 
  
 (disjoin '(1 2 3)'(1 3 4)) 
 (disjoin '(1 2 3 6)'(1 3 4)) 
 (disjoin '(1 2 3 6)'(1 3 4 5 7)) 
  
 (define(difference set1 set2) 
     ;only the numbers from the first set not in the second 
     (cond((null? set1)'()) 
        ((null? set2)set1) 
        (else 
         (let((x1 (car set1))(x2 (car set2))) 
           (cond((= x1 x2) 
                (difference (cdr set1)(cdr set2))) 
                ((< x1 x2) 
                 (cons x1(difference(cdr set1)set2))) 
                (else(difference set1 (cdr set2)))))))) 
 (difference '(1 2 3)'(1 3 4)) 
 (difference '(1 2 3 6)'(1 3 4)) 
 (difference '(1 2 3 5 6)'(1 3 4 5 7)) 
 (difference '(1 2 3 5 6 7)'(1 3 4 7)) 

horeszko

A version that handles ordered sets with duplicate elements in x or set.

  
 (define (adjoin-set x set) 
   (cond ((null? set) (cons x set)) ; case: null set 
         ((null? (cdr set)) (append set (list x))) ; case: end of list 
         (else (let ((a (car set)) (b (car (cdr set)))) ; case: in list 
                 (cond ((> a x) (cons x set)) 
                       ((and (<= a x) (>= b x)) (append (list a x) (cdr set))) 
                       ((< b x) (append (list a) (adjoin-set x (cdr set))))))))) 
 ; test 
  
 (adjoin-set 1 '()) 
 (adjoin-set 1 '(2 3)) 
 (adjoin-set 2 '(1 3)) 
 (adjoin-set 1 '(1 2)) 
 (adjoin-set 1 '(1 1)) 
 (adjoin-set 4 '(1 2 3 5 6)) 
 (adjoin-set 6 '(1 2 3 4 5 6)) 
 (adjoin-set 7 '(1 2 3 4 5 6))