"Addition of arbitrary precision numbers" in Scheme

Question

I am trying to add two numbers (from lists) together in scheme while preserving list format. However, when the numbers being used for calculations add to something greater than or equal to 10 I get an undesired result. For example:

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

(define (apa-add lst1 lst2)
  (cond ((null? lst1) lst2)
    ((null? lst2) lst1)
    ((>= (+ (car lst1) (car lst2)) 10) 
     (append (apa-add (cdr lst1) (cdr lst2)) 
         (list (quotient(+ (car lst1) (car lst2)) 10)) 
         (list (modulo (+ (car lst1) (car lst2)) 10))))
        (else 
         (append (apa-add (cdr lst1) (cdr lst2))
         (list (+ (car lst1) (car lst2)))))))

(apa-add (reverse '(4 4 5)) (reverse'(3 5 8)))

returns

'(7 9 1 3)

How can I modify my code to fix this error? I wanted to use a let statement so I could add the evaluation of (quotient (+ (car lst1) (car lst2)) 10) to (list (+ (car lst1) (car lst2))) of the next call, but I couldn't think of how to do this.

Answer 1

Making this into a tail call simplifies things a bit.

(define (apa-add lst1 lst2)
  (let loop ((carry 0) (L1 (reverse lst1)) (L2 (reverse lst2)) (sum '()))
     (cond ((and (null? l1) (null? l2)) 
            (if (zero? carry) sum (cons carry sum)))
           ((null? L1) 
            (loop (quotient (+ carry (car l2)) 10)
                  '() 
                  (cdr L2) 
                  (cons (modulo (+ carry (car l2)) 10) sum)))
           ((null? L2) 
            (loop (quotient (+ carry (car l1)) 10)
                  (cdr l1) 
                  '() 
                  (cons (modulo (+ carry (car l1)) 10) sum)))
           (else  
            (loop (quotient (+ carry (car l1) (car l2)) 10)
                  (cdr l1) 
                  (cdr l2)
                  (cons (modulo (+ carry (car l1) (car l2)) 10) sum))))))              



(apa-add (list 4 4 5) (list 3 5 8))

;Value 4: (8 0 3)

probably wouldnt be too hard to convert to an n-arity function.

(define (apa-add . Lists)
  (define (cdrs-no-null L)
               (cond ((null? L) '())
                     ((null? (cdar l)) (cdrs-no-null (cdr L)))
                     (else (cons (cdar l) (cdrs-no-null (cdr l))))))
    (let loop ((carry 0) (Lists (map reverse Lists)) (sum '()))
          (if (null? Lists)
              (if (zero? carry) sum (cons carry sum))
              (loop (quotient (fold + carry (map car Lists)) 10)
                    (cdrs-no-null Lists)
                    (cons (modulo  (fold + carry (map car Lists)) 10) sum)))))

(apa-add (list 4 4 5) (list 3 5 8) (list 1 0 2 7))

;Value 11: (1 8 3 0)

(apa-add (list 4 4 5) (list 3 5 8))

;Value 12: (8 0 3)