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))))))))