SICP 問題 2.27(部分枝も逆順にするdeep-reverse手続き)
【問題】
問題 2.18 の手続き reverse を修正し、引数としてリストをとり、要素を逆順にし、更に部分木も奥まで逆順にする手続き、deep-reverse を作れ。
例えば
(define x (list (list 1 2) (list 3 4))) x ((1 2) (3 4) ) (revese x) ((3 4) (1 2) ) (deep-reverse x) ((4 3) (2 1) )
【解答】
問題 2.18 の reverse はこんな感じだった。(名前は my-reverse にしたみたい。)
(define (my-reverse lis) (let loop ((src lis) (dst '())) (if (null? src) dst (loop (cdr src) (cons (car src) dst)))))
if でsrcとなるリストがnullかどうか見てるだけだが、もう一つ今から処理しようとする(car src)がリストだったらこれに対してreverseかけるような感じだろう。
なので、condに変更する。
deep-reverseって手続きは組込みで無いみたいだからそのまま使わせてもらおう。
(define (deep-reverse lis) (let loop ((src lis) (dst '())) (cond ((null? src) dst) ;現在の処理対象要素がリストの場合はその要素に対してもdeep-reverseを適用する。 ((list? (car src)) (loop (cdr src) (cons (deep-reverse (car src)) dst))) (else (loop (cdr src) (cons (car src) dst))))))
これ、反復プロセスを使って記述してるけども、それでも枝の数だけスタック?が消費される。
けどこういう場合はしょうがないはず。だって処理対象が枝なんだもん。
再帰だからこれだけ単純に記述できるわけで、ループで記述しようと思ったら恐ろしく面倒なロジックになる。
さて、では実験。
おっけ〜。
gosh> (define x (list (list 1 2) (list 3 4)))
x
gosh> x
((1 2) (3 4))
gosh> (deep-reverse x)
((4 3) (2 1))
gosh> (define y '((1 2) (3 4 (5 (6 7 8 9) 10))))
y
gosh> y
((1 2) (3 4 (5 (6 7 8 9) 10)))
gosh> (deep-reverse y)
(((10 (9 8 7 6) 5) 4 3) (2 1))
gosh>