Julia: Equality of empty ranges

[sostock]

In order to be equal, ranges need to have the same first element, last element, and step, even if they are empty. Beside being unintuitive, this also breaks the transitivity of ==:

julia> 2:1 == 1:0
false

julia> 2:1 == Int[] == 1:0
true

[nalimilan]

There's likely a historical reason to this: before https://github.com/JuliaLang/julia/pull/16401, arrays and ranges could never be equal, so there was no transitivity issue. We should definitely change that IMHO.

[mschauer]

This is a reasonable change, but it would be at odds with the searchsorted interface, for which the elements of an empty range have a meaning and shouldn't compare equal

julia> searchsorted([1.0,2.0,3.0],2.5)
3:2

julia> searchsorted([1.0,2.0,3.0],2.5) == 2:1
false

[nalimilan]

Yes, that's related to https://github.com/JuliaLang/julia/issues/22354. But I don't think that's a problem here. The result of searchsorted gives you additional information via the start and end values of an empty range, but it's also correct to ignore that information and just say that the value wasn't found.

[nalimilan]

Marking for triage since that would be technically breaking.

[mauro3]

But isn't == supposed to be transitive? If so, this would be a bug.

[StefanKarpinski]

Yes, we can definitely make that case but we still have to consider the consequences. Definitely need discussion in any case.

[StefanKarpinski]

Triage generally feels that these should be made == and isequal. We make things value-equal all the time that have details which differ and this seems no different. Transitivity of equality is more important. Would need a PkgEval run to see what if anything breaks.

[JeffBezanson]

I generally agree with that but searchsorted does kind of throw a monkey wrench into it.

[StefanKarpinski]

I'm a bit hazy on when you would compare the result of searchsorted like that. Can someone thing of realistic example of that kind of usage?

[mschauer]

In interpolation at i = searchsorted(v, x), checking for i == 1:0 or i == n+1:n to special case boundaries seems natural.

[StefanKarpinski]

Right, but when would it be a problem that different empty ranges returned by searchsorted are considered to be equal?

[StefanKarpinski]

It seems like the only way this could be a problem would be if you use searchsorted on two different arrays and want to see if they would insert values at the same location. That seems like a fairly contrived situation. We'll have to run PkgEval on this change and see if it breaks things in practice. If it does we'll have to live with this violation of transitivity until 2.0; if it doesn't we can do it in 1.1.

[StefanKarpinski]

This is a fairly significant change, so it would be good if we got it done sooner rather than later but it's a bit too late for this to happen in 1.1 at this point.

[ti-s]

Should this be changed as well?

julia> 3:3 == 3:2:4
false

julia> 3:3 == [3] == 3:2:4
true

[sostock]

Should this be changed as well?

I think so. I’m kinda surprised that I never noticed that.

[sostock]

I would even say that this should be changed and backported to 1.5, since the behavior in 1.5 is now very confusing. I would consider it a bug.

[rfourquet]

@sostock I agree, could you open an issue so this can be discussed (or a (possibly draft) PR if you feel like) and not forgotten?

[sostock]

Yeah, I will open a PR.

[sostock]

I have opened a PR: #36074