2013-01-02

"Real" List Comprehensions in 24 Lines of Lisp

I've just come across a post on Hackernews titled List Comprehensions in Eight Lines of Clojure. It's definitely a nice little example. But it also feels kind of unreal, even cheating ;) Because who would really use such kinds of list comprehensions? It seems to me, that the whole purpose of this construct is to make the code be concise and resemble a set-theoretic notation for sets. But here we need to use them inside a list-comp macro. This actually looks more like just another iteration construct.

What you really want from a list comprehension syntax is for it to be able to "comprehend" something like this:

{x|x ∊ some set}
or like this:
{x|x ∊ some set|x < 10}
Just like math.

But, surely, it's impossible to implement such syntax in Clojure or any other language without an extensible reader. The only route you can go is what Python does — to implement it as part of the language itself.

But you can do more, if you have control of the reader. This is one of the many cases, when Lisp's reader macros prove indispensable.

So here's an implementation of "real" (i.e. really resembling mathematical notation, no cheating) list comprehensions in 24 lines of Lisp (if you don't count a utility function group):

Unfortunetely, I had to use || instead of |, because on its own the | is used to escape charfactes in symbols, and also <- instead of for ease of typing, obviously. And as for the filter part, there's an implicit and, so you can write several conditions, and they should all hold. Otherwise, I think, this can be considered a literal implementation of the idea.

PS. And using named-readtables instead of plain set-macro-character this syntax can be used on a per-file basis, just like in-package forms.

PPS. I won't discuss here the issues of list vs. sets or lists vs. sequences. They are an implementation detail, worth another post.

submit

No comments: