DomainSetsCore.jl package?

[daanhb]

I believe there was a suggestion at some point to create a new package that would define a Domain type. I can't seem to find the comment. Anyway, I think at some point it will be a good way forward, hence this issue. No rush I guess.

Possible definitions may be: 1.

abstract type Domain end

2.

abstract type AbstractDomain end

abstract type Domain{T} <: AbstractDomain end

Base.eltype(::Type{<:Domain{T}}) where T = T

3.

abstract type Domain{T} end

Base.eltype(::Type{<:Domain{T}}) where T = T

These possibilities of course relate to the discussion of whether or not a domain has an eltype.

My current personal stance is that domains represent discrete or continuous sets (which sets them apart from existing sets in Julia), that sets are expected to have elements, and that it is useful to convey information about that. However, we could ensure that T=Any is a perfectly acceptable option, as it is in Julia for arrays:

julia> ["1", 2]
2-element Vector{Any}:
  "1"
 2

and for dictionaries:

julia> Dict("2"=>1, 2 => "3")
Dict{Any, Any} with 2 entries:
  2   => "3"
  "2" => 1

and for sets:

julia> Set([1, "2"])
Set{Any} with 2 elements:
  "2"
  1

In that case, for simplicity I'd favour the third option above.

[hyrodium]

I believe there was a suggestion at some point to create a new package that would define a Domain type. I can't seem to find the comment.

x-ref: https://github.com/JuliaMath/IntervalSets.jl/issues/106#issuecomment-1332258685 https://github.com/JuliaMath/IntervalSets.jl/pull/126#issuecomment-1332012309

[dlfivefifty]

Probably make it plural a la ChainRulesCore.jl and StaticArrays.jl (either DomainSetsCore.jl or DomainsCore.jl)

[dlfivefifty]

But if you are doing that I'd propose going all in the interface as opposed to an abstract type. E.g.

module DomainCore

abstract type DomainStyle end

"""
    IsDomain()

indicates it satisfies the domain interface, i.e. supports `in`.
"""
struct IsDomain <: DomainStyle end
struct NotDomain <: DomainStyle end

DomainStyle(::Type) = NotDomain()
DomainStyle(::Type{<:AbstractSet}) = IsDomain()
DomainStyle(::Type{<:AbstrctArray}) = IsDomain()

end

[daanhb]

Are there any other packages doing that? I agree it would be the most flexible approach, but it seems like we may have to explore quite a bit of new ground for this to work.

[daanhb]

Probably make it plural a la ChainRulesCore.jl and StaticArrays.jl (either DomainSetsCore.jl or DomainsCore.jl)

DomainSetsCore.jl seems to be the most common suggestion (DomainsCore reads a bit like DomainScore)

[daanhb]

I'm warming up to the idea of an interface. Looks like it might work and solve several issues. (And perhaps create new ones, but we'll see.)

[zsunberg]

I am totally on board for an interface for continuous sets and would like to contribute! I was just in a meeting with @mykelk and @jamgochiana where we were talking about the need for this.

What if we just called it SetInterface.jl? That is a bit presumptuous, but if we got enough people on board, this could be extremely helpful!!

[daanhb]

This seems like an example of a package providing an interface not unlike what is proposed above: https://github.com/JuliaMath/DensityInterface.jl (edit: to be clear, the interface is for a different field, not for continuous sets)

[daanhb]

Update: see here for a possible DomainSetsCore.jl package.

[daanhb]

Update: for experimentation I've made a first working version of DomainSetsCore.jl along with IntervalSets.jl and DomainSets.jl. Aiming for interfaces rather than inheritance, intervals in IntervalSets on this branch no longer inherit from Domain. The package is independent of DomainSets and DomainSetsCore. (I don't think this is a good idea, see below.)

I've adapted DomainSets to make it interoperate with sets that implement the domain interface, but that do not necessarily inherit from Domain. See this branch. The change is fairly massive, but less so than I was expecting. A lot had been done already.

Long story short: it can be made to work, but it is a bit painful and ugly here and there.

The changes to DomainSets are fine and may be worth it. Working on the library becomes more complicated, but that is invisible to an end-user. However, working with intervals changes in a way that requires user cooperation.

Here is an example to illustrate the technical solution and the implications. We essentially want to group types outside of the type hierarchy, namely the group of all types that implement the domain interface. Such grouping is pretty much the definition of traits, but Julia does not support traits and existing trait packages aren't widely used. So we have to do traits manually.

There are two ways we can indicate that an object should be treated as a domain, rather than interpreted based on its type. I'll use the union of two domains as an example. Since the domain-property is not based on type, it is not enough to define union(d1::Domain, d2::Domain). We can not change the untyped fallback definition of union(d1,d2) to check for a domain property either, as somebody else might want to do that for other traits. The two ways out are:

1. We change the function name. The method uniondomain indicates that its arguments will be interpreted as domains, regardless of their type:

   julia> uniondomain(0..1, 2..3.0)
   (0.0 .. 1.0) ∪ (2.0 .. 3.0)

2. We use a wrapper type. The notation AsDomain(d) means that d should be interpreted as a domain. Now we can use union:

   julia> AsDomain(0..1) ∪ AsDomain(2..3.0)
   (0.0 .. 1.0) ∪ (2.0 .. 3.0)

I've implemented both. The latter is what I mean by user cooperation. The user has to explicitly indicate that the interval is to be treated as a domain if he or she wants to use standard syntax. Otherwise the result is an error:

julia> (0..1) ∪ (2..3.0)
ERROR: ArgumentError: Cannot construct union of disjoint sets.

In order to get the test suite of DomainSets passing, I've had to sprinkle AsDomain's in many places. For the internals of DomainSets, it is sufficient to anticipate arguments of type Domain or of type AsDomain, the latter being just a reference to a domain (of any type).

The changes to DomainSets are an improvement, I think, though it requires some knowledge of what's going on before one can use it. For example, we can mix intervals of different types:

julia> using IntervalSets, Intervals

julia> d1 = 0..1
0 .. 1

julia> typeof(d1)
ClosedInterval{Int64} (alias for IntervalSets.Interval{:closed, :closed, Int64})

julia> d2 = Intervals.Interval(2.0, 3.0)
Intervals.Interval{Float64, Closed, Closed}(2.0, 3.0)

julia> d = AsDomain(d1) ∪ d2
(0.0 .. 1.0) ∪ [2.0 .. 3.0]

julia> 0.5 ∈ d
true

julia> 2.5 ∈ d
true

julia> 1.5 ∈ d
false

The union of the two domains even promoted the eltype of d1 to Float64.

@dlfivefifty @hyrodium @zsunberg

My suggestion for now: we use DomainSetsCore in the current form, implement the corresponding changes in DomainSets.jl, but keep the intervals of IntervalSets inheriting from Domain{T}. Strictly speaking that might not even be a breaking change. It would be a status quo for both packages involved, and a net benefit for interoperability. I think more experiments are needed for fallback downstream before changing the inheritance tree or removing the T type parameter.

[daanhb]

I've made a few PR's to make it easy to see the changes: IntervalSets: https://github.com/JuliaMath/IntervalSets.jl/pull/155 DomainSets: https://github.com/JuliaApproximation/DomainSets.jl/pull/140

In these PR's, Domain{T} moves to DomainSetsCore, and intervals continue to inherit from it. That is the least invasive change for IntervalSets.

[zsunberg]

@daanhb Thanks for doing all of the work to try this out!!

We essentially want to group types outside of the type hierarchy, namely the group of all types that implement the domain interface.

I didn't realize that this is the key challenge, but your example with union makes it very clear. I'm going to try to think about it some more. One question: Do you intend to support something like union(Set(1), 1..2)?

[daanhb]

I didn't realize that this is the key challenge, but your example with union makes it very clear. I'm going to try to think about it some more. One question: Do you intend to support something like union(Set(1), 1..2)?

Yes, in fact that already works. As soon as one of d1, d2 in union(d1,d2) is a Domain, we can safely interpret the union as the union of domains. Since 1..2 is a Domain (for now), that syntax already works:

julia> union(Set(1), 1..2)
1 .. 2

julia> union(Set(1), 2..3)
Set{Int64} with 1 element:
  1 ∪ (2 .. 3)

julia> union(Set(1.0), 2..3)
S ∪ (2.0 .. 3.0)

S = Set{Float64} with 1 element:
  1.0

The result depends on whether or not the element of the set lies in the interval. In the final case the element types are promoted.

[zsunberg]

@daanhb covered most of the main ideas that I have below in his previous post, but I will rehash in a slightly different way in case it is helpful (and as an exercise for myself).

TLDR: Requiring sets to be a subtype of Domain is a burden, but I do not currently see an alternative that is obviously better.

To expand on the interface-only package idea, a model package is AbstractTrees.jl.

The critical difference between AbstractTrees and DomainSets is that the DomainSets interface would like to include functions that are already defined in Base. I see two choices:

1. Introduce an abstract type (i.e. Domain)
2. Introduce new functions, e.g. DomainSetsCore.union and DomainSetsCore.eltype that are separate functions from Base.union etc., but may call functions from Base as fallbacks. (@daanhb presented the nearly-equivalent option of introducing new names, i.e. uniondomain, but this is perhaps a bit cleaner.)

Both of these introduce a significant cost: For approach (1), since Julia has only one type tree and only supports single inheritance, it is a big burden to introduce an abstract type and expect developers to subtype it. They have to choose one abstract type to subtype unless wrappers are used. For approach (2), if users do using DomainSetsCore and call union, they will get WARNING: both N and Base export "union"; uses of it in module Main must be qualified.

I guess I would fall on the side of DomainSetsCore.union, but I can understand the other choice.

One story that I am interested in: let's say that I am the author of GeometryBasics, and I want union(DomainSets.Rectangle([0,0], [1,2]), GeometryBasics.Rect(0,0,1,2) to work better than it currently does (i.e. I want it to return just one rectangle). What should I do?

[daanhb]

One story that I am interested in: let's say that I am the author of GeometryBasics, and I want union(DomainSets.Rectangle([0,0], [1,2]), GeometryBasics.Rect(0,0,1,2) to work better than it currently does (i.e. I want it to return just one rectangle). What should I do?

That is a very good question! DomainSets has a notion of "canonical domains", which you could hook into. Reducing domains to a smaller set of canonical ones allows simplifications when deciding equality of domains, and whether one domain might be a subset of another.

The first code to add for GeometryBasics (perhaps in an extension package) would be:

DomainSetsCore.domaineltype(d::Rect2{T}) where T = SVector{2,T}
DomainSets.convert_eltype(::Type{SVector{2,T}}, r::Rect2) where T = Rect2(map(T, r.origin), map(T, r.widths))

These two lines allow Rect2 to participate in the promotion of domains to a common eltype, when they are combined.

Next, the author could define the conversion of a GeometryBasics.Rect2 to a DomainSets.Rectangle and declare the latter to be "canonical":

todomainset(r::Rect2{T}) where T = Rectangle(SVector{2,T}(r.origin), SVector{2,T}(r.origin+r.widths))
DomainSets.canonicaldomain(::DomainSets.Equal, r::Rect2) = todomainset(r)

I had to update DomainSets a bit to make it work, but now on the "domaineltype" branch I get:

julia> using DomainSets, GeometryBasics

julia> rect1 = Rect(0, 0, 1, 2)
HyperRectangle{2, Int64}([0, 0], [1, 2])

julia> rect2 = Rectangle(SA[0,0], SA[1.0,2])
(0.0 .. 1.0) × (0.0 .. 2.0)

julia> isequaldomain(rect1, rect2)
true

julia> rect1 ∪ rect2
Rect2{Float64}([0.0, 0.0], [1.0, 2.0])

julia> rect2 ∪ rect1
(0.0 .. 1.0) × (0.0 .. 2.0)

Although the outcome depends on the order of the arguments, the code has recognized that these domains are equal and the union simplifies.

[daanhb]

Alternatively, the behaviour of uniondomain can be changed more directly. By default uniondomain(d1,d2) invokes uniondomain1(d1,d2), which in turn calls uniondomain2(d1,d2), which returns a UnionDomain. You can dispatch on the type of the first argument to uniondomain1(d1::MyType, d2) without ambiguity errors. The same is true for the second argument of uniondomain2. (There are lots of possible ambiguities when specializing uniondomain(d1,d2) directly.)

So you are free to write an implementation for DomainSets.uniondomain1(d1::Rect2, d2::SomeOtherType) and DomainSets.uniondomain2(d1::SomeOtherType, d2::Rect2) and do something special for those combinations of types.

[zsunberg]

Sorry I never responded to this. I still have a bias against interfaces that are abstract-type forward, but I don't have a perfect alternative suggestion, and this seems workable at least :) Seems like you should go forward with it.