問題 2

問題 2
問 2-1
以下の式を箱・ポインタ記法で図示せよ．
1. ((2012 .
London) (2016 .
Rio) (2020 .
Tokyo))
2. ((a (b)) ((c (d)) (e) f))
問 2-2
以下の箱・ポインタ記法を表現する式を示せ．
1.
(Introduction to and (algorithm) data structure)
(Introduction to and (algorithm) .
(data structure)) などでも OK
2.
(define x (head tail .
x)) や #0 = (head tail .
#0#) など，
再帰的に表現されていること
なお，2. のデータは通常では表現できないので，新たな表現法を工夫すること．
問 2-3
手続き fold-right が以下で定義されるとする．
(define (fold-right op initial sequence)
(if (null? sequence)
initial
(op (car sequence) (fold-right op initial (cdr sequence)) )))
この手続きは右結合 (right-associative) な演算である．例えば以下が成り立つ．
• (fold-right + 0 (list 1 2 3 4 5)) → (1 + (2 + (3 + (4 + (5 + 0))))) = 15
• (fold-right - 0 (list 1 2 3 4 5)) → (1 − (2 − (3 − (4 − (5 − 0))))) = 3
これに対して左結合 (left-associative) な演算 fold-left を考えることができる．例えば以下が成り立つ．
• (fold-left + 0 (list 1 2 3 4 5)) → (((((0 + 1) + 2) + 3) + 4) + 5) = 15
• (fold-left - 0 (list 1 2 3 4 5)) → (((((0 − 1) − 2) − 3) − 4) − 5) = −15
このような性質を満たす手続き fold-left を，適切なコードで埋めよを埋めることにより定義せよ．使用してよ
い Scheme の組込みリスト処理手続きは car, cdr, cons のみとする．その他のリスト処理手続きは定義を示した上
で使用してよい．null?等の述語，if, cond 等の条件式については自由に使用してかまわない．
(define (fold-left op initial sequence) 適切なコードで埋めよ )
(define (fold-left op initial sequence)
(if (null? sequence)
initial
(fold-left op (op initial (car sequence)) (cdr sequence)) ))
左結合な演算として定義できていれば OK．例の計算結果が一致するだけでは不正解．

Download Report