произвольное добавление точности с использованием списков цифр

Question

Что я пытаюсь сделать, это взять два списка и добавить их вместе, как и каждый список - целое число.

(define (reverse lst) 
(if (null? lst) 
    '() 
    (append (reverse (cdr lst)) 
     (list (car lst))))) 

(define (apa-add l1 l2) 
    (define (apa-add-help l1 l2) 
    (cond ((and (null? l1) (null? l2)) '()) 
     ((null? l1) (list (+ (apa-add-help '() (cdr l2))))) 
     ((null? l2) (list (+ (apa-add-help (cdr l1) '())))) 

     ((>= (+ (car l1) (car l2)) 10) 
     (append (apa-add-help (cdr l1) (cdr l2))    
       (list (quotient (+ (car l1) (car l2)) 10)) 
       (list (modulo (+ (car l1) (car l2)) 10)))) ;this is a problem 

     (else (append (apa-add-help (cdr l1) (cdr l2)) 
        (list (+ (car l1) (car l2))))))) 

(apa-add-help (reverse l1) (reverse l2))) 

(apa-add '(4 7 9) '(7 8 4)) 
>'(1 1 1 5 1 3) 

Я знаю, что проблема вращалась вокруг моей рекурсии, я изменил порядок списков, чтобы для облегчения процесса, однако я не могу понять, как добавить мое по модулю значения (переносится значение) к следующему объекту в списке. Как я могу это сделать?

Answer 1

reverse уже определен в Racket, поэтому нет необходимости переопределять его.

Я переписан код для версии, которая яснее (для меня, по крайней мере):

(define (apa-add l1 l2) 

    (define (car0 lst) (if (empty? lst) 0 (car lst))) 
    (define (cdr0 lst) (if (empty? lst) empty (cdr lst))) 

    (let loop ((l1 (reverse l1)) (l2 (reverse l2)) (carry 0) (res '())) 
    (if (and (null? l1) (null? l2) (= 0 carry)) 
     res 
     (let* ((d1 (car0 l1)) 
       (d2 (car0 l2)) 
       (ad (+ d1 d2 carry)) 
       (dn (modulo ad 10))) 
      (loop (cdr0 l1) (cdr0 l2) (quotient (- ad dn) 10) (cons dn res)))))) 

, такие как

-> (apa-add '(4 7 9) '(7 8 4)) 
'(1 2 6 3) 
-> (+ 479 784) 
1263 

car0 и cdr0 являются функциями, которые помогают мне продолжить обработку пустые списки как список нулей.

Я ввел новую переменную переноса, которая используется для переноса значения с итерации на итерацию, так же, как вы делаете это вручную.

РЕДАКТИРОВАТЬ 1

named let эквивалентны следующий код:

(define (apa-add l1 l2) 

    (define (car0 lst) (if (empty? lst) 0 (car lst))) 
    (define (cdr0 lst) (if (empty? lst) empty (cdr lst))) 

    (define (apa-add-helper l1 l2 carry res) 
    (if (and (null? l1) (null? l2) (= 0 carry)) 
     res 
     (let* ((d1 (car0 l1)) 
       (d2 (car0 l2)) 
       (ad (+ d1 d2 carry)) 
       (dn (modulo ad 10))) 
      (apa-add-helper (cdr0 l1) (cdr0 l2) (quotient (- ad dn) 10) (cons dn res))))) 

    (apa-add-helper (reverse l1) (reverse l2) 0 '())) 

EDIT 2

, не входящие в хвостовой рекурсии версия будет

(define (apa-add l1 l2) 

    (define (car0 lst) (if (empty? lst) 0 (car lst))) 
    (define (cdr0 lst) (if (empty? lst) empty (cdr lst)))  

    (define (apa-add-helper l1 l2 carry) 
    (if (and (null? l1) (null? l2) (= 0 carry)) 
     '() 
     (let* ((d1 (car0 l1)) 
       (d2 (car0 l2)) 
       (ad (+ d1 d2 carry)) 
       (dn (modulo ad 10))) 
      (cons dn (apa-add-helper (cdr0 l1) (cdr0 l2) (quotient (- ad dn) 10)))))) 

    (reverse (apa-add-helper (reverse l1) (reverse l2) 0)))