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

[Thorsten Seitz]

> Am 10.05.2016 um 04:48 schrieb Joe Groff via swift-evolution <swift-evolution at swift.org>:
> 
>> 
>> On May 9, 2016, at 6:23 PM, Brent Royal-Gordon via swift-evolution <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.)

big +1

Smalltalk has an OrderedCollection which implies that the elements are ordered (though not automatically sorted) and a SortedCollection which maintains a given sort order like the `Sorted` from Dave’s comment. Smalltalk’s Set and Dictionary are just Collections. I always found these useful distinctions.

-Thorsten


> 
> -Joe
> _______________________________________________
> 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/87d93f09/attachment.html>