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