I like the idea. It worries me a bit if the general recipe for such situations is to add dedicated-purpose methods like `_customIndexOfMinComparableElement` (etc.) to standard-library protocols; it *will* work, but is only going to work for the methods that get such treatment.
If it were feasible, I’d *greatly* prefer having some more-general way to (conditionally?) add overridable methods to a protocol, e.g.: // made-up declaration, all declared methods below are now overridable // on suitable types overridable extension Collection where Iterator.Element: Comparable { func min() -> Iterator.Element? } …but am not sure that’s even realistically possible. The reason I bring it up is that I’d hope that `indexOf`, `contains`, and also `upperBound`/`lowerBound` would merit a similar treatment to that proposed here for min, max, and minmax (if not already given such; if they get added to standard-library; etc.). Moving on, wrt these min/max elements themselves: I think any expectation about *which* index gets returned should be document—either no such expectation in general, or a specific expectation, or that each concrete collection should document the expectation, etc.—because for the minIndex/maxIndex methods different approaches can yield different results. EG: consider an order-maintaining collection that has contents ~ `[1,1,1,2,2,2,3,3,3]`. There are multiple candidates for both `minIndex` and `maxIndex`. I don’t have a strong opinion on what the right preference would be here, but I think whatever the behavior winds up being should be at least documented. Finally, FWIW if more of these semi-hidden methods become something exposed to users (as “advanced” options, perhaps, but still) I think replacing `??` with something like enum AdvancedCustomizationPointResult<T> { case NotCustomized // like `nil` for ?? case NoResult // like `Optional(nil)` for ?? case Result(T) // like `Optional(T)` for ?? } …might be worth considering (except with a better name than that). I’m not trying to backdoor optional protocol methods or anything, it just seems advisable to more-explicitly represent the intent (?? certainly works but feels a bit obscure). > On Apr 17, 2016, at 1:44 AM, Nate Cook via swift-evolution > <swift-evolution@swift.org> wrote: > > Hello all, > > Attached is a draft of a proposal to expand the min and max sequence APIs to > better handle collections and to support future sorted sequences/collections. > The proposal is in a gist here > <https://gist.github.com/natecook1000/d51267a6cf9e9463b9387bced4c65b16> and > inlined below—would love to hear any comments or feedback before submitting > the proposal. > > Nate > > > Proposal: Expanded min/max algorithms > This proposal would expand on the min() and max() sequence methods to add > methods that return the corresponding index for a collection, efficiently > find the minimum and maximum elements or indices at the same time, and > provide extension points for sorted collections to provide all these results > more efficiently. > > Related Bugs: SR-889 <https://bugs.swift.org/browse/SR-889> and SR-890 > <https://bugs.swift.org/browse/SR-890> > Motivation > The Sequence protocol currently offers min() and max() methods that return > the minimum and maximum elements of a sequence or collection. Unfortunately, > there are applications where these methods do not provide enough flexibility > to be useful. > > First, if the user of a collection wants not just to get the minimum value > but also to operate on it in some way (e.g., mutation or just accessing it > multiple times), she would need the index of the minimum element. The current > APIs don't support that, so she would need to write her own. > > Second, the writer of a sorted collection is currently unable to provide > efficient responses to the min() and max() methods when used in a generic > context, even though these should be O(1) operations. Just like Set can > respond quickly to contains(_:) even in a generic context, so too should new > sorted collections be able to optimize their responses. > > Finally, getting the minimum and maximum elements (or indices) of a > collection or sequence currently requires calling both min() and max(). With > two calls, every element is iterated and compared twice. When you need both > results, finding both the minimum and the maximum at the same time is more > efficient, requiring only a single pass and 25% fewer comparisons. > > Proposed solution > This proposal has three parts: > > Adding minIndex() and maxIndex() methods to Collection that return the index > of the minimum and maximum elements, respectively. > > let numbers = [30, 40, 10, 20, 60, 50] > > if let i = numbers.minIndex() { > print("\(i): \(numbers[i])") // 2: 10 > } > Adding minmax() and minmaxIndices() methods to Sequence and Collection, > respectively, to calculate the values (or indices) of the minimum and maximum > elements simultaneously. > > if let result = numbers.minmax() { > // result == (minimum: 10, maximum: 60) > // ... > } > if let i = numbers.minmaxIndices() { > // i == (minimum: 2, maximum: 4) > print("\(i.minimum): \(numbers[i.minimum])") > } > Adding customization points for sequences and collections that can offer more > efficient results: > _customMinComparableElement()/_customMaxComparableElement() for Sequence and > _customIndexOfMinComparableElement()/_customIndexOfMaxComparableElement()for > Collection. > > Detailed design > The following methods would be added to the visible public APIs of Sequence > and Collection as default implementations. > > extension Sequence { > /// Returns the minimum and maximum values of `self`, using > /// `isOrderedBefore` to compare elements, or `nil` if the sequence > /// has no elements. > func minmax(@noescape isOrderedBefore isOrderedBefore: > (Iterator.Element, Iterator.Element) throws -> Bool > ) rethrows -> (min: Iterator.Element, max: Iterator.Element)? > } > > extension Sequence where Iterator.Element: Comparable { > /// Returns the minimum and maximum values of `self`, or `nil` > /// if the sequence has no elements. > func minmax() -> (min: Iterator.Element, max: Iterator.Element)? > } > > extension Collection { > /// Returns the index of the minimum element of `self`, using > /// `isOrderedBefore` to compare elements, or `nil` if the > /// collection has no elements. > func minIndex(@noescape isOrderedBefore isOrderedBefore: > (Iterator.Element, Iterator.Element) throws -> Bool > ) rethrows -> Index? > > /// Returns the index of the maximum element of `self`, using > /// `isOrderedBefore` to compare elements, or `nil` if the > /// collection has no elements. > func maxIndex(@noescape isOrderedBefore isOrderedBefore: > (Iterator.Element, Iterator.Element) throws -> Bool > ) rethrows -> Index? > > /// Returns the indices of the minimum and maximum elements of `self`, > /// using `isOrderedBefore` to compare elements, or `nil` if the > /// collection has no elements. > func minmaxIndices(@noescape isOrderedBefore isOrderedBefore: > (Iterator.Element, Iterator.Element) throws -> Bool > ) rethrows -> (minIndex: Index, maxIndex: Index)? > } > > extension Collection where Iterator.Element: Comparable { > /// Returns the index of the minimum element of `self`, or `nil` > /// if the collection has no elements. > func minIndex() -> Index? > > /// Returns the index of the maximum element of `self`, or `nil` > /// if the collection has no elements. > func maxIndex() -> Index? > > /// Returns the indices of the minimum and maximum elements of `self`, > /// or `nil` if the collection has no elements. > func minmaxIndices() -> (minIndex: Index, maxIndex: Index)? > } > The customization points would be added to Sequence and Collection as > protocol requirements, along with default implementations that return nil. > The existing min()and max() methods would be updated to call the > corresponding methods before iterating over the entire sequence. > > protocol Sequence { > // ... > > /// Returns the minimum element as `Optional(element)` or `Optional(nil)` > /// if the sequence has no elements. The uncustomized version returns > /// `nil`. > func _customMinComparableElement() -> Iterator.Element?? > > /// Returns the maximum element as `Optional(element)` or `Optional(nil)` > /// if the sequence has no elements. The uncustomized version returns > /// `nil`. > func _customMaxComparableElement() -> Iterator.Element?? > } > > protocol Collection { > // ... > > /// Returns the index of the minimum element as `Optional(index)` or > /// `Optional(nil)` if the sequence has no elements. The uncustomized > /// version returns `nil`. > func _customIndexOfMinComparableElement() -> Index?? > > /// Returns the index of the maximum element as `Optional(index)` or > /// `Optional(nil)` if the sequence has no elements. The uncustomized > /// version returns `nil`. > func _customIndexOfMaxComparableElement() -> Index?? > } > Minmax Algorithm > > The minmax() algorithm finds the minimum and maximum elements of a sequence > in one pass more efficiently than consecutive calls to min() and max(). This > optimization comes from iterating over a sequence two elements at a time. > > In each iteration, two consecutive elements are compared with each other. > Only the lesser element could be a minimum for the whole sequence, so it is > compared with the current minimum, while only the greater element could be a > maximum, so it is compared with the current maximum. This works out to 3 > comparisons for every 2 elements vs. 2 comparisons for every element when the > minimum and maximum are found individually. > > Impact on existing code > As new APIs these should have no effect on existing code. > > Alternatives considered > None. > > _______________________________________________ > swift-evolution mailing list > swift-evolution@swift.org > https://lists.swift.org/mailman/listinfo/swift-evolution
_______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution