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

[plx]

> On May 9, 2016, at 10:28 PM, Nate Cook via swift-evolution <swift-evolution at swift.org> wrote:
> 
>> On May 9, 2016, at 9:48 PM, Joe Groff via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
>> 
>>> 
>>> On May 9, 2016, at 6:23 PM, Brent Royal-Gordon via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> 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.
>>> 
>>> 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.
>> 
>> We could also introduce a new OrderedCollection protocol. (This would also be useful in the future for supporting `case` pattern matching on collections. It makes sense to pattern-match arrays and other ordered collections in order by element, but you'd expect very different semantics pattern-matching an unordered Set.)

I have some high-level comments about this proposal: it feels rather muddled and as if it's mixing different concerns.

Taking a step back, at a *minimum* I think the right way to add this functionality is to:

A) add generic functions like `binarySearch` (etc.) to `Collection` (taking the GIGO risk, of course)
B) add overridable methods like `sortedIndex(of:)` to `Collection` (taking the GIGO risk again, of course)
C) provide default implementations of e.g. `sortedIndex(of:)` that use `binarySearch` (etc.)

…and *ideally* I think both (A) and probably (B) wind up introducing some methods like `_customBinarySearchForComparableElement` (etc.), but that is a level of detail that can be skipped for this discussion.

I understand the motivation to try and add only “intent-focused” methods like `sortedIndex(of:)`, but a binary search should be expressible generically and is a very useful building block to have when building such higher-level methods; it would also prove useful to *implement* the `Sorted(…)` concept mentioned above, one would think.

I also think it will be a mistake to restrict the availability of any of these APIs to “sorted” collections; there are several reasons here. 

One reason is simply b/c such sorted collections aren’t part of the standard library yet. 

Also, it seems like for *some* of these methods (binarySearch) it’s a category error to restrict them to sorted collections: such sorted collections should instead simply exploit their own ordering/structure where appropriate! 

Finally, things like binary searches are often basic building blocks (etc.) for *constructing* such ordered collections, and thus being unable to use them in that context would be limiting (e.g. if you wanted to implement `Sorted(…)` as suggested above, you’d probably benefit from being able to use these methods…).

Thus although I understand the desire for jumping immediately to the higher-level, "intent-focused” API, and although I understand the GIGO risk for having some of these methods defined too broadly, I am not sure the cures aren't worse than the disease here, so to speak.

>> 
> 
>> -Joe
> 
> Yet another alternative would be to drop Set and Dictionary down a level to a FiniteSequence protocol in between Sequence and Collection. Basically none of the index-based collection APIs (i.e. everything except `count` and `isEmpty`) make sense on sets and dictionaries. index(where:) was marginally useful with dictionaries, but now that Sequence is getting first(where:), née find(...), even that isn't necessary.

I’ve argued this (unsuccessfully) here in the past, but with 2 such distinctions:

- Sequence -> FiniteSequence 
- Sequence -> StableSequence (“stable” meaning identical on each iteration)
- Collection: FiniteSequence, StableSequence

…but it didn’t go well; I can certainly dredge up my design notes if there’s someone else interested in taking up this case.

> 
> Nate
> 
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org <mailto:swift-evolution at swift.org>
> https://lists.swift.org/mailman/listinfo/swift-evolution <https://lists.swift.org/mailman/listinfo/swift-evolution>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160510/aa82c6f9/attachment.html>