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 _______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution