# Uncompressing a list with some run-length-encoded elements

Regarding the following code

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

;; > (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, & 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?

• LET is binding a local variable. In what way would it alter a recursion path? – Rainer Joswig Jun 27 at 7:34
• Perhaps I'm using the term "recursion path" wrongly (if that has a technical meaning I'm not aware of) - I simply meant that I noticed the order of the computation is going to be different. Specifically, in the first example, (uncompress (cdr lst)) will be evaluated before (apply #'list-of elt), whereas in the second, it's the other way around. Unless I've misunderstood? If this observation is correct, is there any significance to that? – mwal Jun 27 at 8:32
• mwal: it does not matter in this case, there are no side effects and the APPEND function needs to be called anyway. – Rainer Joswig Jun 27 at 8:37

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.
• I don't believe this answers the question. I would have liked some discussion involving comparison between let and let*, for example. plus whether or not let is 'syntactic sugar' (whatever that means). – mwal Jun 26 at 17:32