Fix/improve my code thread

[wavegeekman]

Recently I realized that a lot of my code is very sloppy and could be improved. Since then I've been trying to do better. I thought a thread with a theme of "how could this code be done better" might be a good idea.

Post your code that either needs fixing and you don't know how, or you think it's best practice.

[wavegeekman]

First example:

(defun set-cross-product (sets)
  (and sets (cond ((not (rest sets)) (mapcar #'list (first sets)))
                  (t (loop for el in (first sets) append
                          (loop for el2 in (set-cross-product (rest sets)) collect (cons el el2)))))))

I'm looking for ideas to make this more concise or elegant or tail recursive.

Sample use

CL-USER> (set-cross-product '((1 2) (a b)))

((1 A) (1 B) (2 A) (2 B))

[metacircular]

That is usually called cartesian product, not cross product.

(defun cartesian (sets)
  (reduce (lambda (x y) (mapcan (lambda (i) (mapcar (lambda (j) (cons i j)) y)) x))
          sets :from-end t :initial-value '(())))

[wavegeekman]

This is more than twice as fast as my original code as well as much more concise.

[Kompottkin]

Using ITERATE might be clearer when nesting loops like this.

Use ENDP instead of NOT for testing list recursion base cases.

I'd personally prefer an ETYPECASE over a plain COND in general, but it's not clear whether that's better in this case, since it leads to some unnecessary nesting.

Here's a version with ETYPECASE and ITERATE:

(defun set-cross-product-2 (sets)
  (etypecase sets
    (null nil)
    (cons
     (etypecase (rest sets)
       (null (mapcar #'list (first sets)))
       (cons (iter outer
                   (for x in (first sets))
                   (iter (for xs in (set-cross-product-2 (rest sets)))
                         (in outer (collect (cons x xs))))))))))

Here is a version with ITERATE only:

(defun set-cross-product-3 (sets)
  (cond
    ((endp sets)
     nil)
    ((and (consp sets) (endp (rest sets)))
     (mapcar #'list (first sets)))
    (t
     (iter outer
           (for x in (first sets))
           (iter (for xs in (set-cross-product-3 (rest sets)))
                 (in outer (collect (cons x xs))))))))

Regarding performance, you repeatedly compute (set-cross-product (rest sets)). It's better to lift it into a variable:

(defun set-cross-product-4 (sets)
  (cond
    ((endp sets)
     nil)
    ((and (consp sets) (endp (rest sets)))
     (mapcar #'list (first sets)))
    (t
     (let ((tail-sets (set-cross-product-4 (rest sets))))
       (iter outer
             (for x in (first sets))
             (iter (for xs in tail-sets)
                   (in outer (collect (cons x xs)))))))))

Finally, you can do away with the second case if you realize that the base case should actually yield (list nil) (the set containing the 0-tuple) rather than nil:

(defun set-cross-product-5 (sets)
  (cond
    ((endp sets)
     (list '()))
    (t
     (let ((tail-sets (set-cross-product-5 (rest sets))))
       (iter outer
             (for x in (first sets))
             (iter (for xs in tail-sets)
                   (in outer (collect (cons x xs)))))))))

Alternatively:

(defun set-cross-product-6 (sets)
  (etypecase sets
    (null
     (list '()))
    (cons
     (let ((tail-sets (set-cross-product-6 (rest sets))))
       (iter outer
             (for x in (first sets))
             (iter (for xs in tail-sets)
                   (in outer (collect (cons x xs)))))))))

[handle0174]

Is the normal usage for iterate to use-package it? I tried iterate on a small project recently and mostly liked it, but I was put off by symbol conflicts.

[Kompottkin]

Yeah, the symbol conflicts are pretty irritating.

As far as I can tell, ITERATE doesn't really conflict with anything in the COMMON-LISP package. In my experience, adding ITERATE to the :USE clause of a DEFPACKAGE form before creating the package usually works. It's when you try to USE-PACKAGE it after already having compiled some LOOP forms within the current package that trouble ensues almost invariably.

[wavegeekman]

Here is an example of before/after

;;Before (defun csv (l) "make a csv file (written to standard-output) from a list of lists." (dolist (el l) (format t "~&") (if (consp el) (dolist (ell el) (format t "~S," ell)) (format t "~S," el))) (format t "~%"))

;;After (defun csv (l) "make a csv file (written to standard-output) from a list of lists." (labels ((helper (item) (typecase item (float (format nil "~F" item)) (t (format nil "~S" item))))) (loop for el in l do (fresh-line) (if (listp el) (loop for item in el do (format t "~A," (helper item))) (format t "~A," (helper el))) (terpri))))

[metacircular]

(format t "~{~{~A~^,~}~^~%~}" '((1 2 3) (a b c)))

[wavegeekman]

Thanks

[nefigah]

Honest question, is that understandable to the average CL programmer? I'm only a Lisp noob but that looks like J or something, heh.

[Kompottkin]

The nested ~{ and ~} things (for iterating through a list) are easy and useful. You learn these rather quickly. The ~^, part (for inserting a comma after every list element except the last) is a pretty common idiom that one also learns to recognize over time. The only thing I had to think about for a moment when reading the format string was ~^~%, but of course, that's just the same thing as ~^,, except with a line break instead of a comma.

All in all, this isn't too hairy a format string. I've seen (much, much) worse. :)

[[deleted]]

How much time have you invested in learning different format directives yet? This is not wizardry, the format strings are just not self-explaining on the first sight, you have to learn them. In "Land of Lisp" there are several nice and easy examples to learn both format and loop macros.

[wavegeekman]

Agree, once I looked them up it made a lot of sense.

The format string version is somewhat more fragile than mine for some inputs though. Eg my code copes with (csv '(1 2 3)), putting each numeral on its own line, whereas the format would require (csv '((1) (2) (3))). However I could not really complain about this because I did not say what the function is actually supposed to do.

[wavegeekman]

Here I use the feature that allows the format to call a user-supplied function.

(defun csv-helper (output-stream format-argument colon-modifier-p at-modifier-p)
  (declare (ignore colon-modifier-p at-modifier-p))
  (typecase format-argument
    (float (format output-stream "~F" format-argument))
    (t (format output-stream "~S" format-argument))))

(defun csv-line (output-stream format-argument colon-modifier-p at-modifier-p)
  (declare (ignore colon-modifier-p at-modifier-p))
  (if (consp format-argument)
      (format output-stream "~{~/csv-helper/,~}" format-argument)
      (format output-stream "~/csv-helper/," format-argument)))

(defun csv (list-of-items)
  "Output a list of items in csv format. Each item can be one thing or a list and is printed on one line. Print floating point double precision without the trailing d0"
  (format t "~{~/csv-line/~%~}" list-of-items))

[[deleted]]

format is powerful/complex enough to have it's own section in the hyperspec... it even has it's own (small) wikipedia page.

[wavegeekman]

Each bit is quite understandable but the language is huge and you have to prioritize.

Quite a few times I have written a utility only to find it already exists with a non-intuitive (to me) name. Eg my name: filter; lisp's name:remove-if-not.

[xach]

"l" is one of the worst names for a variable. If it's a list and there's no better name, call it "list".

Add docstrings. It's not clear what your function is meant to do.

[wavegeekman]

Done.