Tuesday, July 15, 2008

Lisp: List Comprehensions

Whenever I explain Python's list comprehensions, I always say that they were taken from Haskell. Apparently, Lisp had them too using a syntactic sugar construct called collect. Here's the Python:
[(i, j, i + j)
for i in range(1, n + 1)
for j in range(1, i - 1)
if is_prime(i + j)]
And here's the Lisp:
(list i j (+ i j))
((i (enum-interval 1 n))
(j (enum-interval 1 (-1+ i))))
(prime? (+ i j)))
I found this in SICP, but I'm a little confused about exactly which dialects of Lisp and Scheme it's present in. I doesn't appear to be in R5RS.


raj said...

My memory is that list comprehensions in python were inspired by SETL and not Haskell.

John Landahl said...

That COLLECT function isn't standard to either Scheme or Common Lisp. It must be something developed in an earlier section of SICP (I don't have my copy handy at the moment).

Common Lisp has a LOOP macro as one way of expressing these sorts of things. It's essentially a domain specific language for looping constructs. Your Python list comprehension would look something like this with LOOP (untested):

(loop for i from 1 to (+ n 1)
for j from 1 to (- i 1)
when (prime-p (+ i j))
collect (list i j (+ i j)))

Google "lisp loop" for a few handy tutorials on the LOOP macro.

There's an even better macro for Common Lisp called ITERATE which isn't standard, but is better than LOOP in a number of ways (it's a lot more "lispy" for one thing). The above would look something like this with ITERATE (also untested):

(for i from 1 to (+ n 1))
(for j from 1 to (- i 1))
(if (prime-p (+ i j))
(collect (list i j (+ i j)))))

Fredrik said...

SETL had set comprehensions (a straight-forward implementation of the "set builder" math notation) long before anyone else implemented that.

The 1998 thread that begins with this post by Greg Ewing is the first discussion about list comprehensions in Python land that I could find.

A few posts down, Tim Peters explains that "List comprehensions are a std feature of modern functional languages, to
which you can look for more examples." Terry Reedy later mentions the set builder notation, and Tim follows up with a post about their use in SETL.

Shannon -jj Behrens said...

Great comments. Thanks, guys!