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 \(\left\{ (x, y) \in \{0, 1, 2\}^2 \, | \, x +y = 2 \right\}\) 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.
You’ll find this paper from Guy Lapalme interesting:
http://rali.iro.umontreal.ca/Publications/urls/LapalmeLispComp.pdf
I wrote a list comprehension macro the other day. I don’t use CL, but I was reading up on it, and I thought it would be an interesting exercise. But I gave mine a different form:
(zf (* x y)
(x ‘(1 2 3 4))
(y ‘(1 2 3 4))
if (evenp x)
(oddp y))
I used zf for the name, as list comprehensions are sometimes called Zermelo–Fraenkel expressions, and because zf is really short and stands out. The if marker in the middle breaks the sets from the conditions, avoiding the prefix <- form and makes the whole thing slightly easier on the eyes. (Again, I’m not a Lisper, so I don’t have the Paren-Sight yet ;-)
It’s cool to see someone else doing the same thing.
Relevant ref to another ready-to-go list comprehensions library, probably the default one a long-time lisper will reach for first (it is mentioned in Mario’s paper, but he dismisses it because it looks complex and possibly slow, which is rather missing the point: Sven’s focus was on versatility – “Collect” is extensible to work with any lisp type, which nice. Very nice. i.e. it’s “almost anything comprehensions”, not just “list comprehensions”:
http://user.it.uu.se/~svenolof/Collect/
Example #1 in J
1 line
(I.2= /”1 n){[n=.3 3#:i.*:3
3 lines
cp=. 3 3 #: i. *: 3
ix=. I. 2= /”1 cp
ix { cp
0 2
1 1
2 0
for boxes
<”1 ix { cp
|0 2|1 1|2 0|
You’ve inspired me to write a series based implementation. It’s available from the Mercurial repository.
It seems as though posting the link within a tag doesn’t work. So here’s the URL to the repository:
http://bitbucket.org/roerd/series-comprehension/