Uncompressing a list with some run-length-encoded elements Regarding the following code


;; ANSI CL - p37
;; Run length encoding: expansion

;; &gt; (uncompress '((3 1) 0 1 (4 0) 1))
;; (1 1 1 0 1 0 0 0 0 1)
(defun uncompress (lst)
  (if (null lst)
      nil
      (let ((elt (car lst))                     ; [1]
            (rest (uncompress (cdr lst))))      ; [2]
        (if (consp elt)
            (append (apply #'list-of elt) rest) ; [3]
            (cons elt rest)))))                 ; [4]

(defun list-of (n elt)
  (if (zerop n)
      nil
      (cons elt (list-of (- n 1) elt))))

;; [1] the compressed form, whether atom or list.
;; [2] uncompress the rest. recursion happens here. curious.
;; [3] compressed form, so expand it, &amp; append to uncompressed rest.
;; [4] not a compressed form, so just cons it.



Left to my own devices, I would have written uncompress like so

;; How my intuition would have said to write it, with the recursive
;; calls made where their results are used:
(defun uncompress (lst)
  (if (null lst)
      nil
      (let ((elt (car lst)))
        (if (consp elt)
            (append (apply #'list-of elt) (uncompress (cdr lst)))
            (cons elt (uncompress (cdr lst)))))))


Question

Computing the value of rest in the let in the first example appears to alter the path of the recursion.  Is that correct? Or are let forms merely substituted into later code where they are used?
There is a slight difference in the order of evaluation, in that the book's solution recurses before calling consp, whereas your solution recurses after calling consp. Either way, the recursion happens before concatenation, because the innermost expressions in (append (apply #'list-of elt) (uncompress (cdr lst))) and (cons elt (uncompress (cdr lst))))))) have to be evaluated first.

I think that your solution is a bit worse than the book's, in that the common expression (uncompress (cdr lst)) is written twice.