☰

「The Little Schemer」の137ページの続きの例を説明してください。質問する

tag-icon • tag-icon recursion lambda scheme continuation-passing the-little-schemer
「The Little Schemer」の137ページの続きの例を説明してください。質問する

問題となっているコードは次のとおりです。

(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))))))

一日中これを見つめていましたが、よく理解できません。関数を再帰的に使用すると再定義しますが、例では元の定義を使用しているようです。なぜ変更しないのでしょうか。colパラメーターを渡さずに再帰的に使用するにはどうすればよいでしょうかnewlat。seen

何かが足りないようなので、質問を説明するのは難しいです。本よりももっと明確な説明をしていただければ、仕組みを理解できるかもしれません。

ベストアンサー1

list例を一つずつ見ていきましょう。役に立つかもしれません。:-) 簡単にするために、コレクター/継続として を使用します。これは、継続への引数を含むリストを返すだけです。

(multirember&co 'foo '(foo bar) list)

開始時、

a = 'foo
lat = '(foo bar)
col = list

最初の反復では、は空ではなく、 の最初の要素はである(eq? (car lat) a)ため、条件が一致します。これにより、次の再帰が次のように設定されます。latlat'foomultirember&co

a = 'foo
lat = '(bar)
col = (lambda (newlat seen)
        (list newlat (cons 'foo seen))

次の反復では、 はelse一致します。 はlat空ではなく、 の最初の要素はlatです'bar( ではありません'foo)。したがって、次の再帰では次のようになります。

a = 'foo
lat = '()
col = (lambda (newlat seen)
        ((lambda (newlat seen)
           (list newlat (cons 'foo seen)))
         (cons 'bar newlat)
         seen))

人間が読みやすくするために（そして混乱を避けるために）、プログラムのセマンティクスを変更せずに、パラメータの名前を変更することができます（レキシカルスコープのため）。

col = (lambda (newlat1 seen1)
        ((lambda (newlat2 seen2)
           (list newlat2 (cons 'foo seen2)))
         (cons 'bar newlat1)
         seen1))

最後に、(null? lat)節は空になったので一致しますlat。そこで、

(col '() '())

これは次のように展開されます。

((lambda (newlat1 seen1)
   ((lambda (newlat2 seen2)
      (list newlat2 (cons 'foo seen2)))
    (cons 'bar newlat1)
    seen1))
 '() '())

これを（newlat1 = '()とを代入するとseen1 = '()）

((lambda (newlat2 seen2)
   (list newlat2 (cons 'foo seen2)))
 (cons 'bar '())
 '())

または（評価中(cons 'bar '())）

((lambda (newlat2 seen2)
   (list newlat2 (cons 'foo seen2)))
 '(bar)
 '())

ここで、とを代入するnewlat2 = '(bar)とseen2 = '()、次の式が得られます。

(list '(bar) (cons 'foo '()))

言い換えれば、

(list '(bar) '(foo))

最終結果を出すために

'((bar) (foo))

おすすめ記事