## **Note: this wiki is now retired and will no longer be updated!**

**The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.**

# SICP exercise 2.61

## Problem

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.

## Solution

The original implementation of `adjoin-set` uses `element-of-set?` to decide whether or not to add the element to the set, but if we use the ordered set representation, we can't do that: `adjoin-set` must preserve the ordering of the set when it adds the new element, but `element-of-set?` only tells us whether the element is already in the set; if it's not, `element-of-set?` doesn't tell us *where* to insert it. Therefore, `adjoin-set` needs to traverse the list itself in order to maintain the ordering of the set.

We should expect the ordered set version of `adjoin-set` to have the same structure as the ordered set version of `element-of-set?`: a recursive procedure containing a `cond` form with 4 clauses, one for each possible case when comparing a value to elements of a set represented as an ordered list. Only the consequents will be different: rather than returning true or false, `adjoin-set` will always return a set with at least one element. Here's the implementation:

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

If `adjoin-set` reaches the end of the set, then `x` is larger than all other elements, so it's placed at the end of the set. If it's already in the set, we're done looking: just return the set as-is. If `adjoin-set` encounters an element larger than `x`, we're done looking: insert `x` into the set at that point by `cons`ing it onto the remaining elements of the set. Otherwise, the new set is the current element `cons`ed onto the result of adding `x` to the remainder of the set.

Tests:

(define s1 '(1 3 5)) (adjoin-set 0 s1)

*Output:*

`
`

(0 1 3 5)

(adjoin-set 1 s1)

*Output:*

`
`

(1 3 5)

(adjoin-set 2 s1)

*Output:*

`
`

(1 2 3 5)

(adjoin-set 4 s1)

*Output:*

`
`

(1 3 4 5)

(adjoin-set 6 s1)

*Output:*

`
`

(1 3 5 6)