Using reduce twice in a row for Run Length Encoding

First of all, I'm new to Lisp (I currently use CLISP and SBCL). There probably are huge mistakes in this code so any guidelines are welcome :)

I'm very confused about how to do this. It's just about a habit and I don't want my actual help to implement an algorithm, as the one I came up with is not the best one.

Is it okay to use reduce twice in a row on the same list? (it is not exactly the same list as it has been reduced, but I hope you get my point)

Here the algorithm is pretty much the same as the run-length encoding the only differences I see are:

• when a letter occurs only once, it has no number indication

• the number of occurrences of a letters is put on the right instead of the left

For example:

input: aabcbaaabbbcc

output: a2bcba3b3c2

The steps I have chosen to do are these:

• Convert the string input to a char list (\#a \#a \#b etc.)

• Use reduce to transform the char list to ((\#a \#a) (\#b) etc.)

• Transform the new list to a string using reduce again (this is where I'm wondering if the previous step should not be a reduce but a map)

I have implemented the 2 first steps of this algorithm here:

(defun compress-reduce (prev curr)
  ;prev is always a 2d list -> ex: ((a) (b))
  ;curr is always a char
  (format t "prev: ~A | curr: ~A | " prev curr)
  (let ((last-seq (nth 0 (last prev)))
        (last-char (nth 0 (nth 0 (last prev)))))

    (format t "last-seq: ~A | last-char: ~A~%" last-seq last-char)

    (if
      (= (char-int last-char) (char-int curr))
      (and (push curr last-seq)
           (setf (nth (- (length prev) 1) prev) last-seq) prev)
      (append prev (list (list curr))))))

(defun compress ()
  (let ((l (coerce "abcccbbabaaa" 'list) ))

    ; reduce
    (format t "~A" (reduce #'compress-reduce l :initial-value (list (list (nth 0 l)))))))

(format t "~A" (compress))

This always outputs:

```
prev: ((a)) | curr: a | last-seq: (a) | last-char: a
prev: ((a a)) | curr: b | last-seq: (a a) | last-char: a
prev: ((a

Algorithm

Your algorith is quadratic for no good reason because last and length
are linear in list length.

I suggest that you add new elements to the beginning instead of the
end of the return value in compress-reduce and
nreverse
it in compress.

Style

Avoid nth 0 in favor of car.

(= (char-int last-char) (char-int curr)) is better written as (char= last-char curr).

Avoid mixing and and push: keep conditions in and and side-effects
(like push) in progn.

Repeated reduce and map

Each map
(and mapcar et al)
allocates a fresh list, so doing a repeated map can waste memory (and
garbage collection cycles), so either using
map-into
or an explicit function composition is a good idea: instead of

(mapcar #'foo (mapcar #'bar my-list))

use either

(let ((res (mapcar #'bar my-list)))
  (map-into res #'foo res))

or

(mapcar (lambda (x) (foo (bar x))) my-list)

However, no such allocation happens with reduce
so there is no reason to avoid nested reduces.

Note that the proverbial "sufficiently smart compiler" should be able to
handle these problems (but not necessarily the quadraticity above!), so
you should only worry about this if you discover it to be the
performance bottleneck.

Remember (SICP):


... a computer language is not just a way of getting a computer to
perform operations, but rather ... it is a novel formal medium for
expressing ideas about methodology

StackExchange Code Review Q#75579, answer score: 2