Run length encoding in Lisp is kind of a trivial problem. Not one that would typically come up in most applications. I came across a treatment while reading the third chapter of ANSI Common Lisp by Paul Graham. I’ve read The Little Schemer and a friend just handed me a copy of ANSI Common Lisp. My style has been greatly influenced by The Little Schemer so when I encountered Paul Graham’s example, my nose crinkled a little and I wondered if I could write a more concise solution. I thought it would be a simple kata.
The “problem” goes like this. You have a list like:
(1 1 1 0 1 0 0 0)And you want a more concise representation. Paul Graham suggests:
((3 1) 0 1 (3 0))For example. Here’s Paul Graham’s solution. I hope I understand fair-use correctly:
(defun ansi-compress (lst)
(if (consp lst)
(compr (car lst) 1 (cdr lst))
lst))
(defun compr (elt n lst)
(if (null lst)
(list (n-elts elt n))
(let ((next (car lst)))
(if (eql next elt)
(compr elt (1+ n) (cdr lst))
(cons (n-elts elt n)
(compr next 1 (cdr lst)))))))
(defun n-elts (elt n)
(if (> n 1)
(list n elt)
elt)) And here is my attempt at a more “Little Schemer” style solution:
(defun compress-b (p c lat)
(cond ((null lat) (cons (cons c p) '()))
((equal (first lat) p)
(compress-b (first lat) (1+ c) (rest lat)))
(t (cons (cons c p) (compress-b (first lat) 1 (rest lat))))))
(defun compress (lat)
(cond ((null lat) '())
(t (compress-b (car lat) 1 (cdr lat)))))As you can see, it’s a few lines shorter. It’s also in many ways, functionally identical. However, my return data structure is a little different. Even if there is a single element, I return a cons. With a little extra code I could probably return an identical data structure. But it will require some way of emulating “n-elts.” However I think I like the uniformity, even if it trades off a tiny, tiny but of space. My function will always return a list of cons cells unless the input list is empty (in which case it will return an empty list).
Of course I’m still learning. I did a trace of the “compress-b” and “compr” functions to test my assumptions. When I first expanded the calls to “compress-b” I was slightly alarmed by the number of returns on the tail end of the function. However, I see that Paul Graham’s solution is the same. The question I have left is whether this is normal and desirable behavior. It seems to me that a single return of the final “chunk” would be better. If there are any Lisp experts in the crowd, would you care to enlighten me?