List Comprehension

About List Comprehension

Please refer to wikipedia for the definition and usage of List Comprehension. http://en.wikipedia.org/wiki/List_comprehension

Example

The following is a typical example of the usage of list comprehension:

(setf l '(1 2 3 4 5 6 7 8 9 10))

(collect-list (list x y)
  (for x in l)
  (evenp x)
  (for y in l)
  (oddp y))

=>

((2 1) (2 3) (2 5) (2 7) (2 9) (4 1) (4 3) (4 5) (4 7) (4 9) (6 1) (6 3) (6 5)
(6 7) (6 9) (8 1) (8 3) (8 5) (8 7) (8 9) (10 1) (10 3) (10 5) (10 7) (10 9))

Implementation

The macro collect-list can be constructed using with-collect macro and LOOP (or iterate) macro. Thus it can collect data in the data types which are supported by LOOP and Iterate. In fact, using with-collect and loop makes the implementation quite easy and straightforward.

Here's the implementation of collect-list (based on Loop):

(defmacro collect-list (element &body qualifiers)
  (labels ((build-form (qualifiers body)
             (if (not qualifiers)
                 body
                 (let ((first-form (first qualifiers))
                       (rest-form (rest qualifiers)))
                   (cond ((string-equal (symbol-name (first first-form))
                                        "FOR")
                          (build-for-clause first-form
                                            (build-form rest-form body)))
                         (t
                          `(when ,first-form
                             ,(build-form rest-form body)))))))
           (build-for-clause (form body)
             `(loop ,@form
                 do ,body)))
    (let ((collector (gensym "COLLECTOR")))
      `(with-collect (,collector)
         ,(build-form qualifiers
                      `(,collector ,element))))))

And the example will be expanded into:

(WITH-COLLECT (#:COLLECTOR1702)
  (LOOP FOR X IN TEST DO
	   (WHEN (EVENP X)
		 (LOOP FOR Y IN TEST DO
			  (WHEN (ODDP Y) (#:COLLECTOR1702 (LIST X Y)))))))

Which is also very efficient.

The with-collect macro can be found in CLOCC/CLLIB/simple.lisp

Other Examples 

(defun permutation (list)
  (if (null list)
      '(())
      (collect-list (cons x ys)
        (for x in list)
        (for ys in (permutation (remove x list))))))

Other Implementations

For another take on comprehensions see List comprehensions for Lisp, a LGPL'd general collect macro.

An afterthought

It’ll be handy to use Iterate instead of Loop, in order to take advantage of its flexibility and expressiveness. But some forms like (for y previous x) are something you definitely don’t want to nest. One way to identify that is to construct it as ((for x …) (for y …)).