問題2-24〜28 - TAKUYA’s CODE RECORDER

今日は、階層構造を操作するための練習問題に取り組みました。以下、それぞれの階層構造とそれの評価結果を羅列します。
まずは、問題2-24です。

(define x (list 1 (list 2 (list 3 4))))
x
=>(1 (2 (3 4)))

次は、問題2-25です。リストの後方部分を取り出すためには少し工夫がいるようです。

(define x1 (list 1 3 (list 5 7) 9))
(car (cdr (car (cdr (cdr x1)))))

(define x2 (list (list 7)))
(car (car x2))

(define x3 (list 1 (list 2 (list 3 (list 4 (list 5 (list 6 7)))))))
(car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr x3))))))))))))

=>7
=>7
=>7

問題2-26です。このあたりをしっかりと抑えておかないと、後の問題でつまずきます。(というよりか、現時点でつまずいています。)

(define (append list1 list2)
  (if (null? list1)
      list2
      (cons (car list1) (append (cdr list1) list2))))

(define y1 (list 1 2 3))
(define y2 (list 4 5 6))

(append y1 y2)
(cons y1 y2)
(list y1 y2)

=>(1 2 3 4 5 6)
=>((1 2 3) 4 5 6)
=>((1 2 3) (4 5 6))

問題2-27です。前回のエントリーで書いたreverseを簡潔に書いたバージョンを利用します。

(define (reverse l)
  (define (iter things result)
    (if (null? things)
        result
        (iter (cdr things)
              (cons (car things) result))))
  (iter l '()))

(define (deep-reverse t)
  (define (iter things result)
    (if (null? things)
        result
        (iter (cdr things)
              (cons (reverse (car things))
                    result))))
  (iter t '()))

(define z (list (list 1 2) (list 3 4)))

z
(reverse z)
(deep-reverse z)

=>((1 2) (3 4))
=>((3 4) (1 2))
=>((4 3) (2 1))

今日のラスト、問題2-28です。ここでつまずいてしまいました。car/cdrの前後で、リストがどうなるかを場合分けする必要がありそうですが、それが上手くいきませんでした。そのため、それらの処理の途中経過をpair?やnull?で調べるとどうなるかをテストしてみました。以下にメモしておきます。

(define t (list (list 1 2) (list 3 4)))

(car t)
=>(1 2)

(car (car t))
=>1
(pair? (car (car t)))
=>#f
(pair? (list (car (car t))))
=>#t

(cdr (car t))
=>(2)
(pair? (cdr (car t)))
=>#t
(null? (cdr (car t)))
=>#f
(null? (cdr (cdr (car t))))
=>#t

(cdr t)
=>((3 4))
(car (cdr t))
=>(3 4)

後日、再考する際の参考にしたいと思います。

■追記(2008/2/24)
ちょっと先に読み進めると答えが書いてあったので、それで試してみました。

(define (append list1 list2)
  (if (null? list1)
      list2
      (cons (car list1) (append (cdr list1) list2))))

(define (fringe tree)
  (cond ((null? tree) '())
        ((not (pair? tree)) (list tree))
        (else (append (fringe (car tree))
                      (fringe (cdr tree))))))

(define x (list (list 1 2) (list 3 4)))

(fringe x)

=>(1 2 3 4)

treeに何の要素もない場合、treeがリスト状になっていない場合(ただの数値の場合)。これらのケースを考慮して、append仕様に合わせて場合分けすればいいということがわかりました。