[swift-evolution] [Review] SE-0074: Implementation of Binary Search functions

[Brent Royal-Gordon]

> * Operations that depend on sorted-ness and use binary predicates should
>  not be available on all Collections; they're too easy to misuse,
>  they're hard to name well, and as Nicola Salmoria has noted, they
>  would not make any sense at all for a Set<T>.
> 
> * They should be scoped to a kind of collection that bundles
>  the predicate with the elements, e.g.
> 
>    let x = Sorted([3, 4, 1, 5, 2], >)          // stores a sorted copy of the array
>    let y = Sorted(preSorted: 0..<100, <)  // stores a copy of the range
> 
>  Maybe there should also be protocols for this; CountableRange<T> would
>  already already conform to the immutable version.  We might want a
>  mutable form of the protocol for sorted collections with
>  insertion/removal methods.  This whole area needs more design.

I agree with both of these statements, but not with your conclusion.

There are three classes of collections:

1) Those which are always sorted, like a SortedSet.
2) Those which may or may not be sorted, like an Array.
3) Those which are never sorted, like a Set.

These APIs are useless on a #3, but #2 is still a valuable use case to support. In particular, it's quite common to use sorted `Array`s, and these APIs would help you do that.

What I might consider doing is tying this to `RangeReplaceableCollection`. That protocol is applied only to types which allow insertion at arbitrary indices, which is a good, though not perfect, proxy for types which might allow you to manually maintain a sort order. `Array`, `ArraySlice`, `ContiguousArray`, and the mutable `String` views would get these methods, while `Set` and `Dictionary` would not.

-- 
Brent Royal-Gordon
Architechies