Using reduce twice in a row for Run Length Encoding

Question

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:

1. Convert the string input to a char list (\#a \#a \#b etc.)
2. Use reduce to transform the char list to ((\#a \#a) (\#b) etc.)
3. 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 a) (b)) | curr: c | last-seq: (b) | last-char: b
prev: ((a a) (b) (c)) | curr: c | last-seq: (c) | last-char: c
prev: ((a a) (b) (c c)) | curr: c | last-seq: (c c) | last-char: c
prev: ((a a) (b) (c c c)) | curr: b | last-seq: (c c c) | last-char: c
prev: ((a a) (b) (c c c) (b)) | curr: b | last-seq: (b) | last-char: b
prev: ((a a) (b) (c c c) (b b)) | curr: a | last-seq: (b b) | last-char: b
prev: ((a a) (b) (c c c) (b b) (a)) | curr: b | last-seq: (a) | last-char: a
prev: ((a a) (b) (c c c) (b b) (a) (b)) | curr: a | last-seq: (b) | last-char: b
prev: ((a a) (b) (c c c) (b b) (a) (b) (a)) | curr: a | last-seq: (a) | last-char: a
prev: ((a a) (b) (c c c) (b b) (a) (b) (a a)) | curr: a | last-seq: (a a) | last-char: a
((a a) (b) (c c c) (b b) (a) (b) (a a a))NIL

Answer 1

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

Answer 2

Now that you've got it working, here's some commented code and some more commentary on what to my taste can be improved in your code:

;; Knowing the package manager is important
(ql:quickload :iterate)
;; Some popular packages are best used this way
;; but in general you'd like to stick to using fully
;; qualified names i.e. (package:exported-symbol ...)
(use-package :iterate)

(defun run-length-encode (string)
  ;; Common Lisp has a lot to offer in terms of convenience:
  ;; Macros are definitely one such thing.  Using 
  ;; `with-output-to-string' makes compiling complex string
  ;; easier
  (with-output-to-string (s)
    ;; Again, using macros to reduce the verbosity of the code
    (iter
      (with counter := 0)
      ;; Typically, implementing this with a `loop' or similar
      ;; will create a lot of mess.  This macro helps reduce it.
      (for char :in-string string)
      (for pchar :previous char :initially nil)
      ;; Since the question basically asks to write a simple
      ;; state machine, `cond' is a good candidate for the task.
      ;; It is easily recognized as managing the fixed number of
      ;; states that may happen during iteration.
      (cond
        ((null pchar))
        ((char= char pchar))
        (t (princ pchar s)
           (when (> counter 1) (princ counter s))
           (setf counter 0)))
      (incf counter)
      ;; Idiomatic way to place postamble of the loop.  Again,
      ;; a task that would often create a mess with additional
      ;; variables and conditions around the main subject of the
      ;; function now eliminated.
      (finally (princ pchar s)
               (when (> counter 1)) (princ counter s)))))

How is this different from your code? It doesn't create intermediate lists. It creates a resizable vector (typically, this is how streams are implemented) and fills it as soon as the input is processed.

While this is a toy exercise (this is the 90 Lisp problems, am I right?), in general when working with data streams, algorithms that can work only on the portion of data (i.e. such that don't require that the whole data be read before the next step of the algorithm is performed) have large practical value. Think about reading files, which wouldn't fit in memory, or joining SQL tables etc. So, your concern about two calls to reduce is justified in this sense.

Another thing sds didn't mention: format is a formidable tool :) It can do a lot of interesting things, but using it to simply print a string is definitely an overkill. Perhaps, when you aren't bothered by performance, it seems nicer to have all output managed by the same function, but generally, I'd reserve format for printing heavily formatted output; simple string doesn't justify its use in my view.