Add Range.intersect to the standard library, analogous to NSIntersectionRange

Evolution Pitches
1

Hi there!

This pitch is about adding intersect along the existing overlaps extension of ClosedRange and Range.

Below a working implementation to extend ClosedRange, analogous to NSIntersectionRange:

extension ClosedRange {
    public func intersect(_ other: ClosedRange<Bound>) -> ClosedRange<Bound>? {
        let lowerBoundMax = max(self.lowerBound, other.lowerBound)
        let upperBoundMin = min(self.upperBound, other.upperBound)

        let lowerBeforeUpper = lowerBoundMax <= self.upperBound && lowerBoundMax <= other.upperBound
        let upperBeforeLower = upperBoundMin >= self.lowerBound && upperBoundMin >= other.lowerBound

        if lowerBeforeUpper && upperBeforeLower {
            return lowerBoundMax...upperBoundMin
        }

        return nil
    }
}

Optionally, a suitable operator could be introduced:

precedencegroup SetTheoryPrecendence {
    lowerThan: RangeFormationPrecedence
    higherThan: ComparisonPrecedence
}

infix operator ∩: SetTheoryPrecendence

extension ClosedRange {
    public static func ∩(lhs: ClosedRange, rhs: ClosedRange) -> ClosedRange<Bound>? {
        return lhs.intersect(rhs)
    }
}

For the provided implementation, the following assertions hold true:

assert((1.0...2.0) ∩ (2.0...3.0) == 2.0...2.0)
assert((1.0...3.0) ∩ (2.0...4.0) == 2.0...3.0)
assert((1.0...2.0) ∩ (3.0...4.0) == nil)

Apart from needing this in one of my projects, I'd say it's a useful tool when working with ranges and would like this to be generally available.

Happy to hear your thoughts!

1 Like
2

The Swift name for this operation is named intersection and is part of the protocol SetAlgebra. Operators for operations on sets have already been considered, experimented with, and rejected as impractical. (The proposal to name these operations was one of the most contentious in the first year of Swift Evolution.)

Naming aside, my difficulty with this idea is that, unlike SetAlgebra-conforming types, the operation here must return an optional result because the intersection could be empty, which cannot be represented as a Range. Moreover, in general, because Range types can't represent collections of disjoint intervals, many other SetAlgebra operations are impossible.

Rather than trying to shoehorn in a slightly different set of operations into Range, I wonder if it would be useful to have a RangeSet type (similar in spirit to Foundation.IndexSet) that could actually conform to SetAlgebra. This might be best as an experimental prototype outside the standard library.

5 Likes
3

Thanks for the background information. I'm not too keen on adding the custom operator, I simply used it to illustrate the example a little. It can easily be added in projects to each their own liking.

the operation here must return an optional result because the intersection could be empty

This is indeed the most interesting bit, and also derved a note in the disussion section of NSIntersectionRange:

Discussion

If the returned range’s length field is 0, then the two ranges don’t intersect, and the value of the location field is undefined.

Which I felt was better modeled using an optional instead of exposing undefined values.

I really like your idea about the RangeSet. To implement it in a way that conforms SetAlgebra, it could internally store an array of ranges – that way the union of disjoint ranges can be represented by multiple ranges, the empty range (when intersecting disjoint ranges) can be represented by the array being empty.

4

Why is that the case? Wouldn't ∩, ⊖ , ∪ , ⊆ , other unicode supported set operators make it better because its the actual mathematical notation?

5

They would be…if there were a widespread, easy way to type them, in common use across platforms and hardware.

1 Like
6

However, you are not forced to use the operator. You can still use the verbose notation if it's too hard to type the character on your platform. (E.g. on macOS you can access them rather easily with ⌃⌘Space.)

In my opinion the concerns should be more about how comprehensible they are when reading. Where, in this case, I don't see a problem at all. The interpretation should be intuitive and leaves no ambiguity.

1 Like
7

Regardless, it reduces the barrier to individuals in non-programming backgrounds to understand what the code does while looking more Swifty.

I have the Touch Bar MacBook so all it takes is Apple to add a math notation Touch Bar key in Xcode to pull up the common operators we see in math. Plus, as Pablosichert said, you can do ⌃⌘Space ,

The main benefit I see is the introduction of recognizable mathematical grammars for areas in mathematics. Theoretical math would find its home in Swift.

8

Oh, I totally understand, and am firmly a supporter of unicode operators in Swift. Indeed, I have my own custom-made keyboard layout (shoutout to Ukelele) where…

⌥⇧M puts me in Math mode
⌥⇧L puts me in Logic mode
⌥⇧; puts me in Symbol mode
⌥⇧D puts me in Double-Struck mode
⌥⇧H puts me in Greek mode

…and for convenience × and θ are available without entering any special mode at all.

However, just because something is easy for *me* to type, doesn’t mean it’s easy for everyone. Now, once computer companies start selling keyboards where each keycap is a tiny display, then the story will be different. :-)

3 Likes
9

There is no need to rehash the conversation here. The issue is long settled and you can look up the reasons why by using the search function for this forum, if you’re interested.

3 Likes
10

Hi @PabloSichert :))
Correct me if I'm wrong, but to me, it seems to provide the same functionality that the standard library function ClosedRange method clamped(to:)

1 Like
11

Good find, thanks for the suggestion – that's exactly my use case.

I still think a RangeSet would have a more intuitive API for all set operations, and would like to keep that idea around.

1 Like
12

@PabloSichert have you found any other approaches to finding the intersection between two ranges? If not, I would like to revive this topic.

Adding intersection(_:) along the existing overlaps(_:) could be very helpful.

Currently, we can achieve a similar result using clamped(to:). However, this method returns an empty range when the ranges don't overlap instead of returning nil. I don't believe this to be very intuitive.