読書会メモ

memo SICP

今日は頁てきには 1 頁でしたが、結構濃かったです。あっという間の 1.5h
今日はなんとなくですが、もくもくとコードをニラんだカンジでした。

問題 2.63

'(3 '(1 '() '()) '(5 '() '()))

;;   3
;;  / \
;; 1   5

なリストを tree->list に吸わせると

(1 3 5)

が戻る。tree->list1 なら

(append (append '() (cons 1 '()))
	(cons 3 (append '() (cons 5 '()))))

tree->list2 なら

(cons 1 (cons 3 (cons 5 '())))

という事で性能てきには append の数分違う、という結論。cons の回数自体は同じはずなんだけど、tree->list1 は cons と同じ回数 append している。

問題 2.64

let がひたすらに重なっておられます。

'(1 3 5 7 9 11)

が何を作るか。なんとなく

'(5 (1 () (2 () ())) (9 (7 () ()) (11 () ())))

;;     5
;;   /   \
;;  1     9
;;   \   / \
;;    2 7   11

ではないかと。以下にざっくり要件を纏めておきます。
まず、基本的には以下のような部分木の集合

n が 1 の場合

;;   1
;;  / \
;; () ()

n が 2 の場合

;;   1
;;  / \
;; ()  2
;;    / \
;;   () ()

n が 3 の場合

;;      2
;;    /   \
;;   1     3
;;  / \   / \
;; () () () ()

の集りである、という事。上記にあるように n が 1 以外の偶数の場合は右の部分木の要素の数の方が多くなる模様。また、上記の通り、n が 1 以外の場合、

  • 奇数だったら (+ (/ (- n 1) 2) 1) が中央の要素
  • 偶数だったら (/ n 2) が中央の要素

ちなみに C な配列と違って要素番号は 1 から始まります。

それにしても

最小構成な構造の集合、というあたりに面白さがあります。例えば n が 4 の場合には

;;      2
;;    /   \
;;   1     3
;;  / \   / \
;; () () ()  4
;;          / \
;;         () ()

になる。左の部分木は n が 1 で、右の部分木は n が 2 になっている。n が 5 になると

;;
;;    3
;;   / \
;;  1   4 
;;   \   \
;;    2   5

という形になるのか。n が 6 になると

;;
;;     3
;;   /   \
;;  1     5 
;;   \   / \
;;    2 4   6

という形、という事でルールが分かってれば類推は簡単になりますな。

今後は

パートナーが希望のあたりをごりごりヤッちゃう、という方向が良さげ。わしが適切な助言ができているか、という問題があるんですが。。