add IntervalSets conversions

[aplavin]

[OlivierHnt]

Thanks for opening this PR. Looks reasonable to have this extension 🙂.

[OlivierHnt]

Mhmm I am not sure we want to have a conversion between IntervalSet.Interval and IntervalArithmetic.BareInterval (eg we do not allow conversion between IntervalArithmetic.BareInterval and Real). I know nothing about IntervalSet.jl, can you perform any sort of arithmetic operations on IntervalSet.Interval? E.g if x = IntervalSet.Interval(1, 2), then is x + 1 or x * 3.1 or x + x allowed?

PS: as mentioned before I am not opposed to this PR, it seems very reasonable for interval libraries to communicate. Though I am curious 🙂, is there any specific reason that motivated opening the PR?

[aplavin]

PS: as mentioned before I am not opposed to this PR, it seems very reasonable for interval libraries to communicate. Though I am curious 🙂, is there any specific reason that motivated opening the PR?

To represent intervals "in general", not specifically as a kind of numbers, IntervalSets are a great choice. They are lightweight, popular, and well-supported by other libraries, they define just the right amount of functionality.

But sometimes, for stuff like arithmetics or bounding function values, IntervalArithmetics are needed. Then one has all these questions on how to convert back and forth:

xint = 1..5  # IntervalSets interval, comes from external code
yint = Interval(myfunc(IA.interval(xint)))  # bound myfunc() values on xint
# yint can be used with anything supporting IntervalSets

For now, I have to copy-paste such conversion definitions whenever such a procedure is needed. Would be nice to have them packaged here! Thanks for all your comments, I'll try to incorporate them.

[aplavin]

I know nothing about IntervalSet.jl, can you perform any sort of arithmetic operations on IntervalSet.Interval?

Not at all, they are "intervals as sets", not "intervals as numbers". Does it affect your BareInterval advice? I added it only for completion, having bareinterval() (not convesion, just the function) is convenient for defining interval() here.

[OlivierHnt]

Yes it affects the BareInterval advice. Long story short, we disallowed conversion between Real and BareInterval because one could perform non-validated numerics and obtain some Real (typically I mean a float here) and then convert it to an interval type (whose bounds are therefore not guaranteed to contain the correct answer). The Interval type in IntervalArithmetic.jl has a special "guaranteed" flag to track this stuff, so conversion is allowed but the resulting interval has a special tag.

So if an IntervalSets.Interval can never be touched by any non-validated numerics (all defined operations are rounding errors free) then I think it is not a problem to have a conversion to BareInterval.

Then you could implement something like

# BareInterval <- IS.Interval
IA.bareinterval(i::IS.Interval) = IA.bareinterval(IS.endpoints(i)...)
IA.bareinterval(::Type{T}, i::IS.Interval) where {T<:IA.NumTypes} = IA.bareinterval(T, IS.endpoints(i)...)
Base.convert(::Type{IA.BareInterval}, i::IS.Interval) = IA.bareinterval(i)
Base.convert(::Type{IA.BareInterval{T}}, i::IS.Interval) where {T<:IA.NumTypes} = IA.bareinterval(T, i)

# BareInterval -> IS.Interval
IS.Interval(i::IA.BareInterval) = IS.Interval(IA.inf(i), IA.sup(i))
# maybe also IS.Interval{T,S,R}(i::IA.BareInterval) where {T,S,R} = IS.Interval{T,S,R}(IA.inf(i), IA.sup(i))
Base.convert(::Type{IS.Interval}, i::IA.BareInterval) = IS.Interval(i)
# maybe you want to add a conversion to a more specific signature, eg Base.convert(::Type{T}, i::IA.BareInterval) where {T<:IS.BareInterval} = T(i)

# Interval <- IS.Interval
IA.interval(i::IS.Interval) = IA.interval(IS.endpoints(i)...)
IA.interval(::Type{T}, i::IS.Interval) where {T<:IA.NumTypes} = IA.interval(T, IS.endpoints(i)...)
Base.convert(::Type{IA.Interval}, i::IS.Interval) = IA.interval(i)
Base.convert(::Type{IA.Interval{T}}, i::IS.Interval) where {T<:IA.NumTypes} = IA.interval(T, i)

# Interval -> IS.Interval
IS.Interval(i::IA.Interval) = IS.Interval(IA.inf(i), IA.sup(i))
# maybe also IS.Interval{T,S,R}(i::IA.Interval) where {T,S,R} = IS.Interval{T,S,R}(IA.inf(i), IA.sup(i))
Base.convert(::Type{IS.Interval}, i::IA.Interval) = IS.Interval(i)
# maybe you want to add a conversion to a more specific signature, eg Base.convert(::Type{T}, i::IA.Interval) where {T<:IS.Interval} = T(i)

[OlivierHnt]

A more perverse potential issue: does convert(::Type{<:IS.Interval}, x::Number) exists?

[aplavin]

A more perverse potential issue: does convert(::Type{<:IS.Interval}, x::Number) exists?

No, IntervalSets is quite strict and defines basically no implicit conversions. The only convert methods are between different Interval types – different endpoint number types, typed/untyped endpoints, such stuff.

[OlivierHnt]

Ok I looked at IntervalSets.jl. I found two issues (from the point of view of IntervalArithmetic.jl):

julia> using IntervalSets

julia> Interval(1e-120, 1e-119) # non trivial interval set
1.0e-120 .. 1.0e-119

julia> ClosedInterval{Float32}(1e-120 .. 1e-119) # issue #1: conversion did not widen the interval set
0.0 .. 0.0

julia> 1 ± 1e-120 # issue #2: the interval only contains 1
1.0 .. 1.0

If these are intentional, then we should not convert to BareInterval and implement

# Interval <- IS.Interval
function IA.interval(i::IS.Interval)
    x = IA.interval(IS.endpoints(i)...)
    return IA._unsafe_interval(IA.bareinterval(x), IA.decoration(x), false)
end
function IA.interval(::Type{T}, i::IS.Interval) where {T<:IA.NumTypes}
    x = IA.interval(T, IS.endpoints(i)...)
    return IA._unsafe_interval(IA.bareinterval(x), IA.decoration(x), false)
end
Base.convert(::Type{IA.Interval}, i::IS.Interval) = IA.interval(i)
Base.convert(::Type{IA.Interval{T}}, i::IS.Interval) where {T<:IA.NumTypes} = IA.interval(T, i)

# Interval -> IS.Interval
IS.Interval(i::IA.Interval) = IS.Interval(IA.inf(i), IA.sup(i))
# maybe also IS.Interval{T,S,R}(i::IA.Interval) where {T,S,R} = IS.Interval{T,S,R}(IA.inf(i), IA.sup(i))
Base.convert(::Type{IS.Interval}, i::IA.Interval) = IS.Interval(i)
# maybe you want to add a conversion to a more specific signature, eg Base.convert(::Type{T}, i::IA.Interval) where {T<:IS.Interval} = T(i)

[aplavin]

Thanks for looking into it! Updated the code.

[OlivierHnt]

LGTM from my side 👍

@lbenet, @Kolaru how do you feel about this PR?

[Kolaru]

It looks very reasonable to me.

There is just one edge case: IA intervals are always closed, except when one of the bounds is infinity, then the interval is always open on the side of the infinity.

So accordingly, IA.Interval(1, Inf) should convert to IS.Interval{:closed, :open}(1, Inf).

[OlivierHnt]

Indeed. Also this raises the question for NaI and empty intervals; @aplavin do you have a special signature for "empty intervals"?

[aplavin]

So accordingly, IA.Interval(1, Inf) should convert to IS.Interval{:closed, :open}(1, Inf).

Hmm, I guess makes sense, even though it would be type-unstable... What's the best way to implement that? Just check if inf/sup are isfinite?

do you have a special signature for "empty intervals"?

Not really, IS.Interval is fully defined by its endpoints – there are no other flags.

[OlivierHnt]

Yes sadly.

So I am a bit puzzled, with IntervalSets you can construct Interval(2, 1). Is this supposed to be equivalent to Interval(1, 2)?

[aplavin]

Interval(2, 1). Is this supposed to be equivalent to Interval(1, 2)?

No, it's an empty interval – no special casing, just following the regular interval definition:

help?> Interval
search: Interval IntervalSets OpenInterval ClosedInterval AbstractInterval searchsorted_interval InteractiveUtils isinteractive

  An Interval{L,R}(left, right) where L,R are :open or :closed is an interval set containg x such that

    1. left ≤ x ≤ right if L == R == :closed

    2. left < x ≤ right if L == :open and R == :closed

    3. left ≤ x < right if L == :closed and R == :open, or

    4. left < x < right if L == R == :open

Naturally, there's no x such that 2 < x < 1:

julia> 1.5 ∈ Interval(1, 2)
true

julia> 1.5 ∈ Interval(2, 1)
false

julia> isempty(Interval(1, 2))
false

julia> isempty(Interval(2, 1))
true

[OlivierHnt]

Oh ok, for us all empty intervals have the convention that sup(x) == -Inf and inf(x) == Inf.

Mhmm maybe there are multiple ways of handling this; e.g.

IA.interval(i::IS.Interval{L,R,T}) where {L,R,T} = IA.interval(IA.promote_numtype(T, T), i)
function IA.interval(::Type{T}, i::IS.Interval{L,R}) where {T<:IA.NumTypes,L,R}
    lo, hi = IS.endpoints(i)
    isinf(lo) & (L == :closed) && return IA.nai(T) # eg IS.Interval(-Inf, 1) is invalid since closed
    isinf(hi) & (R == :closed) && return IA.nai(T) # eg IS.Interval(1, Inf) is invalid since closed
    L == :open && return IA.nai(T) # eg IS.Interval{:open,:closed}(1, 2) is invalid since not closed
    R == :open && return IA.nai(T) # eg IS.Interval{:closed,:open}(1, 2) is invalid since not closed
    x = IA.interval(T, lo, hi)
    return IA._unsafe_interval(IA.bareinterval(x), IA.decoration(x), false)
end

function IS.Interval(i::IA.Interval)
    lo, hi = IA.bounds(i)
    L = ifelse(isinf(lo), :open, :closed)
    R = ifelse(isinf(hi), :open, :closed)
    return IS.Interval{L,R}(lo, hi)
end

which yield the following behaviour (I let you decide if it is appropriate for IntervalSets.jl)

julia> x = IA.interval(1, 2); y = IA.interval(1, Inf); z = IA.interval(-Inf, Inf); # valid intervals according to IA

julia> IS.Interval(x), IS.Interval(y), IS.Interval(z)
(1.0 .. 2.0, 1.0 .. Inf (closed-open), -Inf .. Inf (open))

julia> u = IA.interval(2, 1); # invalid interval according to IA
┌ Warning: ill-formed interval [a, b] with a = 2, b = 1 and decoration d = com. NaI is returned
└ @ IntervalArithmetic ~/.julia/dev/IntervalArithmetic/src/intervals/construction.jl:444

julia> IS.Interval(u)
NaN .. NaN

julia> v = IA.emptyinterval(); # empty interval according to IA

julia> IS.Interval(v)
Inf .. -Inf (open)

[aplavin]

isinf(lo) & (L == :closed) && return IA.nai(T) # eg IS.Interval(-Inf, 1) is invalid since closed isinf(hi) & (R == :closed) && return IA.nai(T) # eg IS.Interval(1, Inf) is invalid since closed

These would be quite unfortunate, given that :closed intervals are the default in IntervalSets. With these lines, one would be unable to convert common intervals like 0..Inf or -Inf..Inf to IA. Of course, if these checks are crucial, we should add them – but it would definitely reduce convenience, typical infinite intervals would require manual handling from the user side.

Other than that, I fully support your suggested implementation!

[OlivierHnt]

Mhmm yeah. What differs when using IS.Interval{:closed,:open}(1, Inf) vs IS.Interval{:closed,:closed}(1, Inf)? If nothing changes, then maybe we do not need to return an NaI (Not an Interval).

[aplavin]

I think you are right, and the safest approach is to disallow converting 1..Inf (closed intervals with Inf) from IntervalSets to IntervalArithmetics – this ensures semantics is preserved as closely as possible.

[aplavin]

Updated the PR implementation and tests. Tagging @hyrodium in case he has some comments on the conversion.

[aplavin]

Should be ready I guess :) @OlivierHnt

[OlivierHnt]

Sorry I was traveling. Merging now 🙂

[codecov-commenter]

:warning: Please install the to ensure uploads and comments are reliably processed by Codecov.

Codecov Report

All modified and coverable lines are covered by tests :white_check_mark:

Project coverage is 81.20%. Comparing base (7ff253f) to head (63ae171). Report is 7 commits behind head on master.

:exclamation: Your organization needs to install the Codecov GitHub app to enable full functionality.

Additional details and impacted files

@@            Coverage Diff             @@
##           master     #677      +/-   ##
==========================================
+ Coverage   81.02%   81.20%   +0.18%     
==========================================
  Files          27       28       +1     
  Lines        2324     2336      +12     
==========================================
+ Hits         1883     1897      +14     
+ Misses        441      439       -2     

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.