Semantics of non-standard empty intervals

[dmcclean]

Prelude> :m Numeric.Interval
Numeric.Interval> let xs = I 2.0 (-3.0)
Numeric.Interval> width xs
-5.0
Numeric.Interval> midpoint xs
-0.5

Contradicting the bog standard definitions, though there may be alternate definitions with which I am unfamiliar.

I'm not sure if you would prefer to document the existing behavior or add a null case, so I haven't prepared a pull request.

It's also possible that I'm not seeing a reason why the existing behavior is beneficial for some clients, I don't tend to use interval/interval arithmetic much in my applications.

[ekmett]

The problem comes down to how do you do this without analyzing the values involved.

An example where the case based approach is really bad is when you go to such a case analysis based approach is, say, using Interval with accelerate.

There is a definition of interval arithmetic that allows for this symmetric form. They are called "Kaucher intervals" or directed intervals.

I'm open to a more invasive approach, perhaps by splitting Numeric.Interval into two modules, on with the directed/Kaucher semantics and the other with the textbook interval definition, but it isn't a pure win either way.

Regardless, the current behavior should be much better documented though. midpoint and width for example only give sensible results for non-null intervals.

Several other definitions should be updated to reflect this in their description as well.

[dmcclean]

I was thinking about that too, I don't think it can even be done for width with such a general context.

The deeper analysis at issue being (a) requiring an Ord a instance, and (b) requiring that the 0 value from Num a actually obeys the law that, for all x in a, x - x = 0.

width :: Num a => Interval a -> a
width (I a b) = b - a

to

width :: (Ord a, Num a) => Interval a -> a
width i | null i = 0
width (I a b) = b - a

(I'm not familiar with accelerate, but Hoogle points me to a package for getting pipelined things to run on GPUs, is that what you mean? If so I'm glad I asked, because that wasn't even on my radar.)

It might be that my needs are better served by splitting. One option would be to look at the data-interval package (which normalizes empty intervals at construction time, and doesn't export the raw constructor); I originally looked past it because it requires a Num context everywhere and allows open/closed everywhere.

Another option would be to resurrect a prototype I did last year that handles closed/open, infinite, semi-infinite, and cyclic intervals but requires a non-standard class that plays the role of Ord, and a whole bunch of type families; I put it aside because it was too complicated, though it would be nice for a full-blown database language.

[dmcclean]

Here's some interesting work on this topic. http://www.jucs.org/jucs_1_7/on_directed_interval_arithmetic/Markov_S.pdf

(I think) it offers a way to describe "ordinary" interval arithmetic on top of directed interval arithmetic, which might be a useful path to, as you said, "splitting Numeric.Interval into two modules, on with the directed/Kaucher semantics and the other with the textbook interval definition". As far as I can tell, all the intervals arithmetic operations align with these definitions. I can't tell what, if anything, this document says about how the various containment operations are defined for directed intervals. I am also having trouble digging up an answer elsewhere on the internet, except for some seemingly unresolved arguments on the mailing list for a working group working on an IEEE standard for interval arithmetic. I can't follow what's happening in the AERN-Real-Interval package well enough to tell either.

[ekmett]

I'd be okay with repurposing Numeric.Interval to be a proper Interval type, and make Numeric.Interval.Kaucher have the existing directed semantics.

/cc'ing @bergey and @byorgey from diagrams, as they also use Interval at last check, so they can know what is going on.

[byorgey]

Thanks for cc'ing us. We use Interval to properly keep track of precision when doing various approximations, mostly having to do with Bezier curves. If we ever do like we've been threatening for a while and abstract over the numeric types underlying diagrams, I imagine the existing directed semantics which doesn't require ordering checks etc. would be important for us. So as long as that stays around in some form we'd be happy. Having to update some of our code to change imports etc. would be no problem.

[ekmett]

I've started work on 0.4, which does this split.

[ekmett]

Feel free to check my logic, as it was a marathon refactoring session this morning.

[ekmett]

Also, we may want a Numeric.Interval.NonEmpty, which isn't directed, but is never empty with appropriate instances as a middle ground.

[ekmett]

Done.

[dmcclean]

Awesome. Thanks for all the help!

[ekmett]

and vice versa. =)