sicp exercise 2.61

;; 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 false #f)
(define true  #t)

(define (element-of-set? ele set)
  (cond ((null? set) false)
        ((> (car set) ele) false)
        ((= (car set) ele) true)
        ((< (car set) ele) (element-of-set? ele (cdr set)))))

(define (adjoin-set ele set)
  (cond ((null? set) (list ele))
        ((> (car set) ele) (cons ele set))
        ((= (car set) ele) set)
        ((< (car set) ele) (cons (car set) (adjoin-set ele (cdr set))))))

(define set1 (list 2 4 6 8 10 12))

(display (element-of-set? 100 set1)) (newline)
(display (element-of-set? 4 set1)) (newline)
(display (element-of-set? 8 set1)) (newline)

(display (adjoin-set 0 set1)) (newline)
(display (adjoin-set 5 set1)) (newline)
(display (adjoin-set 8 set1)) (newline)
(display (adjoin-set 20 set1)) (newline)