Hilft bei der Verständnis der Kontinuationen im Schema

Question

Ich habe neben Der kleine Schemier Schema lernen und PLT-Scheme für meine Umgebung verwenden.

Der kleine Schemier Hat mir enorm mit Rekursion geholfen (es ist jetzt für mich einfach), aber ich stecke an einem Teil des Buches fest, der "Sammler" einführt und die Funktion als Ganzes als Fortsetzung bezeichnet.

Hier ist der Beispielcode, den sie verwendet haben. Ich verstehe die rekursiven Elemente, aber ich stecke fest, insbesondere in den Lambda -Funktionen - mein Verstand kann dem Weg nicht folgen und wie die Argumente für diese Lambda -Funktion festgelegt werden Keine konkrete Verwendung innerhalb des Funktionskörpers).

Wenn mir jemand mehr oder weniger den Berechnungspfad durch die Rekursion der Funktion in die Lambda-Sammler abbauen könnte, kann dies mir helfen.

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

Danke im Voraus!!

Answer 1

Versuchen Sie etwas Einfachenderes, um zu sehen, wie dies funktioniert. Zum Beispiel hier eine Version von a list-sum Funktion, die ein Fortsetzungsargument erhält (das oft genannt wird k):

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

Das grundlegende Muster ist da und die fehlenden Teile sind dort, wo die interessanten Dinge passieren. Das Fortsetzungsargument ist eine Funktion, die erwartet, das Ergebnis zu erhalten. Wenn die Liste also null ist, ist klar, dass wir es senden sollten 0, da das die Summe ist:

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

Wenn die Liste nicht null ist, nennen wir die Funktion rekursiv mit dem Schwanz der Liste (mit anderen Worten, dies ist eine Iteration), aber die Frage ist, was die Fortsetzung sein sollte. Dies tun:

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

ist eindeutig falsch - das bedeutet das k wird irgendwann die Summe von erhalten (cdr l) anstelle von allen l. Verwenden Sie stattdessen dort eine neue Funktion, die das erste Element von zusammenfasst l auch zusammen mit dem Wert, den es erhält:

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

Das kommt näher, aber immer noch falsch. Aber es ist ein guter Punkt, darüber nachzudenken, wie die Dinge funktionieren - wir rufen an list-sum Mit einer Fortsetzung, die selbst die Gesamtsumme erhält, und den ersten Artikel hinzuzufügen, den wir jetzt sehen. Der fehlende Teil zeigt sich darin, dass wir ignorieren k. Was wir brauchen, ist komponieren k Mit dieser Funktion - also machen wir den gleichen Summenoperation und senden dann das Ergebnis an an k:

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

Welches funktioniert endlich. (Übrigens, denken Sie daran, dass jeder von diesen lambda Funktionen haben eine eigene "Kopie" von l.) Sie können dies mit:

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

Und schließlich beachten Sie, dass dies derselbe ist wie:

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

Wenn Sie die Komposition explizit machen.

(Sie können diesen Code auch in der Intermediate+Lambda Student Language verwenden und auf die Taste Stepper klicken, um festzustellen Mit seiner eigenen Sicht auf die Liste.)

Answer 2

Hier ist eine Möglichkeit, Ihnen zu helfen, "eine konkretere Idee zu bekommen". Stellen Sie sich vor, der Sammler wäre so definiert:

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

Sie können im Basisfall sehen, wenn Sie eine leere Liste übergeben, werden Ihre Funktion mit Argumenten aufgerufen '(), 1 und 0. Arbeiten Sie jetzt mit einer Ein-Element-Liste und sehen Sie, womit sie Ihre Funktion nennt. Arbeiten Sie mit längeren und längeren Listen weiter, bis Sie herausfinden, was los ist.

Viel Glück!