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

[Dave Abrahams]

on Mon May 09 2016, Brent Royal-Gordon <brent-AT-architechies.com> wrote:

>> * 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.

Sorted<Array<T>> would help you do that even more :-)

> 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.

That's interesting, but I don't understand why it's better than having
Sorted.

IME it's very rare to have a collection that's transiently sorted and
thus appropriate for a binary search.  You may start out un-sorted, but
after a bit you're maintaining sorted order.  It makes sense to reflect
that in the type system.

-- 
-Dave