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

RFC: I::CartesianIndices .+ j::CartesianIndex -> ::CartesianIndices #29890

Merged
merged 1 commit into from
Nov 18, 2018

Conversation

timholy
Copy link
Member

@timholy timholy commented Nov 1, 2018

In the course of implementing a multidimensional convolution I noticed this seems to be a natural but missing operation. This PR might be slightly provocative because it further cements the notion that CartesianIndex objects are treated like scalars when it comes to broadcasting. Currently this operation results in a "helpful" error message:

julia> I = CartesianIndices((0:2, 1:5))
3×5 CartesianIndices{2,Tuple{UnitRange{Int64},UnitRange{Int64}}}:
 CartesianIndex(0, 1)  CartesianIndex(0, 2)  CartesianIndex(0, 3)  CartesianIndex(0, 4)  CartesianIndex(0, 5)
 CartesianIndex(1, 1)  CartesianIndex(1, 2)  CartesianIndex(1, 3)  CartesianIndex(1, 4)  CartesianIndex(1, 5)
 CartesianIndex(2, 1)  CartesianIndex(2, 2)  CartesianIndex(2, 3)  CartesianIndex(2, 4)  CartesianIndex(2, 5)

julia> j = CartesianIndex(14,-22)
CartesianIndex(14, -22)

julia> I .+ j
ERROR: iteration is deliberately unsupported for CartesianIndex. Use `I` rather than `I...`, or use `Tuple(I)...`
Stacktrace:
 [1] getindex at ./array.jl:739 [inlined]
 [2] error(::String) at ./dict.jl:327
 [3] iterate(::CartesianIndex{2}) at ./multidimensional.jl:153
 [4] copyto!(::Array{Int64,1}, ::CartesianIndex{2}) at ./abstractarray.jl:646
 [5] _collect(::UnitRange{Int64}, ::CartesianIndex{2}, ::Base.HasEltype, ::Base.HasLength) at ./array.jl:563
 [6] collect(::CartesianIndex{2}) at ./array.jl:557
 [7] broadcastable(::CartesianIndex{2}) at ./broadcast.jl:609
 [8] broadcasted(::Function, ::CartesianIndices{2,Tuple{UnitRange{Int64},UnitRange{Int64}}}, ::CartesianIndex{2}) at ./broadcast.jl:1164
 [9] top-level scope at none:0
 [10] eval(::Module, ::Any) at ./client.jl:209
 [11] eval_user_input(::Any, ::REPL.REPLBackend) at /home/tim/src/julia-master/usr/share/julia/stdlib/v1.1/REPL/src/REPL.jl:501
 [12] run_backend(::REPL.REPLBackend) at /home/tim/.julia/dev/Revise/src/Revise.jl:766
 [13] (::getfield(Revise, Symbol("##58#60")){REPL.REPLBackend})() at ./task.jl:259

That error message is really intended to catch cases like a[j...], but it gets triggered here too. In any event, we'd need a specialized implementation just as we do for AbstractRange objects, because it's important to return it as a CartesianIndices object.

This has one notable omission: j .- I. That's because the result can't be expressed as a CartesianIndices. We could return an Iterators.product(...) result here, or a dense array, or just let it error. Thoughts?

I pushed this with ci skip because I want to insert the issue number into NEWS, and I don't know what will be assigned. Once any discussion happens I'll push an amended version.

@timholy timholy requested a review from mbauman November 1, 2018 16:46
@timholy timholy changed the title I::CartesianIndices .+ j::CartesianIndex -> ::CartesianIndices RFC: I::CartesianIndices .+ j::CartesianIndex -> ::CartesianIndices Nov 1, 2018
@mbauman
Copy link
Member

mbauman commented Nov 1, 2018

This has one notable omission: j .- I. That's because the result can't be expressed as a CartesianIndices. We could return an Iterators.product(...) result here, or a dense array, or just let it error. Thoughts?

We do support Iterators.reverse(::CartesianIndices) — we could return that?

NEWS.md Outdated Show resolved Hide resolved
@mbauman
Copy link
Member

mbauman commented Nov 1, 2018

Oh, and I'm fully in support of doubling down on the scalar-ness of a CartesianIndex.

@andyferris
Copy link
Member

+1

I’ve been thinking about what multidimensional dictionaries would look like. I’m pretty sure the keys are just the product of one-dimensional keys. Generally I’d love to think of the product of two abstract vectors as an (indexable) abstract matrix, and the product of abstract unit ranges as CartesianIndices.

(I need to think some more about the “scalarness”...)

@andyferris
Copy link
Member

andyferris commented Nov 3, 2018

Regarding scalarness: I can more-or-less think of CartesianIndexes forming a vector space over integer basis elements, as they support + and *. So if we pull on that thread a little, and we thought of CartesianIndex as an AbstractVector, then we'd want to write something like I .+ Ref(j) rather than I .+ j. This already works but returns a Matrix{CartesianIndex{2}} instead of a CartesianIndices{2}. So overloading something like that could be an alternative possibility.

It seems that the combination of linear indexing, and getindex with an AbstractVector index being already defined as non-scalar indexing, means that CartesianIndex couldn't be an AbstractVector{Int}. It also seems perfectly fine to support vector spaces which are not iterable and not subtypes of AbstractArray (though, when the basis is well defined like in this case, one might ask "why not?").

@timholy
Copy link
Member Author

timholy commented Nov 3, 2018

Regarding scalarness: I can more-or-less think of CartesianIndexes forming a vector space over integer basis elements, as they support + and *. So if we pull on that thread a little, and we thought of CartesianIndex as an AbstractVector, then we'd want to write something like I .+ Ref(j) rather than I .+ j.

I think of the Ref requirement as being about iterability rather than algebraic properties: numbers support + and * yet you don't wrap them in Ref. In terms of how we're using CartesianIndex, at a deep level I think it's better to think of it as a weird Integer ("linear indexing without the integer-division penalty") than as a vector. Of course the fact that they obey the algebra of vector spaces is also really convenient for many applications, so I'm not denying that the other way of thinking about them is attractive too. But #26227 (comment) is, in my view, a really important observation: even if we could make them iterable with good performance (which I am sure will be possible someday with a few more compiler enhancements), it seems increasingly clear that we shouldn't. They really are just "weird Integers" and should be treated as scalars.

Perhaps we'd want to also specialize the Ref version, though, since it is something that people are likely to try.

@timholy
Copy link
Member Author

timholy commented Nov 18, 2018

Updated and ready to merge, barring further objections.

@StefanKarpinski
Copy link
Member

@mbauman, if you're cool with this, please merge.

@mbauman mbauman merged commit ff74f6b into master Nov 18, 2018
@mbauman mbauman deleted the teh/bcastci branch November 18, 2018 20:45
fredrikekre added a commit that referenced this pull request Dec 5, 2018
changes between Julia 1.0 and 1.1, including:

- Custom .css-style for compat admonitions.

- Information about compat annotations to CONTRIBUTING.md.

- NEWS.md entry for PRs #30090, #30035, #30022, #29978,
  #29969, #29858, #29845, #29754, #29638, #29636, #29615,
  #29600, #29506, #29469, #29316, #29259, #29178, #29153,
  #29033, #28902, #28761, #28745, #28708, #28696, #29997,
  #28790, #29092, #29108, #29782

- Compat annotation for PRs #30090, #30013, #29978,
  #29890, #29858, #29827, #29754, #29679, #29636, #29623,
  #29600, #29440, #29316, #29259, #29178, #29157, #29153,
  #29033, #28902, #28878, #28761, #28708, #28156, #29733,
  #29670, #29997, #28790, #29092, #29108, #29782, #25278

- Documentation for broadcasting CartesianIndices (#30230).
- Documentation for Base.julia_cmd().
- Documentation for colon constructor of CartesianIndices (#29440).
- Documentation for ^(::Matrix, ::Number) and ^(::Number, ::Matrix).

- Run NEWS-update.jl.

Co-authored-by: Morten Piibeleht <morten.piibeleht@gmail.com>
Co-authored-by: Fredrik Ekre <ekrefredrik@gmail.com>
fredrikekre added a commit that referenced this pull request Dec 5, 2018
changes between Julia 1.0 and 1.1, including:

- Custom .css-style for compat admonitions.

- Information about compat annotations to CONTRIBUTING.md.

- NEWS.md entry for PRs #30090, #30035, #30022, #29978,
  #29969, #29858, #29845, #29754, #29638, #29636, #29615,
  #29600, #29506, #29469, #29316, #29259, #29178, #29153,
  #29033, #28902, #28761, #28745, #28708, #28696, #29997,
  #28790, #29092, #29108, #29782

- Compat annotation for PRs #30090, #30013, #29978,
  #29890, #29858, #29827, #29754, #29679, #29636, #29623,
  #29600, #29440, #29316, #29259, #29178, #29157, #29153,
  #29033, #28902, #28878, #28761, #28708, #28156, #29733,
  #29670, #29997, #28790, #29092, #29108, #29782, #25278

- Documentation for broadcasting CartesianIndices (#30230).
- Documentation for Base.julia_cmd().
- Documentation for colon constructor of CartesianIndices (#29440).
- Documentation for ^(::Matrix, ::Number) and ^(::Number, ::Matrix).

- Run NEWS-update.jl.

Co-authored-by: Morten Piibeleht <morten.piibeleht@gmail.com>
Co-authored-by: Fredrik Ekre <ekrefredrik@gmail.com>
fredrikekre added a commit that referenced this pull request Dec 5, 2018
Addition of NEWS and compat admonitions for important changes between Julia 1.0 and 1.1, including:

- Custom .css-style for compat admonitions.

- Information about compat annotations to CONTRIBUTING.md.

- NEWS.md entry for PRs #30090, #30035, #30022, #29978,
  #29969, #29858, #29845, #29754, #29638, #29636, #29615,
  #29600, #29506, #29469, #29316, #29259, #29178, #29153,
  #29033, #28902, #28761, #28745, #28708, #28696, #29997,
  #28790, #29092, #29108, #29782

- Compat annotation for PRs #30090, #30013, #29978,
  #29890, #29858, #29827, #29754, #29679, #29636, #29623,
  #29600, #29440, #29316, #29259, #29178, #29157, #29153,
  #29033, #28902, #28878, #28761, #28708, #28156, #29733,
  #29670, #29997, #28790, #29092, #29108, #29782, #25278

- Documentation for broadcasting CartesianIndices (#30230).
- Documentation for Base.julia_cmd().
- Documentation for colon constructor of CartesianIndices (#29440).
- Documentation for ^(::Matrix, ::Number) and ^(::Number, ::Matrix).

- Run NEWS-update.jl.


Co-authored-by: Morten Piibeleht <morten.piibeleht@gmail.com>
Co-authored-by: Fredrik Ekre <ekrefredrik@gmail.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

4 participants