Decompose a list of numbers into digits

Question

I am trying to create a list of digits starting from a list of numbers. For example I want to break (11 4 6) into (1 5 6) by dividing the head of the list to 10 if the head is >= 10 and adding 1 to the next element.
My code looks like this

(defun createparameters (l)
  (cond ((null l) l)
        ((> 9 (car l)) (setf (car l) (mod (car l ) 10))
                       (setf (cadr l) (+ (cadr l) 1)))
        (t (createparameters (cdr l)))))

but it does not change my referenced list. Help would be greatly appreciated.

Answer 1

You write that you want the operation done if the first element is greater than 9, but in your code you are doing the opposite. (> 9 (car l)) is the same as infix 9 > (car l) so you do your thing when first element is 8 or lower.

Here is a functional version of your code that continues to process the next sublist:

(defun createparameters (l)
  (cond ((null l) l)
        ((and (consp l) (< 9 (car l)))
         (cons (mod (car l ) 10) 
               (createparameters 
                (cons (+ (cadr l) 1) 
                      (cddr l)))))
        (t (cons (car l) 
                 (createparameters (cdr l))))))

(defparameter test (list 11 11 2 3))
(setf test (createparameters test))
test ; ==> (1 2 3 3)

Here is a modified mutating version (similar to your code):

(defun createparameters (l)
  (cond ((null l) l)
        ((< 9 (car l)) (setf (car l) (mod (car l ) 10))
                       (setf (cadr l) (+ (cadr l) 1))
                       (createparameters (cdr l)))
        (t (createparameters (cdr l)))))

(defparameter test (list 11 11 2 3))
(createparameters test)
test ; ==> (1 2 3 3)

I'm starting to wonder if this is a carry so that the first element is the least significant digit and the last is the most. If so just adding one will only work if the number always are below 20 and the code will not work if the last digit became 10 or higher.

Answer 2

A direct approach

Here's a version that performs the task directly.

(defun decompose (digits)
  "Given a list of digits (least-significant digit first), return a
list of normalized digits, i.e., where each digit is less than 10."
  (do ((digits digits (rest digits))    ; iterate through the digits.
       ;; There's no initial digit, and the carry is initially 0.
       (carry 0) (digit)
       ;; The result starts as '(), and adds a digit on each successive
       ;; iteration, where the digit is computed in the loop body.
       (result '() (list* digit result)))
      ;; End when there are no digits left.  Most of the result is 
      ;; simply the reversed result, but if there's a non-zero carry
      ;; at the end, put it into a list and decompose it, too.
      ((endp digits)                    
       (nreconc result (if (zerop carry) '() 
                           (decompose (list carry))))) 
    ;; At each iteration, add the first digit to the carry, and divide
    ;; by 10.  The quotient is the carry for the next iteration, and 
    ;; the remainder is the digit that's added into the results.
    (multiple-value-setq (carry digit)
      (floor (+ carry (first digits)) 10))))

(decompose '(10005 2 3))
;=> (5 2 3 0 1)

(decompose '(11 2 4))
;=> (1 3 4)

(decompose '(23 0))
;=> (3 2)

(decompose '(11 11 4 6))
;=> (1 2 5 6)

A modular approach

A more modular approach might break this down into two parts. First, given a list of digits, each of which might be greater than 9, we can reconstruct the original number as a number (i.e., not as a list of digits). This is pretty straightforward:

(defun digits->number (digits)
  (reduce (lambda (digit number)
            (+ digit (* 10 number)))
          digits
          :from-end t))

(digits->number '(1 2 3 4))
;=> 4321

(digits->number '(205 3))
;=> 235

Now, converting a number into a list of digits isn't too hard either.

(defun number->digits (number)
  (do ((digit)
       (digits '() (list* digit digits)))
      ((zerop number) (nreverse digits))
    (multiple-value-setq (number digit)
      (floor number 10))))

(number->digits 1024)
;=> (4 2 0 1)

(number->digits 8923)
;=> (3 2 9 8)

Now, we can observe that digits->number converts the digits list into the number in the form that we need, even when there are 'digits' that are greater than 9. number->digits always produces a representation where all the digits are less than 10. Thus, we can also implement decompose as number->digits of digits->number.

(defun decompose (digits)
  (number->digits (digits->number digits)))

(decompose '(10005 2 3))
;=> (5 2 3 0 1)

(decompose '(11 2 4))
;=> (1 3 4)

(decompose '(23 0))
;=> (3 2)

(decompose '(11 11 4 6))
;=> (1 2 5 6)

As an interesting observation, I think you can say that the space of input for decompose is lists of non-negative integers, and that each list of non-negative integers less than 10 is a fixed point of decompose.