> On Apr 17, 2016, at 8:46 AM, plx via swift-evolution > <swift-evolution@swift.org> wrote: > > 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.
Agreed! I'm not sure if that's part of the generics manifesto or not, but it'd be great to have conditionally applied dynamically dispatched methods for cases like this. > 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.). The customization points in the proposal are modeled after the two existing ones in the standard library for `contains` and `index(of:)`. You can see them here: https://github.com/apple/swift/blob/master/stdlib/public/core/Sequence.swift#L190 https://github.com/apple/swift/blob/master/stdlib/public/core/Collection.swift#L184 > 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 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 and 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
_______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution