Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Support guards/filters in comprehensions #550

Closed
pao opened this issue Mar 9, 2012 · 39 comments
Closed

Support guards/filters in comprehensions #550

pao opened this issue Mar 9, 2012 · 39 comments
Milestone

Comments

@pao
Copy link
Member

@pao pao commented Mar 9, 2012

Quoting @rtzui in #547:
On the other hand more powerful:

x=[1,2,3,4,510,1,2,3,1,9]
y=[sqrt(a) | a ∈ x, x%2==0]

(Discussion from @pao)
There is an open syntactic question. The Haskell syntax (shown above) has guards as boolean expressions separated by commas and interspersed with membership assertions, which works as long as you can tell the difference between an expression evaluating to a boolean and a loop assignment statement. Python uses the keyword "if" to precede each guard. I'm sure there are other approaches as well.

(From @JeffBezanson)
It's maybe not ideal, but you can accomplish this as:

x=[1,2,3,4,510,1,2,3,1,9]
y=[sqrt(a) | a in x[x%2==0] ]
@pao
Copy link
Member Author

@pao pao commented Mar 9, 2012

Jeff's workaround for this particular case is fine, but in general guards could include multiple comprehension variables, as in the Cartesian product except the diagonal:

Prelude> [(a,b) | a <- [1..4], b <- [1..4], a /= b]
[(1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3)]
>>> [(a,b) for a in range(1,5) for b in range(1,5) if a != b]
[(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3)]

I don't see how to get there with the current list comprehension capabilities.

@ViralBShah
Copy link
Member

@ViralBShah ViralBShah commented Mar 9, 2012

I call what we have array comprehensions. The size of the output array is determined by the ranges before the computation starts, and that would be difficult with guards. One could always extract a subarray at the end though, if guards are used, and they should not be too difficult to implement either.

We do need to debate if we want this, and the actual syntax. @StefanKarpinski Given that you came up with the original comprehensions idea, what are your thoughts?

@StefanKarpinski
Copy link
Member

@StefanKarpinski StefanKarpinski commented Mar 9, 2012

Filters and guards don't mix with multidimensional comprehensions. For 1-d comprehensions, I'm not convinced that it's really worth the additional syntax. What's the case for making it part of the syntax instead of just using a filter function?

@rtzui
Copy link

@rtzui rtzui commented Mar 9, 2012

/edit. here was something else, but it was BS.

I don't see the advantage of guards to array slices a la x[x>3], but it don't see the problem with multi dimensions since the slices already operate on multi dimension arrays.

multiple comprehension variables would be cool thou, but I think it would be cooler this way:

((1..4) insert appropriate operator here (1..4))[ (x,y) -> x /= y]

@StefanKarpinski
Copy link
Member

@StefanKarpinski StefanKarpinski commented Mar 9, 2012

Because it doesn't work in higher dimensions: you can't just excise arbitrary items out of a matrix and still get a matrix.

@ViralBShah
Copy link
Member

@ViralBShah ViralBShah commented Mar 9, 2012

One could set values to be excised to zero or some other default provided by the user. One could implement diag, triu, tril, spdiags, etc. using comprehensions. This kind of stuff would be great for experimenting and exploration. However, these would be bad implementations, since even though the running time complexity is the same, one ends up consuming many more flops than necessary.

-viral

On 09-Mar-2012, at 3:24 PM, Stefan Karpinski wrote:

Because it doesn't work in higher dimensions: you can't just excise arbitrary items out of a matrix and still get a matrix.


Reply to this email directly or view it on GitHub:
#550 (comment)

@rtzui
Copy link

@rtzui rtzui commented Mar 9, 2012

julia> x=[1 2 3 4; 5 6 7 9]
2x4 Int64 Array:
 1  2  3  4
 5  6  7  9

julia> [ a | a = x ]
{1, 5, 2, 6, 3, 7, 4, 9}

Today the output is always one dimensional. Or am i missing something?

@pao
Copy link
Member Author

@pao pao commented Mar 9, 2012

Above comments re: full array comprehensions seem reasonable. There are contexts (like the Cartesian product minus the diagonal) where you'd be okay with that array flattened, and some where you would really prefer to never evaluate "invalid" pairs:

[ does_something_useful_but_throws_exception_if_equal(a, b) | a in 1:4, b in 1:4 ]

It might be the case that we'd rather this idiom be written with a double-for-loop-with-inner-if, but adding a guard to this expression is definitely more concise Cartesian for loop and if statement, which was mentioned in #330 but doesn't seem to be documented in the Control Flow section of the manual.

@pao
Copy link
Member Author

@pao pao commented Mar 9, 2012

@rtzui Try [(a,b) | a in 1:4, b in 1:4]. The final array has one dimension per expression on the RHS of the bar.

@pao
Copy link
Member Author

@pao pao commented Mar 10, 2012

I've written a small patch for the manual to mention the Cartesian for feature, JuliaLang/www_old.julialang.org#8.

@pao pao mentioned this issue Apr 28, 2012
@JeffBezanson
Copy link
Member

@JeffBezanson JeffBezanson commented May 3, 2012

I guess this could be implemented by transforming 1d comprehensions with guards to loops using push.

@StefanKarpinski
Copy link
Member

@StefanKarpinski StefanKarpinski commented May 3, 2012

I guess this could be implemented by transforming 1d comprehensions with guards to loops using push.

That's a solid idea. Another option would be to pre-allocate the whole thing and then shrink at the end. Might want to choose between the two approaches based on a threshold. (Guards would still only work in the 1d case.)

@pao
Copy link
Member Author

@pao pao commented Sep 9, 2012

This is pretty absurd, but with https://gist.github.com/3677645 (UPDATE 2013-04-03: or Monads.jl) you can do:

julia> @mdo begin
         a <- MList(1:3)
         b <- MList(1:3)
         guard(MList, a!=b)
         return (a,b)
       end
MList([(1,2), (1,3), (2,1), (2,3), (3,1), (3,2)])
@diegozea
Copy link
Contributor

@diegozea diegozea commented Apr 4, 2013

Would be good have a while sentence for list comprehension too.
This is the proposal for python: http://www.python.org/dev/peps/pep-3142/

@diegozea
Copy link
Contributor

@diegozea diegozea commented Apr 10, 2013

I would like to write Symmetric matrices using list comprehension:

symmat = [ f(x[i],y[j]) for i in 1:length(x), j in i:length(y) ] 

or why not, something like

symmat = [ f(x[i],y[j]) for i in 1:length(x), j in 1:length(y) if i<=j ] 

Maybe some operator, like :, can be overload in order to generate the combinations

symmat_with_diag = [ f(pair) for pair in x:y ] 
symmat_without_diag = [ f(pair) for pair in x:x ] 

Maybe symmetric matrix type can be a vector for only the upper o lower part, with special getindex and setindex methods. And the ability of be printed has complete matrix or list.

@milktrader
Copy link
Contributor

@milktrader milktrader commented Jul 6, 2013

S = [1, -1, 2, -2, 0]

As mentioned in dupe issues, comprehensions in other languages allow something along the lines of

[x for x in S if x > 0]

The work around for this problem seems to be

S[[x for x in S] .> 0]

Is this going to be the preferred choice? Or is there a more Julian way?

@milktrader
Copy link
Contributor

@milktrader milktrader commented Jul 6, 2013

There is of course the filter method.

filter(x -> x > 0, S)

but this is getting further from the beauty of comprehension syntax.

@diegozea
Copy link
Contributor

@diegozea diegozea commented Jul 6, 2013

S[[x for x in S] .> 0] is O(n²), isn't it ?

@StefanKarpinski
Copy link
Member

@StefanKarpinski StefanKarpinski commented Jul 6, 2013

It's O(2n), but that 2 is pretty important.

@quinnj
Copy link
Member

@quinnj quinnj commented Jul 6, 2013

Yeah, I think the whole I idea of comprehension filtering is that the filtering is happening during construction, like using an if-else block inside a for loop instead of running a full for loop and filtering afterwards.

@StefanKarpinski
Copy link
Member

@StefanKarpinski StefanKarpinski commented Aug 27, 2013

I've come around to the idea that having an if clause in a comprehension should force the result to be one-dimensional and grow as necessary. In particular, I just found myself writing Pkg code and wanting to do this:

[ver for (ver,info) in avail if head == info.sha1]

This is pretty hard to express otherwise. It can be done with filter and then map, but it's a bit awkward:

[keys(filter((ver,info)->head == info.sha1, avail))...]

This took me several minutes to get right. Having an if clause flatten comprehensions would allow us to express things that we can't right now, such as writing [ f(x,y) for x=v, y=w if true ] and getting a vector. Currently, this requires either a reshape or a pair of for loops, both of which are a rather awkward ways to express something that's simple to write in other languages.

@johnmyleswhite
Copy link
Member

@johnmyleswhite johnmyleswhite commented Aug 29, 2013

+1 for allowing if clauses in comprehensions by forcing them to be 1D.

@pao
Copy link
Member Author

@pao pao commented Aug 29, 2013

I hate to suggest syntax, but [... if true] seems like an awkward spelling to get a construction that's different than the existing array comprehension. Is [[ ... ]] ambiguous?

@StefanKarpinski
Copy link
Member

@StefanKarpinski StefanKarpinski commented Aug 29, 2013

It's a bit awkward, but it just kind of falls out and isn't the worst idiom I've ever seen. [[ ... ]] is totally non-obvious.

@milktrader
Copy link
Contributor

@milktrader milktrader commented Sep 2, 2013

another +1 for allowing filters and forcing 1D array

@john9631
Copy link

@john9631 john9631 commented Nov 14, 2013

I am commencing this work and will document my successes and failures using iJulia. At this point failure seems the more likely but I'm looking forward to the challenge.

If anyone should see me making a mistake please feel free to provide information :-)

@JeffBezanson JeffBezanson changed the title Support guards/filters in list comprehensions Support guards/filters in comprehensions Apr 3, 2014
@RaulDurand
Copy link

@RaulDurand RaulDurand commented Nov 16, 2014

Has been any update on this subject?
May be I am too late but I would like to make a suggestion for the use of if in array comprehensions:

L = [ i for i in R if i%2 > 0]       # OK: returns a 1D array
L = [ i+j for i in R, j in S if i>j]    # ERROR: 'if' not allowed in matrix comprehensions
L = [ i+j for i in R for j in S if i>j ]    # OK: returns a 1D array (a la Python)

if would not be allowed in matrix comprehensions.
The use of two for would return always a 1d array (a la Python).
That also would allow the second variable to depend on the first.

L = [ i+j for i=1:10 for j=i:10 if (i+j)%2==0 ]   # OK: returns a 1D array

I think in this way array comprehensions are perfectly clear and it doesn't mess the current syntax.

@chriscoey
Copy link

@chriscoey chriscoey commented Jan 7, 2015

I like Raul's idea for syntax.

Any updates on this? I would help if I wasn't such a noob! It would make Julia more attractive I think... I used list comprehensions with guards all the time in Python and they saved a lot of time/space.

@FGFW
Copy link

@FGFW FGFW commented Mar 15, 2016

S[S.> 0]

@diegozea
Copy link
Contributor

@diegozea diegozea commented Mar 15, 2016

What is the future/present of this now that generators exist?

@quinnj
Copy link
Member

@quinnj quinnj commented May 9, 2016

I know there's been a lot of discussion around final 0.5 feature triage, but I think this would be a great candidate. I'd hate for us to release 0.5 with generators only to have python-users everywhere wonder why this didn't come with it. From the discussion in #15023, it sounds like a pretty straightforward parsing re-write, which does limit the number of devs who'd feel comfortable making the change, but I think it'd be well worth it.

@kmsquire
Copy link
Member

@kmsquire kmsquire commented May 9, 2016

👍

@ararslan
Copy link
Member

@ararslan ararslan commented May 18, 2016

I think @StefanKarpinski's proposed placement of if in #16389 is cleaner than Raul's trailing if, i.e.

x^2 if x % 3 == 0 for x = 1:100 # versus
x^2 for x = 1:100 if x % 3 == 0
quinnj added a commit that referenced this issue Jun 25, 2016
JeffBezanson added a commit that referenced this issue Jun 27, 2016
this also uses the new lowering for typed comprehensions, allowing all
comprehensions on unknown-length iterables (fixes #1457)
JeffBezanson added a commit that referenced this issue Jun 28, 2016
this also uses the new lowering for typed comprehensions, allowing all
comprehensions on unknown-length iterables (fixes #1457)
JeffBezanson added a commit that referenced this issue Jun 29, 2016
this also uses the new lowering for typed comprehensions, allowing all
comprehensions on unknown-length iterables (fixes #1457)
JeffBezanson added a commit that referenced this issue Jul 6, 2016
this also uses the new lowering for typed comprehensions, allowing all
comprehensions on unknown-length iterables (fixes #1457)
mfasi added a commit to mfasi/julia that referenced this issue Sep 5, 2016
JuliaLang#4867)

this also uses the new lowering for typed comprehensions, allowing all
comprehensions on unknown-length iterables (fixes JuliaLang#1457)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
You can’t perform that action at this time.