PasteRack.org
Paste # 60635
2025-01-25 21:09:24

Fork as a new paste.

Paste viewed 392 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 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.     ;; if the two lists are both empty...
  17.     [('() '())
  18.      ;; emit a trailing digit if required by the carry
  19.      (cond [(= carry 0) '()]
  20.            [else (list carry)])]
  21.     ;; otherwise, sum the first two digits and the carry,
  22.     ;; and continue
  23.     [('() (cons f r)) (numlist-continue  (+ f carry) '() r)]
  24.     [((cons f r) '()) (numlist-continue  (+ f carry) '() r)]
  25.     [((cons f1 r1) (cons f2 r2))
  26.      (numlist-continue (+ f1 f2 carry) r1 r2)]))
  27.  
  28. ;; given a sum (possibly between 10 and 20), and the rest
  29. ;; of each list, return the numlist formed by summing them
  30. (define (numlist-continue sum new-a new-b)
  31.   (define new-carry (cond [(<= 10 sum) 1]
  32.                           [else 0]))
  33.   (define digit (modulo sum 10))
  34.   (cons digit (numlist-sum/helper new-a new-b new-carry)))
  35.  
  36. ;; some test cases
  37. (check-equal? (numlist-sum '() '()) '())
  38. (check-equal? (numlist-sum '(1 3) '()) '(1 3))
  39. (check-equal? (numlist-sum '() '(1 3)) '(1 3))
  40. (check-equal? (numlist-sum '(9) '(2)) '(1 1))
  41. (check-equal? (numlist-sum '(3 4 2 9 8) '(2 4 9)) '(5 8 1 0 9))
  42.  

=>