SICP問題2.66
キーの数値で順序付けられている二進木で構造化されているデータのlookup
まずレコードの選択子と構成子
(define (make-rec key data) (cons key data)) (define (key rec) (car rec)) (define (get-data rec) (cdr rec))
テスト用にキーの数値で順序付けられている二進木で構造化されているデータを定義。
リストが順番であれば 2.64 の list->tree が使えるので(list->tree は要素の内容でなく個数のみを使用しているので)
(define t1 (list->tree (list (make-rec 1 'n) (make-rec 2 'a) (make-rec 3 'b) (make-rec 6 'y) (make-rec 8 'm) (make-rec 9 's) (make-rec 11 'l)))) ; ((6 . y) ((2 . a) ((1 . n) () ()) ((3 . b) () ())) ((9 . s) ((8 . m) () ()) ((11 . l) () ())))
こんな感じに。
で実装。p91で定義した entry, left-branch, right-branch を使用する
(define (lookup given-key set-of-records) (cond ((null? set-of-records) #f) ((= given-key (key (entry set-of-records))) (get-data (entry set-of-records))) ((< given-key (key (entry set-of-records))) (lookup given-key (left-branch set-of-records))) ((> given-key (key (entry set-of-records))) (lookup given-key (right-branch set-of-records)))))
あまりにもアレなので let 使った版
(define (lookup given-key set-of-records) (if (null? set-of-records) #f (let ((entry-rec (entry set-of-records))) (let ((entry-key (key entry-rec))) (cond ((= given-key entry-key) (get-data entry-rec)) ((< given-key entry-key) (lookup given-key (left-branch set-of-records))) ((> given-key entry-key) (lookup given-key (right-branch set-of-records))))))))