■
sicp lite#13 に参加させていただきました。
いろいろなお話を聞くことが出来てとても楽しかったです。ありがとうございました。
さて、 sicp lite #13 は前回の宿題だった問題 3.17〜3.20 をやりました。
問題 3.17 は「リストを引数に取り、リストの中に含まれる pair の数を返す関数を定義せよ」って内容ですね。
この問題のおもしろいポイントは以下のとおり。
- 枝分かれしても数えられるようにする
- ループしてても数えられるようにする
- 枝分かれした先が別の枝に合流してても数えられるようにする
節3.3では set! を使ってリストを書き換える方法と
その問題点が解説されていましたが、この問題では set! は要りません。
まず cdr が終端に辿り着くまで下っていき、
枝分かれがあればそこも数えていきます。
コードにするとこんな感じですね。
(define (count-pairs l) (define (iter l counted-list) (cond ((null? l) counted-list) ((not (pair? l)) counted-list) ((memq l counted-list) counted-list) (else (let ((cdr-result (iter (cdr l) (cons l counted-list)))) (let ((car-result (iter (car l) cdr-result))) car-result))))) (length (iter l '())))
ただ、この関数あまりテストしてません。
ループしたり合流したりするテスト用のリスト構造を作るのが面倒だったからです。
テスト用のリストを作る関数もそのうち作らなきゃいけませんね。