Add support for unbounded intervals

[hyrodium]

As discussed in #67 (comment), we currently don't support unbounded intervals.
This issue is a proposal for adding types such as

• LeftUnboundedInterval{R,T} $\{x \ | \ x < a\}$
• RightUnboundedInterval{L,T} $\{x \ | \ a < x\}$
• ComplementInterval{L,R,T} $\{x \ | \ x < a \ \text{or} \ x > b\}$.

Define new concrete types, or allow a new type parameter?

We have the following two choices to implement unbounded intervals.

• Define new LeftUnboundedInterval{R, T} and RightUnboundedInterval{L, T}.
• Allow a new type parameter :unbounded. (This is the same approach as Intervals.jl)

I prefer the first, because:

• Duplicated fields of leftendpoint and rightendpoint seems verbose.
  • See https://github.com/invenia/Intervals.jl/blob/c16d29055e9712fa1fd84aac2234cbc57af15f3e/src/interval.jl#L71
• The in method with Interval{:unbounded, :unbounded} will cause some confusion.

julia> using Intervals

julia> i = Interval{Int,Unbounded,Unbounded}(nothing,nothing)  # (-∞,+∞)
Interval{Int64, Unbounded, Unbounded}(nothing, nothing)

julia> 3 in i
true

julia> "a" in i  # confusing
true

julia> i = Interval{Int,Open,Unbounded}(1,nothing)  # (1,+∞)
Interval{Int64, Open, Unbounded}(1, nothing)

julia> 3 in i
true

julia> "a" in i
ERROR: MethodError: no method matching isless(::String, ::Int64)
Closest candidates are:
  isless(::AbstractString, ::AbstractString) at strings/basic.jl:344
  isless(::AbstractFloat, ::Real) at operators.jl:186
  isless(::Real, ::Real) at operators.jl:434
  ...

Where the proposed type LeftUnboundedInterval{L,R,T} is a subtype of AbstractInterval{T}.
I think we need another abstract type just like IntervalSets.TypedEndpointsInterval.

What should the set operator return?

i1 = RightUnboundedInterval{:open, Int}(3) is a interval $(3, +∞)$, and i2 = LeftUnboundedInterval{:closed, Int}(5) is a interval $(-\infty, 5]$.
Then, what should i1 ∪ i2 be? Should we define a new type for $(-∞, +∞)$?
I prefer not to define the new type because:

• The new type represents a whole real number, but we even don't have a special type for an empty set.
  • 2..1 is an example of an empty interval
• The new type has the same problem as in(::Interval{Int64, Unbounded, Unbounded}) method, already discussed abobe.
• If $(-∞, 1) \cup (2, \infty)$ throws an error, then the correct return is only $(-∞, ∞)$ which is really trivial.

Here, I propose adding a new type with ComplementInterval{L,R,T} which represents sets such as $\{x \ | \ x < a \ \text{or} \ x > b\}$, then the ComplementInterval(2,1) represents the whole real numbers.
With these methods and types, the following methods can be defined:

• complement(::Interval) type-stable
• complement(::LeftUnboundedInterval) type-stable
• complement(::RightUnboundedInterval) type-stalbe
• union(::LeftUnboundedInterval, ::LeftUnboundedInterval) type-stability depends on the boundaries
• union(::RightUnboundedInterval, ::LeftUnboundedInterval) type-stable
• union(::LeftUnboundedInterval, ::RightUnboundedInterval) type-stable
• union(::RightUnboundedInterval, ::RightUnboundedInterval) type-stability depends on the boundaries
• intersection(::LeftUnboundedInterval, ::LeftUnboundedInterval) type-stability depends on the boundaries
• intersection(::RightUnboundedInterval, ::LeftUnboundedInterval) type-stable
• intersection(::LeftUnboundedInterval, ::RightUnboundedInterval) type-stable
• intersection(::RightUnboundedInterval, ::RightUnboundedInterval) type-stability depends on the boundaries
• intersection(::Interval, ::LeftUnboundedInterval) type-stability depends on the boundaries
• intersection(::Interval, ::LeftUnboundedInterval) type-stability depends on the boundaries
• intersection(::Interval, ::RightUnboundedInterval) type-stability depends on the boundaries
• intersection(::Interval, ::RightUnboundedInterval) type-stability depends on the boundaries
• intersection(::LeftUnboundedInterval, ::Interval) type-stability depends on the boundaries
• intersection(::RightUnboundedInterval, ::Interval) type-stability depends on the boundaries
• intersection(::LeftUnboundedInterval, ::Interval) type-stability depends on the boundaries
• intersection(::RightUnboundedInterval, ::Interval) type-stability depends on the boundaries

The following methods might throw ArgumentError just like union(1..2, 3..4).

• union(::Interval, ::LeftUnboundedInterval) type-stability depends on the boundaries
• union(::Interval, ::LeftUnboundedInterval) type-stability depends on the boundaries
• union(::Interval, ::RightUnboundedInterval) type-stability depends on the boundaries
• union(::Interval, ::RightUnboundedInterval) type-stability depends on the boundaries
• union(::LeftUnboundedInterval, ::Interval) type-stability depends on the boundaries
• union(::RightUnboundedInterval, ::Interval) type-stability depends on the boundaries
• union(::LeftUnboundedInterval, ::Interval) type-stability depends on the boundaries
• union(::RightUnboundedInterval, ::Interval) type-stability depends on the boundaries

Questions

• Do you have any thoughts on my proposal?
• Is it okay to have ComplementInterval <: AbstractInterval?
  • Note that a complement of an interval is not an interval.
• What should the return type of complement(::ComplementInterval{:open,:closed}) be?
  • Interval{:open,:closed}; this implies ComplementInterval{:open,:closed} is a complement of Interval{:open,:closed}
  • Interval{:closed,:open}; this implies the endpoints of ComplementInterval are specified directly.
• What should the type hierarchy be?
  • With abstract types TypedRightUnboundedInterval, TypedLeftUnboundedInterval, and TypedEndpointsComplementInterval
    • RightUnboundedInterval{L,T} <: TypedRightUnboundedInterval{L,T} <: AbstractInterval{T}
    • LeftUnboundedInterval{R,T} <: TypedLeftUnboundedInterval{R,T} <: AbstractInterval{T}
    • ComplementInterval{L,R,T} <: TypedEndpointsComplementInterval{L,R,T} <: AbstractInterval{T}
  • With more abstract type UnboundedInterval
    • UnboundedInterval{T} <: AbstractInterval{T}
    • RightUnboundedInterval{L,T} <: TypedRightUnboundedInterval{L,T} <: UnboundedInterval{T}
    • LeftUnboundedInterval{R,T} <: TypedLeftUnboundedInterval{R,T} <: UnboundedInterval{T}
    • ComplementInterval{L,R,T} <: TypedEndpointsComplementInterval{L,R,T} <: UnboundedInterval{T}
  • With another abstract type AbstractOrderedSet{T}
    • AbstractInterval{T} <: AbstractOrderedSet{T} <: Domain{T}
    • TypedEndpointsComplementInterval{L,R,T} <: AbstractOrderedSet{T} <: Domain{T}

Any feedback is welcomed!

(cc: @timholy @dlfivefifty @daanhb @omus)

[dlfivefifty]

What was wrong with just using 1..Inf ?

[dlfivefifty]

Note also ComplementInterval comes up in the "extended interval Newton method" and so the terminology should be consistent... I'll check Tuckers book when I'm in the office

[hyrodium]

What was wrong with just using 1..Inf ?

• It promotes Int to Float64, so it's better to have a method to avoid the promotion. (x-ref: Should eltype(1..2) be Float64? (currently it is Int) #115 (comment))
• Non-real intervals such as Date(2022,09,26) .. Inf are not supported.

[zsunberg]

@hyrodium note that both of the problems in the comment above would be fixed by #122 :) I think the behavior in #122 will allow a lot of things to be expressed more naturally.

[hyrodium]

The topics in this issue and #122(#121) are totally different. We just want unbounded intervals, and non-promoted 1..Inf is incomplete because it's different from 1..Inf32. (We don't want to distinguish them.) Date objects is not comparable with Float64, so non-promoted Date(2022,09,26) .. Inf is invalid.

[zsunberg]

Ah, I see the issue with Date. That makes me agree that the Inf solution is not enough.

Regarding 1..Inf32 and 1..Inf, just out of curiosity, we currently have

julia> 1..Inf32 == 1..Inf
true

Is that not the desired behavior?

[hyrodium]

It's okay to have 1..Inf32 == 1..Inf because Inf32 == Inf. What I mean was, defining unbounded intervals should not depend on whether Inf::Float64 or Inf32::Float32.

[daanhb]

Overall, I'd also favour having more and simpler concrete types over having a more complicated interval type that supports everything (like a swiss army knife of intervals). Code will be easier to write and easier to read. It does indeed require some thought about a good choice of abstract types to make it easy to write generic implementations at the right level. (I did not think about the suggestions.)

[daanhb]

Also, I'm beginning to wonder why being open and closed are type parameters, since it seems to lead to quite a few type-instabilities of set operations. I guess it is an optimization, to save on memory (storing two booleans) and possibly saving some if-else statements in set operations by using dispatch.

[hyrodium]

The subtypes of IntervalSets.TypedEndpointsInterval have information about whether the endpoints are closed in their type. However, AbstractInterval does not require the property, so if someone wants a type-stable interval type with set operations, one can define it as a subtype of AbstractInterval.

I don't have use cases that require high-performance (with type-stability) with set operations, so the current implementation is enough for me.

[hyrodium]

Note also ComplementInterval comes up in the "extended interval Newton method" and so the terminology should be consistent... I'll check Tuckers book when I'm in the office

@dlfivefifty Is there any update on this?

[dlfivefifty]

No

[rofinn]

Hmm, I wonder if rather than handling this in the type structure we could just support it through duck typing? Basically something like requiring methods for isleftbounded(::AbstractInterval{T}) and isrightbounded(::AbstractInterval{T}).

Pros:

1. Doesn't complicate the type structure
2. Current behaviour remains unchanged
3. We don't need to handle this for every possible value of T
4. Provides a simple mechanism for overloading behaviour for specific types of intervals

Cons:

1. Doesn't directly address the original concern... you'd still need to explicitly overload the behaviour for things like Int or Date.
2. Promote type-piracy when end users don't control the definition of the interval type or eltype T.
3. Might be more principled to just have endpoints be Union{T, Infinity} (like Union{T, Missing} or Union{T, Nothing}) and use Infinities.jl to handle those definitions?