SICPを読む(51) 問題 2.24 - 2.28 リスト巡り

Scheme

SICPネタを書くとアクセス数が激減することが判明。ブログで読者を逃すならSICPを読もう。

問題 2.24

まずは、括弧表現で、書いてみる。

(1 (2 (3 4)))

評価してみる。ドキドキ。

(list 1 (list 2 (list 3 4)))
; (1 (2 (3 4)))

あってた。

よく見ると、

(list 1 (list 2 (list 3 4)))
; vimで :.s/list //g する。
(1 (2 (3 4)))

括弧表現では(list ...)を()に置き換えただけであることがわかった。

AAで木表現を書くのは辛そうなので、ポインタ表現で。

[ | ] - [ |/]
 |       |
 1      [ | ] - [ |/]
         |       |
         2      [ | ] - [ |/]
                 |       |
                 3       4

(list 3 4)から作るとわかりやすかった。

count-nils

count-leavesの逆を作ってみた。nilの数を数える。

(define (count-nils x)
  (cond ((null? x) 1)
        ((not (pair? x)) 0)
        (else (+ (count-nils (car x))
                 (count-nils (cdr x))))))

ホントに逆にしただけ(笑

「リストの数 = nilの数」になるので、リストがいくつあるのかわかる。

nilは無を表すので、無が複数あるというnilsはなんかおかしい。

問題 2.25

リストをcar,cdrで巡ろう。

(car (cdr (car (cdr (cdr `(1 3 (5 7) 9))))))
(car (car `((7))))
(car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr `(1 (2 (3 (4 (5 (6 7))))))))))))))))))
  • クオート便利!! SICP P84参照。
  • surround.vimのお蔭で楽できた、yss)ラブ。
  • あ　き　た。

問題 2.26

全然迷わず、解けた。

(define x (list 1 2 3))
(define y (list 4 5 6))

(append x y) ; (1 2 3 4 5 6)
(cons x y)   ; ((1 2 3) 4 5 6)
(list x y)   ; ((1 2 3) (4 5 6))

完全理解。

問題 2.27

要素を全て逆順にする。

(deep-reverse `((1 2 3) (4 5 6)))
; ((6 5 4) (3 2 1))

を作る。

できたぁぁぁぁ!!嬉しい!!激しく嬉しい!!

(define (deep-reverse items)
  (define (iter i a)
    (if (null? i)
         a
         (iter (cdr i)
               (cons (if (list? (car i))
                         (iter (car i) `())
                         (car i))
                     a))))
  (iter items `()))
(deep-reverse `((1 2 3) (4 5 6))) ; ((6 5 4) (3 2 1))

値がリストであれば、cons内で、もう一回iterする。

list?を使ってるのは内緒。

数学以外は解けそうな気分

解答例いろいろ
  • SICP memo: 問題2.27
    • 正攻法。deep-reverseに再帰すればよかったのか。
    • 僕のはif2回の解答に近い。
    • (iter (car i) `())でも、(deep-reverse (car i))への再帰でも意味は変わらない。
    • (list? (car i)と、(pair? (car i))の違いがイマイチ。
      • 確認してみる。
(list? (cons 1 2)) ; #f
(list? (list 1 2)) ; #t

(pair? (cons 1 2)) ; #t
(pair? (list 1 2)) ; #t
      • 一個先を見れば良いだけなので、pair?で充分対応できる。
  • ex-2.27 | SICP | OpenSource Web
    • セクシー過ぎるよ!!グレイトジョブ!!
    • mapという発想はなかった。
    • 展開すると・・・。
(deep-reverse `((1 2) (3 4)))
(reverse (map reverse `((1 2) (3 4))))
(reverse (list (reverse `(1 2)) (reverse `(3 4))))

map再帰すげ〜〜〜〜〜〜〜!!

問題 2.28

リストをフラットに並び替える。

appendを使ってみた。

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

(fringe `((1 (2 3)) ((4 5) 6))) ; (1 2 3 4 5 6)

かなり苦戦したけど、もっと良い方法がある気がする。