43

私はThe Little Schemerと協力して Scheme を学び、自分の環境で PLT-Scheme を使用しています。

The Little Schemerは再帰を大いに助けてくれました (今の私にとっては簡単です) が、「コレクター」を紹介し、関数全体を継続と呼んでいる本の一部に行き詰まっています。

これが彼らが使用したサンプルコードです。私は再帰要素を理解していますが、特にラムダ関数で行き詰まっています - 私の心はパスとそのラムダ関数の引数がどのように設定されているかをたどることができません（それらの唯一の呼び出しは再帰でそれらを再度呼び出すことであるため、関数本体内での具体的な使用はありません)。

ラムダ コレクターへの関数の再帰を介した計算のパスの内訳を誰かが多かれ少なかれ教えてくれれば、それは私を助けるかもしれません。

;; Build a nested list of even numbers by removing the odd ones from its
;; argument and simultaneously multiply the even numbers and sum the odd
;; numbers that occur in its argument.
(define (even-only-collector l col)
  (cond
    ((null? l)
      (col (quote ()) 1 0))
    ((atom? (car l))
      (cond
        ((even? (car l))
          (even-only-collector (cdr l)
            (lambda (newl p s)
              (col (cons (car l) newl)
                (* (car l) p) s))))
         (else
           (even-only-collector (cdr l)
             (lambda (newl p s)
               (col newl
                 p (+ (car l) s)))))))
    (else
      (even-only-collector (car l)
        (lambda (al ap as)
          (even-only-collector (cdr l)
            (lambda (dl dp ds)
              (col (cons al dl)
                (* ap dp)
                (+ as ds)))))))))

;; The collector function
(define (collector newl product sum)
  (cons sum
    (cons product newl)))

前もって感謝します！！

4

2 に答える 2

43

これがどのように機能するかを確認するために、もっと簡単なことを試してみてください。たとえば、list-sumこれは継続引数を受け取る関数のバージョンです (これはしばしば と呼ばれkます):

(define (list-sum l k)
  (if (null? l)
    ???
    (list-sum (cdr l) ???)))

そこには基本的なパターンがあり、欠けている部分で面白いことが起こります。continuation 引数は、結果を受け取ることを期待する関数です。つまり、リストが null の場合0、合計であるため、それを送信する必要があることは明らかです。

(define (list-sum l k)
  (if (null? l)
    (k 0)
    (list-sum (cdr l) ???)))

ここで、リストが null でない場合、リストの末尾を使用して関数を再帰的に呼び出します (つまり、これは反復です) が、問題は継続がどうあるべきかです。これを行う：

(define (list-sum l k)
  (if (null? l)
    (k 0)
    (list-sum (cdr l) k)))

は明らかに間違っています。これは、が最終的に のすべてではなく のk合計を受け取ることを意味します。代わりに、 too の最初の要素と受け取った値を合計する新しい関数を使用します。(cdr l)ll

(define (list-sum l k)
  (if (null? l)
    (k 0)
    (list-sum (cdr l) (lambda (sum) (+ (car l) sum)))))

これは近づいていますが、まだ間違っています。しかし、物事がどのように機能しているかを考えるのは良い点です。list-sum全体の合計を受け取り、現在表示されている最初のアイテムをそれに追加する継続を呼び出しています。欠落している部分は、無視しているという事実から明らかですk。必要なのは、この関数で構成する kことです。つまり、同じ合計演算を行い、結果を に送信しますk。

(define (list-sum l k)
  (if (null? l)
    (k 0)
    (list-sum (cdr l) (compose k (lambda (s) (+ s (car l)))))))

これは最終的に機能しています。(ところで、これらのlambda関数にはそれぞれ独自の の「コピー」があることにl注意してください。) これは次の方法で試すことができます。

(list-sum '(1 2 3 4) (lambda (x) x))

最後に、これは次と同じであることに注意してください。

(define (list-sum l k)
  (if (null? l)
    (k 0)
    (list-sum (cdr l) (lambda (s) (k (+ s (car l)))))))

構成を明確にする場合。

(このコードを中間 + ラムダ学生言語で使用し、ステッパー ボタンをクリックして、評価がどのように進行するかを確認することもできます。これには時間がかかりますが、継続関数がどのようにネストされているかがわかります。リストの独自のビューで。)

于 2010-01-07T04:32:34.307 に答える
1

「より具体的なアイデアを得る」ための 1 つの方法を次に示します。コレクターが次のように定義されていると想像してください。

(define (collector l p s)
  (display l)
  (newline)
  (display p)
  (newline)
  (display s)
  (newline))

基本ケースで、空のリストを渡すと、引数'()、1、および 0 を使用して関数が呼び出されることがわかります。次に、1 要素のリストを操作し、関数を呼び出すものを確認します。何が起こっているのかを理解するまで、リストをどんどん長くして作業を続けてください。

幸運を！

于 2010-01-07T03:27:27.777 に答える