PasteRack.org
Paste # 44000
2025-01-25 20:45:52

Fork as a new paste.

Paste viewed 381 times.


Embed:

add two lists of digits representing a natural number

  1. #lang racket
  2.  
  3. (require rackunit)
  4.  
  5. ;; a numlist is either
  6. ;; - (cons <digit> <numlist>), or
  7. ;; - '()
  8.  
  9. ;; sum the two numlists
  10. (define (numlist-sum a b)
  11.   (numlist-sum/helper a b 0))
  12.  
  13. ;; sum the two numlists with a carry digit
  14. (define (numlist-sum/helper a b carry)
  15.   (match* (a b)
  16.     [('() '())
  17.      (cond [(= carry 0) '()]
  18.            [else (list carry)])]
  19.     [('() (cons f r)) (numlist-continue  (+ f carry) '() r)]
  20.     [((cons f r) '()) (numlist-continue  (+ f carry) '() r)]
  21.     [((cons f1 r1) (cons f2 r2))
  22.      (numlist-continue (+ f1 f2 carry) r1 r2)]))
  23.  
  24. ;; given a sum (possibly between 10 and 20), and the rest
  25. ;; of each list, return the numlist formed by summing them
  26. (define (numlist-continue sum new-a new-b)
  27.   (define new-carry (cond [(<= 10 sum) 1]
  28.                           [else 0]))
  29.   (define digit (modulo sum 10))
  30.   (cons digit (numlist-sum/helper new-a new-b new-carry)))
  31.  
  32. (check-equal? (numlist-sum '() '()) '())
  33. (check-equal? (numlist-sum '(1 3) '()) '(1 3))
  34. (check-equal? (numlist-sum '() '(1 3)) '(1 3))
  35. (check-equal? (numlist-sum '(9) '(2)) '(1 1))
  36. (check-equal? (numlist-sum '(3 4 2 9 8) '(2 4 9)) '(5 8 1 0 9))
  37.  

=>