JuliaMath / JuliaMath/IntervalSets.jl

Add support for unbounded intervals

Open
#123 13 comments 0 reactions 0 assignees View on GitHub
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.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.