Chapter 2, Building Abstractions with Data

Section - 2.3 Symbolic Data

Exercise 2.66


Here I am evading the implementation of records structure as exercise seems to focus more on the lookup instead of the record.

It can be extended to use record.

1
2
3
4
5
6
7
8
9
(define (lookup x set)
  (cond ((null? set) false)
        ((= x (entry set)) true)
        ((< x (entry set))
            (lookup x (left-branch set)))
        (else
            (lookup x (right-branch set)))
  )      
)

Test/Output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
; using procedure from previous exercise to build tree.
> (define my-tree (list->tree (list 0 3 4 9 11 20 26 29 35 76 93 97)))
> (lookup 21 my-tree)
#f
> (lookup 0 my-tree)
#t
>  (lookup 10 my-tree)
#f
>  (lookup 97 my-tree)
#t
>  (lookup 35 my-tree)
#t
>  (lookup 33 my-tree)
#f
>