Schéma: récursivité et listes

Question

J'ai essayé d'apprendre un peu de programmation par moi-même en travaillant sur le manuel How to Design Programs for Scheme. J'ai tout traversé jusqu'à maintenant. Voici le problème:

9.5.5 Développer la fonction convertir. Il consomme une liste de chiffres et produit le nombre correspondant. Le premier chiffre est le moins significatif, et ainsi de suite.

Après les premières étapes, à partir de l'analyse des données à modèle, je finis avec cela, les os nus d'un programme:

;; A list-of-numbers is either 1. an empty list, empty, or 2. (cons n 
lon) where n is a number and lon is a list of numbers 
;; convert : lon -> number 
;; to consume a lon and produce the corresponding number. The least 
significant digit corresponds to the first number in the list, and so 
on. 
;; (= (convert (cons 1 (cons 9 (cons 10 (cons 99 empty))))) 991091) 
(define (convert lon) 
    (cond 
    [(empty? lon)...] 
    [(cons? lon)...(first lon)...(convert (rest lon))...])) 

Comment puis-je obtenir passé ce stade, comme livre a-t-il, "combinant des valeurs"? La seule façon de penser pourrait travailler est si je multiplié la première valeur par 10 à la puissance de l'importance de la valeur dans le nombre total, par exemple,

(CONS 1 (contre 9 vide)) => 1 * 10^(SIGNIFICANCE), où MOINS SIGNIFICANCE serait 0. En utilisant ma compréhension limitée de la programmation , je suppose que cela nécessite un compteur, où n augmente de un chaque fois que la fonction, en quelque sorte, est appelée récursivement. Mais cela me semble être une tentative d'exécuter deux récursions en même temps. Étant donné que les expressions sont évaluées de manière séquentielle (évidemment), vous ne pouvez pas appeler la fonction de compteur lorsque vous appelez la fonction de conversion .

Alors, quelqu'un peut-il m'aider à résoudre ce problème? Je préférerais si vous résolu cela en utilisant la récursivité naturelle et le CONStructor pour les listes et pas lambda ou d'autres idées que le livre n'a pas encore abordé.

Merci!

Answer 1

Vous n'avez pas besoin de faire de l'exponentiation - une simple multiplication fera l'affaire.

(define (convert digits) 
    (cond 
    ((empty? digits) 0) 
    (else (+ (* 10 (convert (rest digits))) (first digits))) 
) 
) 

(convert '(1 2 3 4 5 6)) 

Ou, une autre façon de penser:

(define (convert digits) 
    (convert-helper digits 1 0) 
) 

(define (convert-helper digits multiplier sofar) 
    (cond 
    ((empty? digits) sofar) 
    (else 
     (convert-helper 
      (rest digits) 
      (* 10 multiplier) 
      (+ (* multiplier (first digits)) sofar) 
     ) 
    ) 
) 
) 


(convert '(1 2 3 4 5 6)) 

Answer 2

est ici une version récursive de la queue:

(define (convert lon) 
    (let rec ((i 0) 
      (n 0) 
      (lon lon)) 
    (cond ((empty? lon) n) 
      (else (rec (+ i 1) 
        (+ n (* (first lon) (expt 10 i))) 
        (rest lon))))))