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)))

You may also be interested in Peter Seibel's [Practical Common Lisp](http://www.gigamonkeys.com/book/). — molbdnilo, Oct 05 '15 at 14:06
@molbdnilo I'm using this literature as well, it's a good one too. But didn't find a pdf version there, just the Tex files, which are a bit confusing and I couldn't compile it. If u have an idea how to do it, please let me know. — Giovanni Oliveira, Oct 05 '15 at 20:49
@StanislavKondratyev good catch. A nil check at input woudn't be bad idea, actually it's necessary since my algorithm adds the last item outside the list-loop. Thank you ! — Giovanni Oliveira, Oct 05 '15 at 20:54

score 3 · Accepted Answer · answered Oct 06 '15 at 12:32

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))

it's clear to me which takes nreverse to be faster than reverse, but I'm still a little unaccustomed to Lisp variable scope, I really got to take a deeper reading about this topic. Anyway I'll run some tests with these and another codes I have to the same function and submit them to large amount of data, then I tell u the result. Thank you for contributing. — Giovanni Oliveira, Oct 18 '15 at 19:42

score 3 · Answer 2 · edited May 23 '17 at 12:34

3

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))

edited May 23 '17 at 12:34

Community

1
1

answered Oct 06 '15 at 14:16

coredump

37,664
5
43
77

Your implementation is certainly more concise and elegant. Starting from the end you avoid having to reverse after compressing, which doesn't reduces the time complexity, but saves an O(n) operation, and depending of how reduces is implemented (gotta check it), saves also memory space. This function is really interesting. We could implement integer partition algorithms, for instance, much more easily, what would be a bit painful in C (which also have its virtues). The fact is: the more I know Lisp, the more I like it. Thank you for your rich contribution – Giovanni Oliveira Oct 07 '15 at 04:56
@GiovanniOliveira Thanks. About reduce, there was an interesting article called "Processing List Elements in Reverse Order", by Irène Durand and Robert Strandh – coredump Oct 07 '15 at 06:21
@GiovanniOliveira It might not save an O(n) operation, since the `:from-end` option might be implemented by reversing the list before operating on it in the usual forward direction. – Throw Away Account Oct 10 '15 at 22:03
@coredump this article is really impressive. Besides presenting a really efficient method to process lists in reverse order (which becomes a serious problem when you're handling a big volume of data), it shows a a good point for justify why and when we shoud use recursive functions in some circumstances. Thank you again – Giovanni Oliveira Oct 18 '15 at 19:28
@ThrowawayAccount3Million I think it could be related to which version and dialect of List are you building your code. As soon as I can, I'll take a look at sources and try to make some experimental tests. – Giovanni Oliveira Oct 18 '15 at 19:35

Lisp good practices

2 Answers2