[swift-evolution] [Review] SE-0074: Implementation of Binary Search functions
Dave Abrahams
dabrahams at apple.com
Tue May 17 18:30:42 CDT 2016
on Fri May 13 2016, Joe Groff <swift-evolution at swift.org> wrote:
>> On May 13, 2016, at 7:30 AM, Dave Abrahams <dabrahams at apple.com> wrote:
>>
>>
>> on Mon May 09 2016, Joe Groff <jgroff-AT-apple.com> wrote:
>>
>
>>>> 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.)
>>
>> What do you mean by “Ordered” here? Please note that when Cocoa uses
>> “Ordered” it means something very different from “Sorted.” I don't find
>> the Cocoa usage intuitive myself, but it might be best to avoid that
>> term to avoid confusion.
>
> By "ordered", I only mean "ordering is significant to the value of the
> collection", so Array is ordered but Set is not.
That does not strike me as a useful-enough distinction to be worth
enshrining in a protocol. What generic components would be constrained
on it?
--
-Dave
More information about the swift-evolution
mailing list