List Comprehensions in Eight Lines of Clojure | Hacker News Reader

List Comprehensions in Eight Lines of Clojure

hackerschool.com

109 pointsdavidbalbert41 comments

We don't address this in the post, but adding :while conditions is quite a fun challenge.

This is the best I could come up with (in Emacs Lisp): https://gist.github.com/4356261 . It's rather hacky :D

Darius Bacon (abecedarius) came up with a beautiful alternative formulation that handles :while conditions seamlessly. Here's my port of his idea into Emacs Lisp: https://gist.github.com/4380866

I'd be very happy to see other versions :)

"We don't address this in the post, but adding :while conditions is quite a fun challenge."

Eurgh, I hate the common Clojure habit (you see it in for, doseq, etc. loops, and in domonad, which is annoying in other ways) of abusing binding vectors to add in extra stuff that doesn't, in itself, have anything to do with binding names to values.

If you use a very slightly modified version of the macro defined at [1] (modified to use algo.monads), you can do list comprehensions like this:

     > (monads/with-monad
             monads/sequence-m
             (mdo x <- [1 2 3]
                  y <- [3 4 5]
                  let added = (+ x y)
                  (monads/m-result [x y added])))
     ([1 3 4] [1 4 5] [1 5 6] [2 3 5] [2 4 6] [2 5 7] [3 3 6] [3 4 7] [3 5 8])

The "let added = (+ x y)" is an unnecessary flourish: it would have worked just as well to wrap what followed in (let [added (+ x y)] ...). Likewise (as against domonad), you can just use regular old if; no need for :if.

1: https://bitbucket.org/kenko/macroparser/src/7a492ef941db38db...

abusing binding vectors to add in extra stuff that doesn't, in itself, have anything to do with binding names to values

I'm not familiar with the Clojure examples you mention, but it's interesting that Common Lisp provides directives like &rest for similar purposes.

Sure, and Clojure has '&' in function argument lists for rest arguments.

Here's a Clojure example:

user=> (for [x [0 1 2 3 4 5] :let [y (* x 3)] :when (even? y) z [1 2] [y z]) ([0 1] [0 2] [6 1] [6 2] [12 1] [12 2])

The binding vector for 'for' takes alternating name/value pairs, except it also allows these special keywords whose semantics affect the environment of the subsequent bindings, and whether the bindings are even evaluated, as well as the environment of the body expression (and whether it's evaluated). This strikes me as kind of ugly. The same can be done like this, using that mdo macro:

    > (monads/with-monad monads/sequence-m
                     (mdo x <- [0 1 2 3 4 5]
                          (let [y (* x 3)]
                             (when (even? y)
                              (mdo z <- [1 2]
                                   (monads/m-result y))))))

with identical results, or, as above, like this:

    > (monads/with-monad monads/sequence-m
                         (mdo x <- [0 1 2 3 4 5]
                                   let y = (* x 3)
                                   (when (even? y)
                                    (mdo z <- [1 2]
                                         (monads/m-result [y z])))))

Of course, if you think of a macro like "for" of consisting of a binding vector followed by an expression (or a sequence wrapped in an explicit do), there's no other place for the whens and lets that you want to use to control evaluation of (the environments of) the various bindings than the binding vector itself.

If I'm not mistaken, Common Lisp's loop macro (e.g.) isn't like this---that is, it establishes its own little mini language, instead of mimicking forms found elsewhere in the language (the way Clojure's for loop control constructs are all stuffed into a "binding vector" similar to what might be found in a defn). Now it's true that something like "let y = (* x 3)" is not very Lispy at all. But neither, I think, is having something like ":when (even? y)", a sequence of two elements in a flat vector, actually govern bindings and execution of things that follow it but which it doesn't enclose.

OK, I get you. The inline :WHEN in that FOR form makes me go "what?" as well. The syntax feels halfsie to me; it abandons regularity but doesn't want to go full mini-language a la LOOP, so it ends up in a syntactic no man's land. It doesn't feel very composable to me, either — does it scale to more complex expressions? I'm biased, though. The following seems far better to me; slightly lower-level, but clearer and more composable:

  (loop for x in '(0 1 2 3 4 5) for y = (* x 3) when (evenp y) append
    (loop for z in '(1 2) collect (list y z)))

  => ((0 1) (0 2) (6 1) (6 2) (12 1) (12 2))

The reason why LOOP has keywords for all its loopy things is that the set "stuff you often want to do while iterating" is too varied to be supported by an entirely regular syntax. Of course it can all be done with the utilities of the underlying Lisp (which is all that LOOP expands to), but often not as concisely and especially not as idiomatically. I like crossing out of universal Lisp into Loopland to do those little plumbing jobs. Because LOOP is so limited and specific, I know why such a construct is there and can grok very quickly what I'm looking at and what it evaluates to. Having such forms stand out from the backdrop of the far more powerful language the main program is written in is a major clarity win. (Good god, I sound like someone arguing against Lisp syntax altogether!)

For the same reasons (concision, idiom, and clarity), forgive me but I don't like the monads/with-monad versions you've given. "monads/with-monad monads/sequence-m" is much too verbose — I want an operation this simple to be lightweight. It doesn't feel idiomatic to me for looping and pairing things, though that may just be my ignorance. And it feels like some powerful and general infrastructure is being invoked to do something whose triviality I would rather see the code bring out. Looping is the canonical example, I think, of something that one does so often and has such repetitive-yet-assorted patterns that a little language is perfect for the job. But I'm biased, as I said.

By the way, I've been puzzling over that FOR form trying to make out how it ends up producing a Cartesian product out of '(0 1 2 3 4 5) and '(1 2). In CL, if you make the bindings parallel like that, as in (loop for x in foo for y in bar...), it means "take an x from foo and a y from bar and keep going as long as they're both producing new values". So to get a Cartesian product, I had to make an explicit nested loop in my translation above. Both idioms are useful, but I use the parallel one quite a bit more than the nested one. Does FOR handle both?

p.s. You're missing a square bracket after [1 2]. I was puzzling even more before I realized that :)

"p.s. You're missing a square bracket after [1 2]. I was puzzling even more before I realized that :)"

Whoops!

"Both idioms are useful, but I use the parallel one quite a bit more than the nested one. Does FOR handle both?"

Not directly---to get a parallel product, you would use something like:

    (map vector '(0 1 2 3 4 5) '(1 2))

> Here's a question, though: If your language did not support list comprehensions, what would it take to add them? For a language like Ruby, you may have to dig into the language implementation itself.

No, not really:

http://stackoverflow.com/questions/310426/list-comprehension...

Very cool! I'm not completely sure how it would support comprehensions over more than one list, though (as in the permutations example).

The point of a list comprehension is often that it can work with multiple lists. This can't do that, can it?

That can't, but with https://gist.github.com/605891 you can, using syntax like:

    [(1..6),(4..6),(7..9)].comprehension { |a, b, c| a + b + c if a % 2 == 0 }

And if you go to extremes like https://gist.github.com/3356675 you can use Haskell-like syntax:

    [a + b | a <- ['n','p'..'t'], b <- %w[a i u e o]]

Ruby's blocks and method_missing are very powerful.

Very nice indeed.

NB. Correction to my earlier comment elsewhere here about List::Gen & multiple lists because it does provide cross combinators and also gather/take which is a perl6 way of doing complicated (multi) list comprehensions.

Here are the two examples written in perl6 (which do work in Rakudo).

  gather for 1..6 X 4..6 X 7..9 -> $a, $b, $c { take $a + $b + $c if $a %% 2 }

  gather for ('n', 'p'..'t') X <a i u e o> -> $a, $b { take $a ~ $b }

That second example is awesome! And it demonstrates that I don't know nearly enough about Ruby. :) Thanks for contributing it.

You're welcome!

Just to be clear, I am not the original author. I was impressed with it myself. :)

Ditto for Perl with modules like List::Maker and List::Gen.

However like the Ruby example this only works on a single list. Which reminds me that I keep meaning to write a port of CL loop in Perl using Devel::Declare.

ref: https://metacpan.org/module/List::Maker | https://metacpan.org/module/List::Gen | https://metacpan.org/module/Devel::Declare

Gosh, if you had an extensible reader, you could do so much more... Oh wait, why don't we try it: http://lisp-univ-etc.blogspot.com/2013/01/real-list-comprehe... ;)

Haha, this is really fun :)

I'm looking forward to exploring your blog.

Someone's very happy to have authored Clojure's for special form.

Clojure's `for` is ~80 lines of code, and isn't particularly accessible. My goal here wasn't to reinvent the wheel, but to give an example of a not-totally-trivial macro that does something neat. :)

(Clojure is simply my lisp of choice. This could be just as easily implemented in elisp, which does not have this built in.)

[edit] For those interested, here's an elisp version: https://gist.github.com/4430934

I can appreciate the fun of doing things like implementing a list comprehension and the excitement of both applying macros in a useful way and being able to tell other people about it. I found the tone of the linked article to sound self impressed to a point I personally found distasteful, and after reviewing it again I don't see any mention of Clojure's built in for special form, and thusly reacted in a snarky manner.

But everyone should get an opportunity to see what you can do with things like macros, how useful list comprehensions are in general, and how a homoiconic language can make the simple things slightly less intuitive but the hard things vastly more tractable. I certainly have no business in detracting from your enjoyment of Clojure, so please don't allow me to.

Instead of being snarky may I offer some constructive criticism:

1) You don't mention the Clojure `for` special form, which is a built in list comprehension. 2) There's a significant amount baked into Clojure's `for` special form. How does it compare to your macro? After reviewing the macro again I think you'll find there's some differing behaviors over when members of seqs are realized and bound between your implementation and that in clojure.core. 3) I think reflecting on what the real power here is: that you are able to dictate the hows and whys of evaluation at what time, and discussing that matter, can make more salient the power of LISPs.

Please do continue to enjoy what you are building and what you learn, and don't let the jaded musings of crotchety old men like me get in your way!

I enjoyed the article but was also a little bummed `for` wasn't mentioned at all.

Minor nit: `for` is a macro in the clojure.core namespace, not a special form. Special forms in Clojure are these: http://clojure.org/special_forms

I really appreciate the thoughtful response and constructive criticism! I think that much of it is valid.

All of this actually fell out of a desire to better understand Clojure's `for`, which is a piece of code I would have run away from not too long ago. (Earlier versions of this post made significant mention of `for` and its implementation; that it was totally stricken from the final version was, I think, an unfortunate product of editing.)

I'll certainly think more on your second and third points.

It's a nice post/example. Obviously useful, not that trivial, or at least something you might not have thought of doing if you're just beginning to grok macros, but simple enough so that you can do a pretty detailed explanation of it without going on forever.

Mentioning that there is a `for` form might be nice, just so it's clear that you don't have to do (something like) this in order to do list comprehension in Clojure. Kind of disagree with aredington's 2nd and 3rd points though. Those might be fine things to write some stuff about, but I don't know that that post really needs them.

Like, I don't think every post on macro stuff must deal with "macros and evaluation". It's an interesting topic and all, but as it is I like that the post is more like, here's a macro and look how we can use it to turn code like this into code like that. Without getting into every topic that that touches on.

How does he at all sound self-impressed? I just read the article twice and still don't understand this comment.

Your blog post should probably at least mention clojure.core/for, so that new Clojurists can use that in real projects, after they are done learning.

Yes, exactly. I am confused. Why use Clojure for the example, when Clojure already has this built in? I don't know all of the Lisp's, but if one of them does not have this, it would make sense to offer the example in that language.

Having said that, there is probably some educational value in writing out what a special form would look like if it was not a special form, so in that regard, yes, this is interesting to look at.

Because he is just showing an example of macros, not giving a tutorial on how to add list comprehensions to Clojure.

`for` is a macro, not a special form. Special forms are these: http://clojure.org/special_forms

Without monads?)

I nice and somewhat related paper is "Simple and Efficient Compilation of List Comprehension in Common Lisp" by Mario Latendresse:

http://www.iro.umontreal.ca/~latendre/publications/listCompF...

Given that clojure is a dialect of lisp (the list processing language), it seems that list comprehensions should not be a remarkable achievement. Am i missing something?

yes and no. Yes, because the example is a novel language feature in other languages that would be very difficult to implement. No, because these sorts of things are easy only when code is data, like lists, which is a design property of lisps, but not really captured within 'list processing'. I think perhaps there could exist a language that says it's good at lists and data without the macro system that makes this possible.

This is very telling example of how differently Java people think.

First of all - ''this'' is NOT list comprehensions. Lisp has list comprehension, the sub-set of features that makes macros possible. Quote, back-quote, comma and grouping with parenthesis are parts of Lisp syntax to do it.

This is a meaningless generalization from a lisp programmer's perspective, just another macro.

Look at it carefully. This is the how confusion looks like. Thinking in terms of classes and methods prompts them to create artificial, unnecessary complications.

This is not hacking, this is exactly opposite.)

> This is very telling example of how differently Java people think.

Notice how the blog didn't even mention Java once and is talking about Clojure and defmacro, still you managed to imagine the article, an argument and respond to it. What more, your response is on the lines of "The earth goes around the sun" -> "Hah. No".

> First of all - ''this'' is NOT list comprehensions

This is list comprehension as in the accepted definition of list comprehension.

> Lisp has list comprehension, the sub-set of features that makes macros possible. Quote, back-quote, comma and grouping with parenthesis are parts of Lisp syntax to do it.

List comprehension doesn't mean whatever you want it to mean.

http://en.wikipedia.org/wiki/List_comprehension#Common_Lisp

> Look at it carefully. This is the how confusion looks like.

Look at this comment carefully. If you ever wondered how empty vessels make most noise, this is how it looks like. Without pointing out anything in the article which is wrong or can be improved, or without even giving out unrelated examples(that would have been something), this comment has shit all over it over some delusional sense of lisp programmers superior to Java programmers. It might have been a bit acceptable if the comment would have posted a clever lisp solution, or the blog would have had anything to do with Java at all.

> Thinking in terms of classes and methods prompts them to create artificial, unnecessary complications.

And again, imagine arguments and respond to them. Where on earth TFA mentioned classes and methods?

Also, this fucking hippy culture of "classes suck; functional programming rockz; lolz" need to die. What makes it more irritating is 99.999% of the times, the person singing the praises of lisp, functional programming et al. and trashing Java(there is a very high correlation) is a fucking moron and can't code to save his life, in lisp or any other language. Do a 100,000 lines project in Haskell, come back and then tell me how classes suck and this functional programming project of yours is so much better. Even then, that will be just personal anecdote, but currently, it's just incoherent, incompetent rambling.

  (define a 1)

  `(1 ,a)   ; this construction satisfies the definition of list comprehension

Everything else follows.

Next time try to add pointers to Assembly language.

> `(1 ,a) ; this construction satisfies the definition of list comprehension

How dense you have to be to conveniently ignore everything, imagine arguments, imagine counter arguments, post it, and keep repeating it?

How on earth (define a 1) and `(1, a) related? Do you understand scheme and what list comprehensions are? Or do you just dump "lisp, lisp, lisp, na da ...not listening...lisp, lisp" in response to everything?

there are a ways to create a list:

  '(1 2 3)

  ((lambda x x) 1 2 3)

  (defun list1 (&rest args) args)

This works because lisp expressions are lists, and the reader function uses list as an underling representation of lisp expressions.

   `(1 ,a)

This is a syntactic sugar to make construction of lists at read-time easily to express.

Read-time construction of lists is a feature of the language which gives us macros. Not the other way around.

Defining a macro for implementing a limited functionality a language can do, which consists of just a cond is a sign of inability to grasp what features are available and how to use them in appropriate way.

We don't need some macro for doing list comprehension, we have list comprehension to write macros.

This construct list-comp - is just ugly, because it is artificial and meaningless.

The habit of piling up crap without understanding, along with over-verbosity are a signs of a typical Java dev.

btw, using such kind of language against a Russian is a shortest way to a ProblemFactory)

> Defining a macro for implementing a limited functionality a language can do, which consists of just a cond is a sign of inability to grasp what features are available and how to use them in appropriate way.

Work on your reading comprehension, and comprehension in general. Every fucking language has fucktard ways of contructing lists. Constructing lists and list comprehensions aren't the same thing(I am a bit weirded out that I have to point it, but with someone as dense as you, there aren't any other options).

> btw, using such kind of language against a Russian is a shortest way to a ProblemFactory)

Everytime I think online forums have hit the rock bottom, and can't go any lower, some fucktard comes along and proves me wrong. Why don't you go fuck off somewhere where people might be impressed with your imaginary tales of bad-assery? Or find other morons on youtube or something and make shit up about how badass you are, instead of wasting my time here.

EDIT: Please tell me this russian bit is your idea of humor. The alternative is depressing.

Would you guys please stop this?

It surely is. Do google "culture of honor".

I don't think you understand what was claimed in the article. 'List comprehension' is the name of a specific syntactic construct. List comprehensions describe straightforward transformations of other lists in convenient notation. http://en.wikipedia.org/wiki/List_comprehension

They're syntactic sugar for map and filter. Consider this python code:

    [x**2 for x in range(100) if x % 2 == 1]

This is a list comprehension. It's equivalent (in 2.x) to the Python

    map(lambda x: x**2, filter(lambda x: x%2 == 1, range(100)))

(or in Clojure,

    (map #(* % %) (filter #(= 1 (mod % 2)) (range 100)))

(seems like cheating to use the odd? function))

...so, equivalent to map and filter, just with better syntax.

Caveat: in 3.x, python's map and filter return generators, so the equivalent comprehension would be a generator comprehension instead--just the same thing as above but wrapped in parens and not square brackets--which would also return a generator.

You forget monads. Much brighter people already done this in comments above.)

Reply on news.ycombinator.com