SICP独習会 リスト演算(問題2.17〜)
この節では、リストを操作する手続きを作成する。例題として、
- リストの各要素にアクセスする手続き(配列のように扱う) list-ref
- リストの要素の個数をかえす手続き length
- 二つのリストを連結する手続き append
が、提示してあった。
これらの手続きを利用して、問題を解いていきたい。
問題2.17
これは、すんなり完成。
(define (last-pair items) (if (null? (cdr items)) (car items) (last-pair (cdr items))))
実行結果
gosh> (last-pair (list 1 2 3))
3
gosh> (last-pair (list 3 2 1))
1
gosh> (last-pair (list 11 2 3 5 6))
6
問題2.18
かなり時間がかかった。一番最初に書いたコードが、ひげぽんさんのコードと同じだった。なぜか、少し感激した。で、例題にでてきた手続きを使って、
(define (my-reverse items) (reverse-iter items (list-length items))) (define (reverse-iter lst cnt) (if (= cnt 1) (cons (car lst) '()) (cons (list-ref lst (- cnt 1)) (reverse-iter lst (- cnt 1)))))
のようにした。
これは、Cの配列の要領で各要素に後ろから（ディクリメントしながら）アクセスしていき、consでリスト化している。cntの初期値を、リストの個数にしている。
問題2.20
以下が、最初に書いたソース。
(define (odd-list lst) (if (odd? (car lst)) (if (null? (cdr lst)) (cons (car lst) '()) (cons (car lst) (odd-list (cdr lst)))) (if (null? (cdr lst)) '() (odd-list (cdr lst))))) (define (even-list lst) (if (odd? (car lst)) (if (null? (cdr lst)) '() (even-list (cdr lst))) (if (null? (cdr lst)) (cons (car lst) '()) (cons (car lst) (even-list (cdr lst)))))) (define (same-parity n . lst) (if (odd? n) (cons n (odd-list lst)) (cons n (even-list lst))))
長いし、何回も同じことをしていてかなり無駄のあるプログラムになってしまった。もっとキレイに書けないかなあ、と思って解答集を見たところ、
(define (same-parity h . ts) (define pred (if (even? h) even? odd?)) (define (filter p xs) (cond ((null? xs) xs) ((p (car xs)) (cons (car xs) (filter p (cdr xs)))) (else (filter p (cdr xs))))) (cons h (filter pred ts)))http://oss.timedia.co.jp/show/SICP/ex-2.20
とあった。これはスゴいきれい。高階手続きをつかって、うまく抽象化してる。これにならって、書きなおしてみたのが、コレ。
(define (same-parity-ex n . lst) (define judge (if (odd? n) odd? even?)) (define (filter judge lst) (if (null? (cdr lst)) lst (if (judge (car lst)) (cons (car lst) (filter judge (cdr lst))) (filter judge (cdr lst))))) (cons n (filter judge lst)))
まさに、高階手続きの強力さが身に染みた所である。
