List comprehensions

[zork...@hotmail.com]

I like list comprehensions, so I decided to improve the list
comprehensions in Clojure. In Haskell, where they originate, they look
like this [ expression, qualifiers ]. Where a qualifier is either a
generator "var <- list expression" or a filter, which is a boolean
expression. In Haskel 98 it can also be a let expression. Clojure
allows only one filter.

My implementation is based on the paper "Implementation of a "Lisp
comprehension" macro" http://rali.iro.umontreal.ca/Publications/urls/LapalmeLispComp.pdf
.

(defmacro for
[qualifiers expr]
(let [for6 (fn for6
[qualifiers expr list2]
(if (nil? qualifiers)
`(lazy-cons ~expr ~list2) ; rule C
(let [q1 (first qualifiers)
q2 (second qualifiers)
qualifiers (rrest qualifiers)]
(if (= q1 :when)
`(if ~q2 ; rule B ; filter
~(for6 qualifiers expr list2)
~list2)
(let [variable q1 ; rule A
list1 q2
h (gensym "H-")
us (gensym "US-")
us1 (gensym "US1-")]
`(let [~h (fn ~h [~us]
(if (nil? ~us) ~list2
(let [~variable (first ~us)
~us1 (rest ~us)]
~(for6 qualifiers expr
`(~h ~us1)))))]
(~h ~list1)))))))]
(for6 qualifiers expr nil)))

Example: (for [x (range 1 10) :when (odd? x) y (range 1 10) :when
(even? y)] [x,y])

LCs now look like this (for [qualifier ...] expression]) where
qualifier is either a generator "var seq-expression" or a filter
":when filter-expression". BTW this is the same syntax that PLT-Scheme
4.0 will be using. Rich's syntax was very similar coincidentally. I
hope this gets included in the main distribution.

This implementation produces a stream. There's also a paper "Simple
and Efficient Compilation of List Comprehension in Common Lisp"
http://www.iro.umontreal.ca/~latendre/publications/listCompFinal.pdf
which describes eager comprehensions.

[Rich Hickey]

On Mar 28, 2:30 pm, "zorkz...@hotmail.com" <zorkz...@hotmail.com>
wrote:

> I like list comprehensions, so I decided to improve the list
> comprehensions in Clojure. In Haskell, where they originate, they look
> like this [ expression, qualifiers ]. Where a qualifier is either a
> generator "var <- list expression" or a filter, which is a boolean
> expression. In Haskel 98 it can also be a let expression. Clojure
> allows only one filter.
>
> My implementation is based on the paper "Implementation of a "Lisp
> comprehension" macro"http://rali.iro.umontreal.ca/Publications/urls/LapalmeLispComp.pdf
> .

I'd read that paper, as you might see from the similarity in the
expansions. But there are some tricks to the laziness aspect, both in
stack usage and eagerness of touching args. This makes mine a bit
gnarlier, but:

(time (doall (take 100 (for [x (range 100000000) y (range 1000000)] (<
y x) [x y]))))
"Elapsed time: 14355.767 msecs"
-> ([1 0] [2 0] [2 1] [3 0] [3 1] ...

(time (doall (take 100 (for2 [x (range 100000000) y (range
1000000) :when (< y x)] [x y]))))
-> java.lang.StackOverflowError

That's why mine uses lazy-cat and recur.

I'm not averse to supporting multiple filters, but you'll either have
to do it my way or figure out how to be lazy in argument consumption,
and non-stack-consuming.

Rich

[zork...@hotmail.com]

I don't know how to add lazy comprehensions when the language doesn't
support tail call optimizations. But your comprehensions aren't proper
LC. Consider this:

(time (first (doall (for5 [x (range 1 1000) :when (< x 2) y (range 1
1000)] [x,y]))))
(time (first (doall (for [x (range 1 1000) y (range 1 1000)] (< x 2)
[x,y]))))

The first proper LC runs much faster because the second is doing a lot
of unnecessary work. The first generates 1000 values, while the second
generates all 1000x1000 values.

So I think eager LC are the only way to go, unless someone figures out
how to implement proper lazy LC.

[Rich Hickey]

On Mar 30, 6:06 am, "zorkz...@hotmail.com" <zorkz...@hotmail.com>
wrote:

I'd appreciate it if you'd tone down the 'proper' rhetoric. Clojure
offered only a single filter, and it followed all of the generators,
so:

(time (first (doall (for [x (range 1 1000) y (range 1 1000)] (< x 2)
[x,y]))))

was thus equivalent to:

(time (first (doall (for5 [x (range 1 1000) y (range 1 1000) :when (<
x 2)] [x y]))))

with identical results and performance.

But I do think having a filter per sequence expression is superior, so
I've enhanced Clojure's 'for' to support that, using :when as you
suggested:

(time (first (doall (for [x (range 1 1000000) :when (< x 2) y (range 1
1000)] [x y]))))
"Elapsed time: 1704.647 msecs"
[1 1]

In addition, I've added support for :while filters which short-circuit
(does Haskell have this?):

user=> (time (first (doall (for [x (range 1 1000000) :while (< x 2) y
(range 1 1000)] [x y]))))
"Elapsed time: 6.836 msecs"
[1 1]

which will offer superior performance for cases in which the filter
will never become true again once false, which are many:

(time (doall (take 100 (for [x (range 100000000) y (range

1000000) :when (< y x)] [x y]))))

"Elapsed time: 17361.471 msecs"

-> ([1 0] [2 0] [2 1] [3 0] [3 1] ...

(time (doall (take 100 (for [x (range 100000000) y (range

1000000) :while (< y x)] [x y]))))
"Elapsed time: 1.508 msecs"

-> ([1 0] [2 0] [2 1] [3 0] [3 1] ...

Everyone on SVN should note that you will have to move your filter
clause into the seq-expressions vector and specify :when or :while.

Thanks for the suggestion,

Rich