Sorted Collection Protocol

Evolution Pitches
7

Thanks for starting up this topic, @Letan! This is a bit of a hole in the standard library, and we haven't had a good answer yet. There was a proposal that was rejected about two years ago—the response from the standard library team at the time is particularly useful to read, and the rest of the thread also has a good discussion that would be helpful to catch up on: [Review] SE-0074: Implementation of Binary Search functions - #5 by dabrahams

In my exploration of the topic after that proposal, I've found that it helps if the protocol you start with only has a requirement that lets you maintain the order of the elements. That is, SortedCollection might look like this:

protocol SortedCollection: Collection {
  /// An ordering for all elements in the collection.
  var areInIncreasingOrder: (Element, Element) -> Bool { get }
}

This way Range and ClosedRange can conform right out of the gate, and ReversedCollection can even conditionally conform.

extension Range: SortedCollection 
    where Bound: Strideable, Bound.Stride: SignedInteger {
  var areInIncreasingOrder: (Element, Element) -> Bool { 
    return (<)
  }
}

Then we want to fill in what operations make sense to do on an immutable sorted collection, before we move on to sorted collections that can have elements inserted and removed. A binary search could be provided as an implementation detail, and maybe an insertionPoint(for element: Element) -> Index method, as a way of finding where an element would go if it were to be added.

On mutation, it does seem like there's room for a RangeRemoveableCollection protocol for types that can remove groups of elements. Along with sorted collections, Set and Dictionary could even conform to that protocol, which would go in between Collection and RangeReplaceableCollection.

In general, it's difficult to design the protocols for something like this without implementing the concrete types that would conform to them. I'd strongly suggest starting there, and then finding the abstractions that make sense.

7 Likes