Aide à la compréhension des suites dans Scheme

Question

J'ai travaillé aux côtés de La Petite Intrigant à l'apprenant et à l'aide de PLT-Schéma de mon environnement.

Le Petit Intrigant m'a aidé énormément avec la récursivité (c'est simple pour moi pour l'instant) mais je suis bloqué sur une partie d'un livre qui présente les "collectionneurs" et appelle l'ensemble de la fonction continuation.

Voici l'exemple de code qu'ils ont utilisés. Je comprends le récursive éléments, mais je suis coincé, en particulier sur les lambda fonctions - mon esprit ne peut pas suivre le chemin d'accès et comment les arguments de cette fonction lambda sont fixés (puisque leur seul appel est de les appeler de nouveau à la récursivité, il n'est pas concret d'utilisation dans le corps de la fonction).

Si quelqu'un pourrait-plus-ou-moins me donner une pause en bas de la voie de calcul par le biais de la récursivité de la fonction dans le lambda collectionneurs, qui peut m'aider.

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

Je vous remercie à l'avance!!!!

Answer 1

Essayez quelque chose de plus simple pour voir comment cela fonctionne. Par exemple, voici une version d'un list-sum fonction qui reçoit une poursuite argument (qui est souvent appelé k):

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

Le motif de base est là, et les parties manquantes sont où les choses intéressantes se produisent. La poursuite de l'argument est une fonction qui attend de recevoir le résultat, donc, si la liste est null, il est clair qu'on devrait l'envoyer en 0, puisque c'est la somme:

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

Maintenant, lorsque la liste n'est pas nul, nous appelons la fonction de manière récursive avec la liste de la queue (en d'autres termes, c'est une itération), mais la question est de savoir quelle devrait être la continuation de l'être. Pour ce faire:

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

est clairement mauvais, cela veut dire qu' k recevra finalement la somme des (cdr l) au lieu de tout l. Au lieu de cela, utiliser une nouvelle fonction, ce qui somme le premier élément de l trop avec la valeur qu'il reçoit:

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

Ceci se rapproche, mais toujours mal. Mais c'est un bon point de penser à la façon dont les choses fonctionnent -- nous appelons list-sum avec une poursuite que lui-même va recevoir la somme globale, et ajouter le premier élément que nous voyons maintenant à elle. La partie manquante est évident dans le fait que nous sommes en ignorant k. Ce dont nous avons besoin est de composer k avec cette fonction, -- si nous faisons la même opération de somme, puis envoyer le résultat à l' k:

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

qui est finalement de travail. (BTW, n'oubliez pas que chacun de ces lambda fonctions a son propre "copie" de l.) Vous pouvez aussi essayer avec:

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

Et enfin, notez que c'est la même chose que:

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

si vous faites la composition explicite.

(Vous pouvez également utiliser ce code dans les intermédiaires+lambda étudiant de la langue, et cliquez sur la flèche de défilement bouton pour voir comment l'évaluation se déroule -- cela va prendre un certain temps à aller plus, mais vous verrez comment le maintien des fonctions d'obtenir imbriquées, chacune avec son propre point de vue de la liste.)

Answer 2

Voici un moyen de vous aider à "avoir une idée plus concrète". Imaginez si le collecteur était défini ainsi:

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

Vous pouvez voir dans le cas de base que si vous transmettez une liste vide, la fonction sera appelée avec les arguments '() , 1 et 0. Utilisez maintenant une liste à un élément et voyez ce qu'elle Je vais appeler votre fonction avec. Continuez à travailler avec des listes de plus en plus longues, jusqu'à ce que vous compreniez ce qui se passe.

Bonne chance!