SICP Exercise 2.61: Adjoining to Orderered Representations

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.

The implementation of element-of-set? given for using the ordered representation iterates through the list until it either finds the item being checked or until it finds an element greater than the item being checked. Our implementation of adjoin-set has to produce a representation that maintains the ordering and can do so using a similar approach. We're going to iterate through the list until we find the appropriate location for the new item to be inserted, and we still have the same four cases to consider. However, as we need to build up a result list as we go along, the actions taken for each case differ:

• If we're adjoining to a null list, then the result is simply a list containing only the item being adjoined.
• If the head of the list is the same as the item being adjoined then the item is already present in the list and so we don't need to modify the list and can just use the current list as the result.
• If the head of the list is greater than the item being adjoined then the item needs to go at the head of the list, and so we need to cons the item onto the list.
• Otherwise (i.e. if the head of the list is less then the item being adjoined) then the item needs to be inserted later in the list. We can do this by consing the head of the list onto the result of adjoining the item to the cdr of the list.

An appropriate implementation of the procedure is therefore:

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

Here it is in action:

> (adjoin-set 4 '())
'(4)
> (adjoin-set 3 '(4))
'(3 4)
> (adjoin-set 10 '(3 4))
'(3 4 10)
> (adjoin-set 6 '(3 4 10))
'(3 4 6 10)
> (adjoin-set 7 '(3 4 6 10))
'(3 4 6 7 10)
> (adjoin-set 5 '(3 4 6 7 10))
'(3 4 5 6 7 10)

Similar to the element-of-set? implementation, assuming that the items we adjoin are of many different sizes and are randomly ordered, then we'll sometimes be able to insert items near (and so stop iterating near) the start of the list, while for other items we'll have to insert them later in the list, and so on average we'll need Θ(n/2) steps to adjoin items.

It's worth noting that the ordering of the items processed is important for adjoin-set in making this assertion, whereas it wasn't for element-of-set?. For example, if you take any set and then check each of it's members is present in the set using element-of-set? then this will require, on average, n/2 recursive calls to element-of-set? to perform the check, regardless of the ordering we use. However, if we start with an empty list and try to build a set by inserting items in numerically ascending order (i.e. (adjoin-set 3 (adjoin-set 2 (adjoin-set 1 '())))) then each adjoin will require n recursive calls to adjoin-set - the first will require 1 call, the second will require 2 calls, and so on, as for each new item it will need to iterate to the end of the current list to find the appropriate location for the item. On the other hand, if we build the set by inserting items in numerically descending order (i.e. (adjoin-set 1 (adjoin-set 2 (adjoin-set 3 '())))) then each adjoin will only require 1 call to adjoin-set, as each item will go at the head of the current list.