## SICP – cap. 2 – sets e recupero informazioni – 88 – esercizio Continuo da qui, copio qui.

Exercise 2.66: Implement the `lookup` procedure for the case where the set of records is structured as a binary tree, ordered by the numerical values of the keys.

Io quando ci sono gli esercizi chiamo Bill the Lizard 😋

The final part of [the] section asks us to consider a database that contains records, each of which has a `key` and some `data`. If the database is represented as an unordered list, a record can be looked up by its key using the following procedure.

``````(define (lookup given-key set-of-records)
(cond ((null? set-of-records) false)
((equal? given-key (key (car set-of-records)))
(car set-of-records))
(else (lookup given-key (cdr set-of-records)))))``````

We can define simple procedures for making a record out of a `key` and its `data`, and for extracting the `key` and `data` from an existing record in order to test the procedure above.

``````(define (key record) (car record))
(define (data record) (cdr record))
(define (make-record key data) (cons key data))

(define database
(list (make-record 1 'Bill)
(make-record 2 'Joe)
(make-record 3 'Frank)
(make-record 4 'John)))``````

We can start by including the `list->tree` and `partial-tree` procedures given for exercise 2.64 [qui], along with a few required supporting procedures.

``````(define (entry tree) (car tree))
(define (make-tree entry left right)
(list entry left right))

(define (list->tree elements)
(car (partial-tree elements (length elements))))

(define (partial-tree elts n)
(if (= n 0)
(cons '() elts)
(let ((left-size (quotient (- n 1) 2)))
(let ((left-result (partial-tree elts left-size)))
(let ((left-tree (car left-result))
(non-left-elts (cdr left-result))
(right-size (- n (+ left-size 1))))
(let ((this-entry (car non-left-elts))
(right-result (partial-tree (cdr non-left-elts)
right-size)))
(let ((right-tree (car right-result))
(remaining-elts (cdr right-result)))
(cons (make-tree this-entry left-tree right-tree)
remaining-elts))))))))``````

Raccolgo tutto il codice in `es-2.66.rkt`.

This makes it easier to convert the existing database to one structured as a binary tree. Finally, we can write the new implementation of `lookup` using `element-of-set?` as a guide.

``````(define (lookup given-key set-of-records)
(cond ((null? set-of-records) #f)
((= given-key (key (car set-of-records)))
(car set-of-records))
((< given-key (key (car set-of-records)))
(lookup given-key (left-branch set-of-records)))
((> given-key (key (car set-of-records)))
(lookup given-key (right-branch set-of-records)))))`````` sicp-ex propone, senza spiegazione, lo stesso codice di Bill.
Più articolata la versione di Drewiki.

Seguendo Bill, oltre che miei nuovi interessi, devo rivedere il mio progetto relativo a SICP 😯

🤩

Posta un commento o usa questo indirizzo per il trackback.