Lisp good practices

Question

I've started studying Lisp 2 days ago and I'm reading Paul Graham's ANSI Common List, which exposes the language structure in a very interesting way. It's not too much theoretical for beginners, and not too shallow (as Sierra-Bate's Head First Java, which personally I hate). After a brief general language introduction, he starts talking bout lists and raise an example of simple list compression. Basically, let el be an element which is repeated n times. You replace all of them by a single (n el) list. To do this he gave an code implementation, but I tried to do my own, which apparently is working. I'd like if possible, that someone analyses my code and show me the critical points of its implementation, which I'm sure there is a lot, since it's my first contact with Lisp. Thank u all!

(defun compress (x)
"compress a list replacing repeated sequential values for (<n> <value>)"
(let ((lst '()) (fst t) (lt nil) (n 0)) 
    (dolist (el x)
        (if fst
            (progn
                (setq fst nil)
                (setq lt el)
                (setq n 1))
            (progn 
                (if (equal el lt)
                    (setq n (+ n 1))
                    (progn
                        (setq lst (cons (if (= n 1)
                                    lt
                                    (list n lt)) 
                                lst))
                        (setq lt el)
                        (setq n 1)
                    )))))
    (setq lst (cons (if (and (not (= n 0)) (= n 1))
                        lt
                        (list n lt)) 
            lst))
(reverse lst)))

Answer 1

The algorithm seems quite reasonable. I only find the fst variable superfluous. You use it only when entering the loop, so you could just as well move the first bunch of assignments to the preamble and iterate over the rest elements of the list.

Now the question is how to express the algorithm in Lisp.

The most significant point is that you can use nreverse instead of reverse. nreverse is more efficient, but it destroys the structure of its argument. Generally, you don't want that because of so-called shared structure: a cons cell can be a part of a few lists, so modifying a cons sell you can bring about unexpected changes in apparently unrelated lists. (PCL treats this issue very well.) However, in your function you construct lst from scratch, manually pushing new elements onto it, so there is no way it could share structure with other lists. So you can safely dispense with the structure. This is the common push/nreverse idiom. reverse just conses up a new list, and lst becomes garbage.

To make the code more idiomatic, you could use standard shortcuts like incf for += and push for cons=. Nowadays the universal setf seems to be more popular then setq. Personally, I prefer using cond where a progn would otherwise appear. So you could end up with something like this:

(defun compress (x)
  "compress a list replacing repeated sequential values for (<n> <value>)"
  (if x
      (let ((lst '())
            (lt (first x))
            (n 1)) 
        (dolist (el (rest x))
          (cond ((equal el lt) (incf n))
                (t (push (if (= n 1)
                             lt
                             (list n lt))
                         lst)
                   (setf lt el)
                   (setf n 1))))
        (push (if (= n 1)
                  lt
                  (list n lt))
              lst)
        (nreverse lst))
      nil))

Answer 2

In addition to Stanislav's answer I would like to show another possible implementation. The compression algorithm is a perfect use-case for REDUCE, also known as fold. The reducing function takes the result so far, a new element, and combines them to produce the next result. The result you want is a list of couples. The initial element is the empty list.

(defun compress (sequence)
  (reduce (lambda (number list &aux (head (first list)))
            (if (eql number (first head))
                (prog1 list
                  (incf (second head)))
                (cons (list number 1) list)))
          sequence
          :from-end t
          :initial-value nil))

Reduction is applied from the end, so that you can easily cons a new couple on top of the current result while keeping the existing order of elements. If your input is '(a b b c), then the anonymous reducing function will be called as follows:

number  list           new list
---------------------------------------------
c       nil            ((c 1))
b       ((c 1))        ((b 1)(c 1))
b       ((b 1)(c 1))   ((b 2)(c 1))
a       ((b 2)(c 1))   ((a 1)(b 2)(c 1))

REDUCE being defined for sequences, the compression function is generic:

;; string
(compress "aaddzadzaaaddb")
=> ((#\a 2) (#\d 2) (#\z 1) (#\a 1) (#\d 1) (#\z 1) (#\a 3) (#\d 2) (#\b 1))

;; vector
(compress #(1 2 3 3 3 3 4 4 4 55 5 5 5 5 5 5 ))
=> ((1 1) (2 1) (3 4) (4 3) (55 1) (5 6))

;; list
(compress '(1 2 3 3 3 3 4 4 4 55 5 5 5 5 5 5 ))
=> ((1 1) (2 1) (3 4) (4 3) (55 1) (5 6))