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)
      (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)
      (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)
      (let ((elt (car lst)))
        (if (consp elt)
            (append (apply #'list-of elt) (uncompress (cdr lst)))
            (cons elt (uncompress (cdr lst)))))))


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?

  • 1
    \$\begingroup\$ LET is binding a local variable. In what way would it alter a recursion path? \$\endgroup\$ – Rainer Joswig Jun 27 '19 at 7:34
  • \$\begingroup\$ 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? \$\endgroup\$ – mwal Jun 27 '19 at 8:32
  • 1
    \$\begingroup\$ mwal: it does not matter in this case, there are no side effects and the APPEND function needs to be called anyway. \$\endgroup\$ – Rainer Joswig Jun 27 '19 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.

| improve this answer | |
  • \$\begingroup\$ 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). \$\endgroup\$ – mwal Jun 26 '19 at 17:32
  • \$\begingroup\$ If you are asking for an explanation of how your code works, or how the book's code works, then Code Review is not the place to ask. \$\endgroup\$ – 200_success Jun 26 '19 at 21:10
  • \$\begingroup\$ I'm not sure how let* would factor into this particular function. Let* allows variables to get their value from other variables created in the let statement. The book reviews that. In this situation, rest isn't depending on elt to get it's value in the sense that we would use let* normally. \$\endgroup\$ – Simeon Ikudabo Jul 23 '19 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.