オンラインSICP読書女子会 #24 (2.2.4 (1))
練習問題 2.43, 2.44
ex-2.43
本来は board-size 回, 自分に必要な盤面を1回だけ呼べばよかったのが,
board-size 回の中で, (1 回だけではなく) board-size 回再計算してしまっているため.
board-size = n とすると, 元が O(n) で,
失敗版が O(n^n) …?＝ω＝;
掛かる時間は T^{board-size} でいいのかな…？＝ω＝;;
sec-2.2.4. 例: 図形言語
Example: A Picture Language
sec-2.2.4. (a) 図形言語
The picture language
和訳だとどっちも単に図形言語だけどニュアンスが…＞ω＜;
beside演算は二つのペインタを引数に取り、枠の左半分に一つ目のペインタの画像を描き右半分に二つ目のペインタの画像を描く新しい複合ペインタを作ります。
左側の引数を左側に描いて, 右側の引数を右側に描く. 素直・ω・*
(define (beside left right) SOMETHING)
belowは二つのペインタを引数に取り、二つ目のペインタの画像の下に一つ目のペインタの画像を描く複合ペインタを作ります。
below takes two painters and produces a compound painter that draws the first painter's image below the second painter's image.
beside は左右どっちでも beside だけど, below は「〜の下に」で中途半端に順番意識しないとだし日本語だと上下なのに (below 下 上) なのちょっとびみょ…
英語だと draw FIRST below SECOND で draw LOWER below UPPER なのでそっちだと below の位置はともかく上下の出現順は自然言語のまま？＝ｘ＝;
(define (below lower upper) SOMETHING)
基本図形, wave.
環境にこれが既にあるのをまずは前提に.
合成図形, wave2:
(define wave2 (beside wave (flip-vert wave)))
; left = wave = 基本図形
; right = (flip-vert wave) = 左右反転
右に鏡写しをぺたり.
合成図形, wave4:
(define wave4 (below wave2 wave2))
; upper = wave2 = (left=基本図形, right=左右反転)
; lower = wave2 = (left=基本図形, right=左右反転)
今度は wave2 をそのまま上下に. 今度は鏡写しはなし.
flipped-pairs:
wave2, wave4 は, 環境に wave がある前提で記述していたけれど, 任意の図形を引数で渡して, それに対して wave4 と同様の合成図形生成処理を適用する処理.
(define (flipped-pairs painter)
(let
(
(painter2 (beside painter (flip-vert painter)))
)
(below painter2 painter2)
)
)
右方向に枝分かれを再帰的に, right-split:
(define (right-split painter n)
(if
(= n 0)
painter
(let
(
(smaller (right-split painter (- n 1)))
)
(beside painter (below smaller smaller))
)
)
)
; left = 基本図形
; right = (below smaller smaller))
;==>
; left = 基本図形, upper-right = smaller
; lower-right = smaller
corner-split:
本文の途中だけど練習問題に出てるので練習問題に割り込み.
ex-2.44. up-split
上方向に枝分かれを再帰的に.
(below lower upper) の順が微妙になれない…
(define (up-split painter n)
(if
(= n 0)
painter
(let
(
(smaller (up-split painter (- n 1)))
)
; 引数順は `(below lower upper)`
(below painter (beside smaller smaller))
)
)
)
; lower = 基本図形
; upper = (beside smaller smaller))
;==>
; upper-left = smaller, upper-right = smaller
; lower = 基本図形
本文に戻って, corner-split:
図 2.13 だと, 大きさ的に, corner-split = identity で up-split は縦半分, right-split は横半分ってなってるけれど,
実際には up-split, right-split, corner-split は3種類とも辺の長さが identity の半分 (面積だと4分の1) の正方形になりそう.
次のページにある 図 2.14 右下の図もそうなってるし.
最終的にできる図形の大きさは, 辺の長さで言うと, identity から縦横どっちも 1.5 倍.
具体的な拡大縮小の比率については書いてないし, 図 2.13 の比率で伸縮しても矛盾は生じなそう.
こっちだと最終的にできる図形の大きさは, 辺の長さで言うと, identity から縦横どっちも 2 倍.
n=0 の時を基本図形のサイズと考えて全体のサイズは?って考えると, 等比数列になるのかな…?
square-limit:
(define (square-limit painter n)
(let
(
(quarter (corner-split painter n))
)
(let
(
(half (beside (flip-horiz quarter) quarter))
)
(below (flip-vert half) half)
)
)
)
全体としては, 部分パネルが 2x2 で4枚並んでる構成.
基本パネルは右上部分.
ここが corner-split で再帰図形で生成されたもので quarter (4分の1パネル).
これを左に鏡写しすると横長になって halt (2分の1パネル).
さらに下に鏡写しすると正方形に戻って全体 (square-limit) になる.