The Little Schemerを読み解く ~ multirember&co

前置き

The Little Schemer(邦題は「Scheme手習い」)を読みました。自分にとって難所だったmultirember&coについてメモっておきます。登場するのはペーパーバック 4th EditionのP137です。

本文

定義

multirember&co
(define multirember&co
  (lambda (a lat col)
    (cond
      ((null? lat)       (col (quote ()) (quote ())))                    ;;①
      ((eq? (car lat) a) (multirember&co                                 ;;②
                           a
                           (cdr lat)
                           (lambda (newlat seen)
                             (col newlat (cons (car lat) seen)))))
      (else              (multirember&co                                 ;;③
                           a
                           (cdr lat)
                           (lambda (newlat seen)
                             (col (cons (car lat) newlat) seen)))))))

名前

名前から読み取れるのは以下の点です。

  • remberは、removeとmemberを合わせた造語
  • aは、atom
  • latは、list of atom
  • remberは、latの中の最初のaを削除して新しいlat(つまりnewlat)を返す
  • multiremberは、latの中の全てのaを削除したnewlatを返す
  • coとcolは、collector、あるいはcontinuation(継続)の略
  • 「継続」は「後続の処理」のような意味
  • よってmultirember&coは、「multiremberし、そしてcolせよ」というニュアンス
  • seenは「見終わったやつ」、つまりremoved-latのこと

メカニズム

  • multirember&coは、3つの引数(a, lat, col)を取る
  • colは、2つの引数を取るらしい
  • multirember&coの本体は、condで3分岐
  • ①latが空リストの場合、②latの先頭がaと一致する場合、③latの先頭がaと一致しない場合
  • ②と③では再帰しており、第2引数は(cdr lat)
  • つまり再帰するたびに、latは空リストに近づいていく
  • よって、いずれは①に分岐するはず
  • ②も③も、新しいcolを定義して再帰の第3引数に渡す
  • ②も③も新しいcolの中で古いcolを呼ぶが、そのときの引数は②と③とで異なる
  • ②の場合は、newlatと、(cons (car lat) seen)
  • ③の場合は、(cons (car lat) newlat)と、seen

以上より、latの要素を1つずつ取り出しながら、aと一致すればseenへ、一致しなければnewlatへ挿入していく姿が想像できます。で、latが空っぽになったら、その時点の最新のcolを2つの空リストへ適用します(①)。

colの例として、以下の関数を使います(P138のa-friendと同じです)。

col0
(define col0
  (lambda (x y) (null? y)))

これを使って、

(multirember&co 'tuna '(strawberries tuna and swordfish) col0)

を評価してみましょう。

  • 1周目は③へ分岐し、新しいcol1は、(col0 (cons 'strawberries newlat) seen)
  • 2周目は②へ分岐し、新しいcol2は、(col1 newlat (cons 'tuna seen))
  • 3周目は③へ分岐し、新しいcol3は、(col2 (cons 'and newlat) seen)
  • 4周目は③へ分岐し、新しいcol4は、(col3 (cons 'swordfish newlat) seen)
  • 5周目は①へ分岐し、(col4 '() '())を評価する
  • (col3 '(swordfish) '())を評価
  • (col2 '(and swordfish) '())を評価
  • (col1 '(and swordfish) '(tuna))
  • (col0 '(strawberries and swordfish) '(tuna))
  • 結果は#f

まさに、「multiremberし、そしてcolせよ」って感じですよね。'(strawberries tuna and swordfish)から'tunaをmultiremberし、そしてcol0すると、1つ以上tunaを見つけたかどうかが分かる、というわけです。

colが2つの引数を取るおかげで、multiremberから2つの出力を得ている点にも注意しましょう。multiremberがlatを走査する過程で得た情報をcolの引数に蓄積していくイメージです。これがcollectorとも呼ばれる由来でしょう。colの引数を3つに増やして、「何番目にaを見つけたか」という情報を蓄積することもできそうです。

Last modified:2013/04/07 22:51:28
Keyword(s):
References:[FP: 関数型プログラミング] [Schemeの継続とcall/cc]
This page is frozen.