Roadmap

[mronian]

@timholy What all functionality would be a good start for this package?

• show
• in
• length
• subset
• . or *, ∩ (intersection)
• +, ∪ (union)
• isequal

Currently doing ClosedSet. For this, if someone does ClosedSet(a, b) where a>b what should be the behaviour?

[timholy]

Looks good. A couple of comments/questions:

• what do you mean by "subset"?
• I would only define ∩ (intersect) and ∪ (union), and not ., *, or +. Those might mean something else to other people.

[mronian]

Subset as in if A belongs to B i.e. ⊆, ⊇, ⊃ et al. :)

[timholy]

Oh, gotcha. That's called issubset (I thought you were talking about making a subset.)

[ararslan]

Regarding ClosedSet... for base ranges, having an upper bound greater than the lower bound results in (the equivalent of) an empty set, but the empty set is both open and closed, so this is kind of a tricky case. Would you have ClosedSet(4, 3) == OpenSet(4, 3)? To me it seems like the best option would be an error.

[mronian]

Do we check for this every time a ClosedSet is created? One of the motivations behind this package was to avoid that. ClosedIntervals.jl does that.

[ararslan]

If you don't check for a > b at all, how would you be able to define any kind of behavior in that scenario?

[timholy]

I would say ClosedSet(a, b) for a>b just returns that literal object, without any checking at construction time. It should return true for isempty, and I agree it should compare equal to empty OpenSets when someone gets around to implementing that type.

I don't think it's a problem that the empty set is both closed and open; we also have the property that ClosedSet(4,3) == ClosedSet(2,-1) as well. This is no different from the following:

julia> isa((), NTuple{0, Int})
true

julia> isa((), NTuple{0, Float64})
true

[timholy]

You only check it when asked to do so, by calling isempty.

[ararslan]

Ah, gotcha. Thanks for the explanation, Tim. That sounds like the best course of action to me.

[timholy]

The fanciest thing the constructor should do is promotion,

ClosedSet(a, b) = ClosedSet(promote(a,b)...)

[simonbyrne]

@dpsanders might be interested in this as well.

[timholy]

I'd also add the .. and ± constructors to the list. Since only one package can productively use those as constructors without conflicts, I'd suggest that for the sake of people who want to implement autoswapping interval mathematics on top of this package, we should export

autoswap{T}(a::T, b::T) = ifelse(a < b, (a, b), (b, a))
autoswap(a, b) = autoswap(promote(a, b)...)

(but of course the constructor doesn't call this, it has to be called manually, ClosedInterval(autoswap(a, b))). It's a good idea to use an explicit promote here because comparison typically involves promotion, and there's no sense in doing it twice.

EDIT: or maybe ordered is a better name.

[dpsanders]

This looks good, but just for the record seems to be duplicating a lot of functionality in ValidatedNumerics.jl.

[simonbyrne]

On that note: what is the purpose of this package?

[timholy]

Background is here and here. The most important points are:

• for some uses you need the ability to create an empty interval in the same way that UnitRange does. Autoswapping is hot death.
• having nice interval constructor operators .. and ± will run into conflicts if multiple packages define them. This argues for a dirt-simple (nearly trivial) package that might serve as the foundation for other packages that add more functionality.
• we definitely don't need all the numerics.

So the idea is that this package just represents a connect set on an ordered domain, and nothing more.

But no objections if people add operations to these sets in other packages.

[simonbyrne]

Thanks, that was useful. Would be good to add that to the README.

[timholy]

To be concrete, the functionality should be similar to the two files intervals.jl and set_operations.jl in ValidatedNumerics, which by lines corresponds to ~6% of ValidatedNumerics.

Aside from having a trivial constructor, there will be small differences:

• support more than Real (anything with a total order should be OK)
• VN's union is equivalent to its hull, but if our model here is set theory then we need to be more strict (see https://github.com/JuliaMath/IntervalSets.jl/pull/2/files#r76705521) or not implement this operation at all.
• similarly, if we implement setdiff, it should just throw an error if the result would be two disjoint intervals.

But other than those, the two look quite compatible. See #2 for a nearly-complete implementation

[dlfivefifty]

I like the idea of a package that just defines the object and set operations, independent of interval arithmetic.

Should this (down the line) be part of a broader set theoretic package? To support, for example, (1..2) ∪ (3..4), OpenIntervals, etc.? I'd be happy to contribute to that (some of which is implemented in ApproxFun but needs to be cleaned up.)

[timholy]

Yes, we've set this up so that open & half-open intervals should also be supportable. Strictly speaking (1..2) ∪ (3..4) isn't an "interval set," but since it is an "intervals set" that could surely fit within the domain of this package. Though I'd be curious to know what practical application needs that.

[dlfivefifty]

I'm not proposing to include additional functionality in this package. Rather, that ClosedInterval{T} <: Set{T} and other packages could implement other sets. In my case, this would be Disk, Circle (embedded in R^2), UnionSet (to represent unions of two arbitrary sets), R, R^2, R^d, etc.

The relevance to this package is that

1. The addition of abstract Set that other packages can create subtypes for.
2. This package would then be a template for standardizing implementation of other sets.

My application: Representing functions on a disjoint union of two sets.

[dlfivefifty]

Here's an example relevant to interval arithmetic:

d=(-1)..1
f = x->sign(x)+x
f(d)  # should be (-2..-1) ∪ (1..2)

[dlfivefifty]

Though probably it should actually be

 ClosedOpenInterval(-2,-1) ∪ ClosedInterval(0,0) ∪ OpenClosedInterval(1,2)

[timholy]

As far as the abstraction goes, see

IntervalSets.jl/src/closed.jl

Line 5 in 9a4d3ea

immutable ClosedInterval{T} <: AbstractInterval{T}

. For simple interval sets, I don't see any reason not to have them here, but things that go beyond could definitely be in other packages. I just submitted JuliaArrays/AxisArrays.jl#36, but AxisArrays still extends the functionality of intervals.

[dlfivefifty]

OK I mean

abstract AbstractInterval{T} <: Set{T}

[dlfivefifty]

And I'm posing this more as a question than a proposal: I need to use more than one type of set, with interval being an important case. Should this use case, where ClosedInterval is one type of set, be taken into account in the design of IntervalSets.jl?

The only action item at the moment would be another layer called Set, but there could be implications in how the union of disjoint intervals is done.

[dpsanders]

@timholy holy For a reasonably sophisticated package that is based on unions of (in general, Cartesian products of) intervals, see IntervalConstraintProgramming.jl. (This is a registered package, but as far as I remember I have not yet announced it, since it is currently undergoing major development.) Something similar is in @zenna's Sigma.jl package.

Basically, the idea is to approximate an arbitrary set, e.g. the feasible set satisfied by a collection of constraints, using a collection of non-overlapping boxes.

On the other hand, I'm not sure how useful such a thing would be in the abstract, without actually being able to calculate things to do with the boxes.

@dlfivefifty I like the idea, but note that the name Set is already taken (unfortunately). Maybe AbstractSet, and it could have a subtype ConnectedSet. Just a reminder that similar ideas were already implemented, also by @zenna, in AbstractDomains.jl.

Finally, I wonder how easy it would be to actually use this underneath e.g. ValidatedNumerics.jl. Would the idea be for that package to just define the arithmetic operations on ClosedIntervals? I am not sure that that will work (but haven't thought about it much).

[dlfivefifty]

@dpsanders raises a good point: you wouldn't want other packages overriding Base commands (such as Base.+) for ClosedInterval, as it could lead to conflicting packages. Perhaps there should be AbstractClosedInterval{T} and then ValidatedNumerics.jl has its own ArithematicInterval{T} <: AbstractClosedInterval{T} which overrides convert(::Type{ArithematicInterval},::ClosedInterval) to convert between the two packages intervals?

AbstractDomains.jl is exactly what I'm thinking of. The question is whether AbstractDomains.Interval should be a subtype of IntervalSets.AbstractInterval, in which case IntervalSets.AbstractInterval would be a subtype of AbstractSet (or Domain, if you prefer the AbstractDomains.jl/ApproxFun.jl terminology.)

[dlfivefifty]

Another source of conflict/redundancy is the notion of a point. I guess ClosedInterval(0.,0.) is meant to represent the point 0?

[dlfivefifty]

@dpsanders I don't think connectedness (ConnectedSet) should be incorporated into the type information, but instead a function isconnected overriden.

A slightly complicated example of why is if there were to be a type SetMinus(bigset,innerset) that represents the set minus operation bigset \ innerset then some SetMinus are connected (e.g., Disk() \ 0.5Disk()) while some are disconnected (e.g., -1..1 \ -0.5..0.5).

[dlfivefifty]

Same logic applies to openness and closedness: isopen and isclosed overrides would be better than abstract types.

[timholy]

I think it would be fine to introduce a layer above. Note that Set is already taken, though:

help?> Set
search: Set setenv setdiff setdiff! setfield! setindex! setrounding setprecision set_rounding set_zero_subnormals set_bigfloat_precision reset IntSet issetuid issetgid insert! InsertionSort

  Set([itr])

  Construct a Set of the values generated by the given iterable object, or an empty set. Should be used instead of IntSet for sparse integer sets, or for sets of arbitrary objects.

[timholy]

When there's really only one reasonable meaning, then extending arithmetic operations on these intervals seems perfectly fine. For example, (1..3) + 2 has a pretty unambiguous meaning. Where it gets into trouble is when there's more than one possible interpretation. For example, the notion of isless in IntervalTrees is OK from the standpoint of introducing a total order on all intervals, but is definitely not what someone doing interval arithmetic might mean (where it would presumably mean "disjointness").

[dlfivefifty]

If it's disambiguous, it should probably be in this package. So for example +(::ClosedInterval{Int},::Integer) could be overridden.

But for floating arithmetic there are multiple possible definitions...

[timholy]

I both agree and disagree. A user who wants to think in terms of pure topology might not want them. We could conceivably have a system like ColorTypes/ColorVectorSpace. Although really there too that was motivated by the ambiguity of arithmetic on colors, so I'm not sure it's an applicable model.

Can you clarify why there are multiple definitions of + with floating point?

[dlfivefifty]

There may be uses for different rounding modes. While the ValidatedNumerics.jl rounding mode with guaranteed containment is probably the only useful one for ClosedInterval, one could imagine cases where you would want the guaranteed containment to go the other way around.

This is more applicable for open intervals, where the open endpoint may indicate a singularity (e.g., the domain that 1/sqrt(x-sqrt(2)) is defined). In this case, you would want to ensure that the open endpoint does not cross the singularity. Or in other words, you want the complement to follow the rules of ValidatedNumerics.jl.

The reason to include the non-ambiguous overrides in this package is that, in 0.5, there will be warnings if multiple packages implement the same functions. A user interested in pure topology can ignore features they don't want to use.

[timholy]

Thanks for the explanation. I see your point.

We could have a common IntervalArithmetic package, but I agree that there may not be strong reason to do that.

[dlfivefifty]

OK I'll make a pull request with the abstract type. I'd propose Domain (as that is the name used in both ApproxFun and AbstractDomains.jl) though AbstractSet is also reasonable, or even just an unexported IntervalSets.Set.

@zenna is AbstractDomains.jl still being developed? If so, I might make a pull request to use IntervalSets and start using it in ApproxFun.

[andyferris]

Is there any appetite to move some of this and particularly the .. operator to Base?

It seems small enough and really useful to me, and I can imagine a lot of packages (in disparate fields/settings) wanting to use the syntax in the future, so it would be good to have a common starting point. (I think part of the productivity of Julia is that all the packages are working together pretty seamlessly).

[dlfivefifty]

I think it's a mistake unless all the appropriate Base overrides are doable, but there is an open question about what to do with union(0..1,2..3).

[andyferris]

Yes, union is tricky.

I guess I meant really bare bones - just .. creates an object that supports in using ordering operators. A separate package could define more operations?

[dlfivefifty]

Except they usually say don't overload functions that only have Base types.

Of course, that policy is likely to be incompatible with the current goal of moving stuff out of Base...

[timholy]

just .. creates an object that supports in using ordering operators. A separate package could define more operations

The intended point of this package is to be that bare-bones package of which you speak, and rampant type-piracy is very much encouraged.

Can you go through the source code and tell me which things seem controversial? Anything that is controversial should be moved out to a separate package.

what to do with union(0..1,2..3)

If you want that to return an AbstractInterval then I think union(0..1, 2..3) should return an error but we could also define boundinginterval(a, b).

[timholy]

Although I guess if you think of the set on which the topology is defined as being Integer rather than Real, then it is a valid operation.

One thought is that we need a second parameter to AbstractInterval defining the "space" on which the topology is constructed, presumably defaulting to Real so that 0.0..1.0 doesn't typically behave differently from 0..1. An alternative is that we should rename this RealIntervalSets.

[dlfivefifty]

If a..b, i.e., ClosedInterval(a,b), is {x : a ≤ x ≤ b} then the only meaning of union(a..b,c..d) would be a type to represent {x : a ≤ x ≤ b or c ≤ x ≤ d}.

[timholy]

But it can't be an IntervalSet, it has to be a different type, e.g., IntervalUnion. If you want it to be type-stable then indeed union(::ClosedInterval, ::ClosedInterval) always has to return a IntervalUnion even when theoretically you could return a single ClosedInterval. Do you really want that?

Probably the best way to make sure that succeeds is to call it as union(IntervalUnion(a), IntervalUnion(b)); that way we can keep the current behavior but also make sure it doesn't throw an error.

[dlfivefifty]

I think union(IntervalUnion(a), IntervalUnion(b)) is reasonable, assuming type stability is desirable.

[timholy]

Yeah, for our use purposes it's vital because we do really compute-intensive stuff involving union and Intervals.

I'd be inclined to say IntervalUnions.jl should be a separate package since this package is intended to be a very minimalistic foundation (really just to "standardize" .. and ±).

[dlfivefifty]

In that case I withdraw my argument for this not being in Base (not that I particularly think it should or shouldn't be.)

[hyrodium]

This issue seems not active and is not focusing on a specific issue, so I'll close this issue.

See #41 for a discussion of union operations.