Julia: Support broadcasting for `Set`

[dlfivefifty]

I'm surprised this doesn't work:

julia> versioninfo()
Julia Version 0.7.0-DEV.1377
Commit a945af3aae (2017-08-17 16:48 UTC)
Platform Info:
  OS: macOS (x86_64-apple-darwin16.7.0)
  CPU: Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
  WORD_SIZE: 64
  BLAS: libgfortblas
  LAPACK: liblapack
  LIBM: libopenlibm
  LLVM: libLLVM-3.9.1 (ORCJIT, broadwell)
Environment:

julia> exp.(Set([1,2,3]))
ERROR: MethodError: no method matching exp(::Set{Int64})
Closest candidates are:
  exp(::BigFloat) at mpfr.jl:528
  exp(::Complex{Float16}) at math.jl:992
  exp(::Float16) at math.jl:991
  ...
Stacktrace:
 [1] broadcast(::Function, ::Set{Int64}) at ./broadcast.jl:434

[dlfivefifty]

More confusingly, two argument map works, even though the ordering doesn't make sense here:

julia> map(+, Set([1,2,3]), Set([4,5,6]))
3-element Array{Int64,1}:
 6
 8
 7

[ararslan]

the ordering doesn't make sense here

The order of iteration over a Set is undefined.

Since we define map(f, ::Set) I agree it would also make sense to define broadcast(f, ::Set).

[dlfivefifty]

The order of iteration over a Set is undefined.

Sorry, that was the point I was trying to make: map(+, Set([1,2]), Set([3,4])) should throw an error since the ordering is undefined.

[dlfivefifty]

In an ideal world, the following would also work:

Set([1,2,3]) .+ 2

[TotalVerb]

My intuitive expectation for broadcasting over sets is to operate on the cartesian product, since the math notation {1, 2} + {3, 4} often means {4, 5, 6}. However this is not very consistent with array broadcast.

[dlfivefifty]

That might be a reasonable definition for Set([1,2]) + Set([3,4]), but I don't think it makes sense to define Set([1,2]) .+ Set([3,4]).

[stevengj]

Note that currently a Set is treated like a "scalar" in broadcast, consistent with the rule that broadcast is only defined for collections with "shape". Hence you can do:

julia> [Set([1,2]), Set([3,4])] .∪ Set([5])
2-element Array{Set{Int64},1}:
 Set([2, 5, 1])
 Set([4, 3, 5])

Would we want to keep that behavior for mixing arrays and sets? That could get confusing, if a Set by itself (or a mixture of one set and scalars to support Set([...]) .+ 2) was treated as a collection. Or disallow it, so you'd have to do [Set([1,2]), Set([3,4])] .∪ Ref(Set([5])) or similar? It also kind of violates the spirit of broadcasting if you can broadcast with a single Set but not with two Sets.

My inclination is to just say that you need to use map for sets. The "broadcast is for containers with shape (and order)" rule is not a "do what I mean" rule, but at least it has some logical consistency.

[dlfivefifty]

The issue with only allowing map is that it's impossible to do the following without requiring everytime:

function foo(s::Set,k::Number)
   map(x->x+k, s)
end

If broadcasting is supported, then this can be done via

function foo(s::Set,k::Number)
   broadcast(+, s, k)
end

For the issue of precedence: I also came across this in ApproxFun, where both array's and Funs support broadcasting, with different meanings. My solution was to have Array take precedence of Fun: if there is an Array argument, then it uses the standard broadcasting definition.

I think this solution would be reasonable for Sets too: have Array take precedence, so that [Set([1,2]), Set([3,4])] .∪ Set([5]) would work as you describe. This would be possible with a few function definitions:

promote_containertype(::Type{Set}, ::Type{Set}) = Set
promote_containertype(::Type{Array}, ::Type{Set}) = Array
promote_containertype(::Type{Set}, ::Type{Array}) = Array
promote_containertype(::Type{Set}, ct) = Set
promote_containertype(ct, ::Type{Set}) = Set

[TotalVerb]

Considering that sets don't have a natural order, I'm not sure what this behavior (for cases with >1 argument) even means. Is Set([1,2]) .+ Set([3,4]) being non-deterministically Set([4,6]) or Set([5]) really the desired behavior here? @dlfivefifty brought up similar concerns above.

[mbauman]

Yes, I think you're right. Thank you so much. I was basing the new behavior on https://github.com/JuliaLang/julia/issues/19577, but the better solution here is
https://github.com/JuliaLang/julia/issues/20678 and erroring here.

[mbauman]

We decided to stick with the enumerated plan in https://github.com/JuliaLang/julia/pull/26980 that I had initially implemented.