> On Apr 17, 2016, at 8:46 AM, plx via swift-evolution
> <[email protected]> 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
>> <[email protected]> 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
>> [email protected]
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>
> _______________________________________________
> swift-evolution mailing list
> [email protected]
> https://lists.swift.org/mailman/listinfo/swift-evolution
_______________________________________________
swift-evolution mailing list
[email protected]
https://lists.swift.org/mailman/listinfo/swift-evolution
