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

From Drewiki
Jump to: navigation, search

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 consing it onto the remaining elements of the set. Otherwise, the new set is the current element consed 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)
Personal tools