Scheme - 記号データ(二進木としての集合(木をリストに変換する手続き、appendと増加の程度))

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Lion - Apple(OS)
• Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
• プログラミング言語: MIT/GNU Scheme

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション)の2(データによる抽象の構築)、2.3(記号データ)、2.3.3(例: 集合の表現)、二進木としての集合の問題 2.63、a、bを解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題 2.63

a.

全ての木に対して同じ結果を生じる。

図2.16の全ての木の対して、(1 3 5 7 9 11)という結果になる。

確認。

コード

sample.scm

(define tree1
  (make-tree 7
             (make-tree 3
                        (make-tree 1 '() '())
                        (make-tree 5 '() '()))
             (make-tree 9
                        '()
                        (make-tree 11 '() '()))))

(define tree2
  (make-tree 3
             (make-tree 1 '() '())
             (make-tree 7
                        (make-tree 5 '() '())
                        (make-tree 9
                                   '()
                                   (make-tree 11 '() '())))))

(define tree3
  (make-tree 5
             (make-tree 3
                        (make-tree 1 '() '())
                        '())
             (make-tree 9
                        (make-tree 7 '() '())
                        (make-tree 11 '() '()))))

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

1 ]=> (tree->list-1 tree1)

;Value 2: (1 3 5 7 9 11)

1 ]=> (tree->list-2 tree1)

;Value 3: (1 3 5 7 9 11)

1 ]=> (tree->list-1 tree2)

;Value 4: (1 3 5 7 9 11)

1 ]=> (tree->list-2 tree2)

;Value 5: (1 3 5 7 9 11)

1 ]=> (tree->list-1 tree3)

;Value 6: (1 3 5 7 9 11)

1 ]=> (tree->list-2 tree3)

;Value 7: (1 3 5 7 9 11)

b.

どちらも再帰的手続きで、tree->list-1は再帰的プロセス、tree->list-2は反復的プロセス。そして、tree->list-1はappendを使っているので、n個の要素の釣り合っている木をリストに変換するのに必要なステップ数は、appendを使っていない分、tree->list-2の方がより遅く増加する。