Scheme - データによる抽象の構築(記号データ(集合の表現(集合と情報検索)))

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)
異なる出版社で予約受付中

開発環境

• OS X Mavericks - Apple(OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• Scheme (プログラミング言語)
• Gauche (処理系)

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の2(データによる抽象の構築)、2.3(記号データ)、2.3.3(例: 集合の表現)、集合と情報検索、問題 2.66.を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs
• プログラミングGauche (Kahuaプロジェクト (著), 川合 史朗 (監修), オライリージャパン)

問題 2.66.

コード(BBEdit, Emacs)

sample.scm

#!/usr/bin/env gosh
;; -*- coding: utf-8 -*-

;; これまでに書いた手続き
(load "./tree.scm")

;; レコードを対で表現
;; 構成子
(define (make-record key value)
  (cons key value))

;; 選択子
(define (key record) (car record))
(define (value record) (cdr record))

(define (lookup given-key set-of-records)
  (if (null? set-of-records)
      false
      (let ((e (entry set-of-records)))
        (let ((k (key e)))
          (cond ((equal? given-key k) e)
                ((< given-key k)
                 (lookup given-key
                         (left-branch set-of-records)))
                (else
                 (lookup given-key
                         (right-branch set-of-records))))))))

(define record1 (cons 1 "a"))
(define record2 (cons 2 "b"))
(define record3 (cons 3 "c"))
(define record4 (cons 4 "d"))
(define record5 (cons 5 "e"))

(define set-of-records (list->tree (list record1
                                         record2
                                         record3
                                         record4
                                         record5)))

(print "set-of-records")
(print-tree set-of-records)
(print "lookup")
(for-each (lambda (k)
            (print k ": " (lookup k set-of-records)))
          (enumerate-interval 0 9))

入出力結果(Terminal(gosh), REPL(Read, Eval, Print, Loop))

$ ./sample.scm
set-of-records
                ()
        (1 . a)
                        ()
                (2 . b)
                        ()
(3 . c)
                ()
        (4 . d)
                        ()
                (5 . e)
                        ()
lookup
0: #f
1: (1 . a)
2: (2 . b)
3: (3 . c)
4: (4 . d)
5: (5 . e)
6: #f
7: #f
8: #f
9: #f
$