src/sicp/ch2_3_3_sets_as_trees.rkt

   1 #lang racket
   2
   3 (require racket/trace)
   4
   5 (define (entry tree) (car tree))
   6 (define (left-branch tree) (car (cdr tree)))
   7 (define (right-branch tree) (car (cdr (cdr tree))))
   8
   9 (define (make-tree entry left right) (list entry left right))
  10
  11 (define (element-of-set? x set)
  12   (cond ((null? set) #f)
  13         ((= x (entry set)) #t)
  14         ((< x (entry set)) (element-of-set? x (left-branch set)))
  15         ((> x (entry set)) (element-of-set? x (right-branch set)))
  16         (else #f)))
  17
  18 (define (adjoin-set x set)
  19   (cond ((null? set) (make-tree x '() '()))
  20         ((= x (entry set)) set)
  21         ((< x (entry set)) (make-tree (entry set)
  22                                       (adjoin-set x (left-branch set))
  23                                       (right-branch set)))
  24         ((> x (entry set)) (make-tree (entry set)
  25                                       (left-branch set)
  26                                       (adjoin-set x (right-branch set))))))
  27
  28 (trace make-tree)
  29
  30 (provide entry left-branch right-branch make-tree)