JuliaMath / JuliaMath/IntervalSets.jl
Add support for unbounded intervals
- Dominant language
- Julia
- Stars
- 109
- Forks
- 29
- PR merge metrics
- No merged PRs in 30d
Description
As discussed in https://github.com/JuliaMath/IntervalSets.jl/issues/67#issuecomment-692981223, 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
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)
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.