Adjoin-set for an ordered set representation From SICP:


  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)
  (define (rec subset) 
    (cond ((null? subset) (list x))
          ((&gt; x (car subset)) (cons (car subset) (rec (cdr subset))))
          (else (cons x subset))))
  (if (element-of-set? x set)
      set
      (rec set)))


Can this be improved?
Calling element-of-set? from adjoin-set introduces unnecessary redundancy.  One may incorporate this test within the adjoin-set function (in your case, rec should be the main body of your function, with an = test added):

(define (adjoin-set x set)
  (cond
    ((null? set) (cons x set))
    ((= x (car set)) set)
    ((&lt; x (car set)) (cons x set))
    (else (cons (car set) (adjoin-set x (cdr set))))))


This function performs fewer steps since it does not call element-of-set?.  However, its complexity is still O(n), which is the same as your implementation's complexity, as well as the complexity of element-of-set?.