関数型言語の勉強にSICPを読もう - (10) 2章 - データによる抽象の構築(59ページ)

問題2.20

この問題をぱっと見で解こうとしたらあっという間に、はまってしまったので簡単な要素に分けてみました


まずは数値のリストを受け取って、その中に含まれる偶数だけを返す関数を作ってみるのはどうでしょうか。

(define (collect-even list)
    (if (null? list)
        nil
        (if (even? (car list))
            (cons (car list)  (collect-even (cdr list)))
            (collect-even (cdr list)))))

;; (list 2 4 6)が返ってくるといいな
(collect-even (list 1 2 3 4 5 6))

結果

gosh> *** ERROR: unbound variable: nil
Stack Trace:
_______________________________________
  0  (collect-even (cdr list))
        At line 90 of "(stdin)"
  1  (collect-even (cdr list))
        At line 90 of "(stdin)"
  2  (collect-even (cdr list))
        At line 90 of "(stdin)"

うーん。正直よく分からない。
コンパイラなりインタプリタなりが吐くエラーメッセージはある程度慣れたプログラマにとっては非常に有用で、どこが間違っているかすぐに分かる場合が多いのですが、初心者にとっては???です。


というわけで更にもっと簡単なものから作ることに。
リストを受けとり、そのリストをそのまま返す関数(clone-list)。
受け取ったリストをcar/cdrで分解して再帰的にリストを作り直すという謎仕様。

その過程でやっと

(cdr nil)

がエラーの元であることを認識した。

関数はこんな感じ。

(define (clone-list l)
  (if (null? (cdr l))
      (list (car l))
      (cons (car l) (clone-list (cdr l)))))

(null? (cdr l))の条件判定がもっと簡単にかけそうな気がするけど。。
実行してみます。

(collect-even (list 1 2 3 4 5 6))
gosh> (1 2 3 4)

できた。
さてこれを偶数リストを返す関数に適用しようとすると(null? (cdr l))のところが問題になってうれしくないです。


いろいろ試行錯誤して clone-list はこう書くのがよさそう。

(define (clone-list l)
  (if (null? l)
      '()
      (cons (car l) (clone-list(cdr l)))))

これをベースに偶数リストを返す関数を作ってみる

(define (collect-even list)
    (if (null? list)
        '()
        (if (even? (car list))
            (cons (car list)  (collect-even (cdr list)))
            (collect-even (cdr list)))))
(collect-even (list 1 2 3 4 5 6))

結果

gosh> (2 4 6)

やった!。


そうか、リストの終端の部分にはまっていたのか。
ロジック部分に問題がなくて一安心。


さて長くなったので振り返りましょう。
問題2.20が難しかったので偶数リストを返す関数を作ってみたのでした。

奇数リストを返す関数も簡単にできそうなんだけど、どうせならかっこよく関数を引数で渡そう。

(define (collect f? list)
    (if (null? list)
        '()
        (if (f? (car list))
            (cons (car list)  (collect f? (cdr list)))
            (collect f? (cdr list)))))

引数 f? が #tのものだけを集める関数collect

(collect odd? (list 1 2 3 4 5 6))
(collect even? (list 1 2 3 4 5 6))
(collect (lambda (x) (= 3 x)) (list 1 2 3 4 5 6))

lambda式が背伸びした感じで良いですね。
ここまで来れば所望の関数は簡単。

(define (hoge a . b)
  (define (collect f? list)
    (if (null? list)
        '()
        (if (f? (car list))
            (cons (car list)  (collect f? (cdr list)))
            (collect f? (cdr list)))))
  (cons a (collect (if (even? a) even? odd?) b)))

第一引数の偶奇に合わせてcollectに仕事を任せるだけ。
結果

(hoge 2 3 4 5 6 7)
gosh> (2 4 6)
(hoge  3 4 5 6 7)
gosh> (3 5 7)

デバッグについて

デバッグが難しいと感じる。
大きな関数のデバッグは他の言語の経験から、ここの小さな関数レベルでテストや動作確認をすれば良いだけなのであまり問題がない。
困るのは小さい関数の場合。
慣れている言語であれば、小さな関数であればどこがおかしいか経験上すぐ見つけられるのですが、新しく学び始めるとノートに置換法で書いていってロジックミスを見つけるしかないってのがとても苦しく感じます。


処理系がどういう場合にどんなエラーを吐くか?というのは、処理系依存なのは当たり前なんですが、それ以外にもやはり言語特有の癖ってのがあると感じています。

*** ERROR: unbound variable: nil
Stack Trace:

これはよく見るエラーなんだけど

(cdr nil)
とか
(cons 1 nil)

とかをやってしまうとこのエラーになります。
これが分かるまでかなり苦労しました。

追記

後にdan kogaiさんからtraceを教わりました。
えSICPを読もう - (6) 1章 - 小休止 traceを使えるようにする」が参考になれば幸いです。


※「SICPを読もう」の目次はこちら


計算機プログラムの構造と解釈
Gerald Jay Sussman Julie Sussman Harold Abelson 和田 英一
ピアソンエデュケーション (2000/02)
売り上げランキング: 56,404