Schemeの課題をあの実装で　の4 - .mjtの日記復帰計画

今回はmosh。

mosh

http://code.google.com/p/mosh-scheme/

インストールに関しては先日書いた(多少更新)。

http://d.hatena.ne.jp/mjt/20081203/p1

今回の目的のためだけならば、特にSVN版を使用する必要は無い。リリース版(.tar.gzでダウンロードできるもの)は、Gaucheやmoshが無くてもビルドできる。

SICP ex 2.33

mapやappend、lengthを作る。これらを作るにあたって、以下のようなaccumulateを使用することとする。

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence) (accumulate op initial (cdr sequence)))))

ヒントとして与えられている２つの事例は重要。３つの課題はこれらのヒントの変形でしかない。

(accumulate + 0 '(1 2 3 4 5)) ; リストの総和
(accumulate cons '() '(1 2 3 4 5)) ; リストをそのまま返す

前者がなぜ総和を返すのかを考える。総和のaccumulateを展開すると次のようになる。

(+ 1 (+ 2 (+ 3 (+ 4 (+ 5 0)))))

これは確かにリストの総和をあらわしている。
mapは次のように作ることが出来る。

(define (my-map p sequence)
  (accumulate (lambda (x y) (cons (p x) y) ) '() sequence))

後者の例と比較するために、まず、consをlambdaで書き直してみる。

cons = (lambda (x y) (cons x y))

これを、my-mapで渡しているクロージャと比較すると、consのxをpで処理していることが分かる。
同様に、lengthも例からの類推で考えることが出来る。前者の例は、リストの要素がすべて1であったときだけlengthとして働くことがわかる。そのため、+のパラメタの片方を無理やり1にしてしまえばどのようなリストでもlengthとして働くことが分かる。

をlambdaで書き直すと、

+ = (lambda (x y) (+ x y)) ;この+は複数のパラメタを取れない

となり、常に1だけ加えたければ、xを「無視」して1に置き換えてしまえば良い。基本的にlambdaに渡された引数はすべて消費しなくても良い。

(define (my-length sequence)
  (accumulate (lambda (x y) (+ 1 y)) 0 sequence))

xとyを逆にするとうまく行かない。
appendは後者の例から考える。

(define (myappend seq1 seq2)
  (accumulate cons seq2 seq1))

引数の順序に注意する。

moshでの検証

moshのように開発中の実装は、基本的にユーザのエラーに寛容でない*1ので、予め入力すべき式をファイルに保存しておくことが望ましい。
moshのREPLにはloadやload後の対話モード*2が無いので、テスト用の式もファイルに書きこんでおく。

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence) (accumulate op initial (cdr sequence)))))

(define (my-map p sequence)
  (accumulate (lambda (x y) (cons (p x) y) ) '() sequence))

(define (my-append seq1 seq2)
  (accumulate cons seq2 seq1))

(define (my-length sequence)
  (accumulate (lambda (x y) (+ 1 y)) 0 sequence))

;;; tests
(display (my-map (lambda (x) (+ 1 x)) '(1 2 3 4 5)))
(display "   (= (2 3 4 5 6))")
(newline)
(display (my-append '(1 2 3 4 5) '(6 7 8 9 10)))
(display "   (= (1 2 3 4 5 6 7 8 9 10))")
(newline)
(display (my-length '(1 "two" "three" 4 #f)))
(display "   (= 5)")
(newline)