List comprehensions in Common Lisp

List comprehensions are a programming language construct that closely mimics the way you declare a set in mathematics and sometimes are more succinct and readable than using a composition of mapcar, delete-if or an ad hoc imperative loop.

Having list comprehensions in Lisp was something I was missing from Python and Haskell. So I tried to find something similar and discovered that the LOOP facility can be used as a means of achieving this goal but this, although nice, didn’t feel natural enough. In the end, I read the paper Simple and Efficient Compilation of List Comprehension in Common Lisp by Mario Latendresse which appeared at ILC 2007 and have decided to adopt that implementation for translating list comprehensions into loops.

For example, the set

can be expressed as

(lc (cons x y) (<- x '(0 1 2)) (<- y '(0 1 2)) (= (+ x y) 2))  ==>
((0 . 2) (1 . 1) (2 . 0))

Another example:

(lc (sin x) (<- x (range 0 .1 (/ pi 2)))) ==>
(0.0 0.09983342 0.19866933 0.29552022 0.38941833 0.47942555 0.5646425 0.6442177
 0.71735615 0.783327 0.8414711 0.8912074 0.93203914 0.96355826 0.9854498
 0.997495)

The macro I’m using is lc:

(defmacro lc (collection-form &rest quantifiers)
  "Assembles a multiset containing the results of evaluating
COLLECTION-FORM and subject to QUANTIFIERS."
  (labels ((translate (collection-form qs)
             (if (null qs)
                 `(collect ,collection-form)
                 (translate-generator-or-filter collection-form qs)))
           (translate-generator-or-filter (collection-form qs)
             (let ((q (first qs))
                   (qr (rest qs)))
               (if (eq (first q) '<-)
                   (translate-generator collection-form (second q) (third q) qr)
                   (translate-filter collection-form q qr))))
           (translate-generator (collection-form variable collection qs)
             `(nconc (loop for ,variable in ,collection
                          ,@(translate collection-form qs))))
           (translate-filter (collection-form filter-form qs)
             `(when ,filter-form ,@(translate collection-form qs))))
    (when quantifiers
      `(loop repeat 1 ,@(translate collection-form quantifiers)))))

and the helper function range is:

(defun range (a b &optional c)
  "Builds a range of numbers as Matlab would do"
  (flet ((|:| (start step stop)
           (assert (and (<= start stop) (> step 0)))
           (loop for x from start to stop by step collect x)))
    (if c
        (|:| a b c)
        (|:| a 1 b))))

A possible enhancement would be to translate to series instead
of loop in order to have lazy list comprehensions.

This code (and more) can be found in the (incf cl) utilities.