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).