Adjoin-set for an ordered set representation

Question

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))
 ((> 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?

Answer 1

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