使用數字列表的任意精度加法

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的功能，可以幫助我繼續處理空列表作爲零列表。

我引入了一個新的變量carry，它用於將值從迭代運送到迭代，就像手動執行一樣。

EDIT 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 '())) 

編輯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)))