[Draft] Expanded min/max algorithms

nnnnnnnn · 2016-04-17T06:44:09.000Z

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 <Issues · apple/swift-issues · GitHub; and SR-890 <Issues · apple/swift-issues · GitHub;
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.

plx · 2016-04-17T13:46:21.000Z

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 <Issues · apple/swift-issues · GitHub; and SR-890 <Issues · apple/swift-issues · GitHub;
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

Taras_Zakharko1 · 2016-04-17T06:50:52.000Z

Hi Nate,

I think this is a very useful addition! I also had a related proposal few days ago: [swift-evolution] [Proposal] Add .order() family of methods to Collection

I feel like min/max extension and element order belong to the same family of enhancements. If you are interested, maybe we can combine them together into a single proposal?

Best,

Taras

···

On 17 Apr 2016, at 08:44, 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 <Issues · apple/swift-issues · GitHub; and SR-890 <Issues · apple/swift-issues · GitHub;
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

dabrahams · 2016-04-19T18:12:04.000Z

Just with regard to naming, I don't think these work. I read “minIndex”
as “the minimum index,” and since we expect all indices to be
comparable, that clearly implies c.minIndex() == c.startIndex. I think
you'd need “c.indexOfMin()”

I am also really reluctant to add specialized algorithms for things
that can be trivially composed out of existing parts, e.g.

c.indices.min { c[$0] < c[$1] }

Once we start down this road, we very quickly end up with mapValues,
mapKeys, indexOfMinimumKey, etc.

···

on Sat Apr 16 2016, Nate Cook <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:

1 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
}

--
Dave

Karl · 2016-04-19T23:50:43.000Z

Maybe this has been addressed before on another topic, but why are minmax(), minIndex(), maxIndex() and minmaxIndices() functions rather than read-only properties? It seems like things would be much cleaner without the brackets, and it’s shorter to implement in some cases as you can back it with a stored property for caching. As functions, you'd need to write separate getters.

e.g.

struct Blah<T:Comparable> : Collection
{
var minIndex : Index?
var maxIndex : Index?

    func insertElement(element: T)
    {
        // insert element
        // compare with elements at stored minIndex, maxIndex
        // update minIndex/maxIndex if necessary
    }
}

Also, I’d favour “bounds”, “boundaries” or “limits” over minmax. There are plenty of English words which better and more precisely describe what it provides.

Karl

···

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<Issues · apple/swift-issues · GitHub SR-890<Issues · apple/swift-issues · GitHub;
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.

gribozavr · 2016-04-17T06:54:40.000Z

Thanks Nate and Taras! I'd recommend to keep minmax and .order()
proposals separate.

Dmitri

···

On Sat, Apr 16, 2016 at 11:50 PM, Taras Zakharko via swift-evolution <swift-evolution@swift.org> wrote:

Hi Nate,

I think this is a very useful addition! I also had a related proposal few
days ago:
[swift-evolution] [Proposal] Add .order() family of methods to Collection

I feel like min/max extension and element order belong to the same family
of enhancements. If you are interested, maybe we can combine them together
into a single proposal?

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/

nnnnnnnn · 2016-04-17T14:42:14.000Z

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:

github.com

apple/swift/blob/main/stdlib/public/core/Sequence.swift#L190


      
          
          /// Advances to the next element and returns it, or `nil` if no next element
          /// exists.
          ///
          /// Repeatedly calling this method returns, in order, all the elements of the
          /// underlying sequence. As soon as the sequence has run out of elements, all
          /// subsequent calls return `nil`.
          ///
          /// You must not call this method if any other copy of this iterator has been
          /// advanced with a call to its `next()` method.
          ///
          /// The following example shows how an iterator can be used explicitly to
          /// emulate a `for`-`in` loop. First, retrieve a sequence's iterator, and
          /// then call the iterator's `next()` method until it returns `nil`.
          ///
          ///     let numbers = [2, 3, 5, 7]
          ///     var numbersIterator = numbers.makeIterator()
          ///
          ///     while let num = numbersIterator.next() {
          ///         print(num)
          ///     }

github.com

apple/swift/blob/main/stdlib/public/core/Collection.swift#L184


      
          ///     print(firstChar)
          ///     // Prints "B"
          ///
          /// The `Collection` protocol declares and provides default implementations for
          /// many operations that depend on elements being accessible by their
          /// subscript. For example, you can also access the first character of `text`
          /// using the `first` property, which has the value of the first element of
          /// the collection, or `nil` if the collection is empty.
          ///
          ///     print(text.first)
          ///     // Prints "Optional("B")"
          ///
          /// You can pass only valid indices to collection operations. You can find a
          /// complete set of a collection's valid indices by starting with the
          /// collection's `startIndex` property and finding every successor up to, and
          /// including, the `endIndex` property. All other values of the `Index` type,
          /// such as the `startIndex` property of a different collection, are invalid
          /// indices for this collection.
          ///
          /// Saved indices may become invalid as a result of mutating operations. For
          /// more information about index invalidation in mutable collections, see the

···

On Apr 17, 2016, at 8:46 AM, plx via swift-evolution <swift-evolution@swift.org> wrote:

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

VladimirS · 2016-04-19T19:52:59.000Z

Agree with notes about minIndex vs indexOfMin. Seems clear for me the later should be chosen. We have .min() so it is naturally to have .indexOfMin

But I disagree on specialized algorithms. Can't understand, how custom-made function with block with comparision is better than handful, clear and explicit method. Btw, I feel your "composition" is not obvious on what is going on from first look and if instance name is somethingDescriptive you'll have very long expression instead of method with clear name and obvious meaning.

What is wrong to have a set of useful and explicit methods for basic operations on array, map, set etc?

···

On 19.04.2016 21:12, Dave Abrahams via swift-evolution wrote:

Just with regard to naming, I don't think these work. I read “minIndex”
as “the minimum index,” and since we expect all indices to be
comparable, that clearly implies c.minIndex() == c.startIndex. I think
you'd need “c.indexOfMin()”

I am also really reluctant to add specialized algorithms for things
that can be trivially composed out of existing parts, e.g.

c.indices.min { c[$0] < c[$1] }

Once we start down this road, we very quickly end up with mapValues,
mapKeys, indexOfMinimumKey, etc.

Brent_Royal-Gordon · 2016-04-20T08:14:43.000Z

Maybe this has been addressed before on another topic, but why are minmax(), minIndex(), maxIndex() and minmaxIndices() functions rather than read-only properties?

The API Guidelines say this:

Document the complexity of any computed property that is not O(1). People often assume that property access involves no significant computation, because they have stored properties as a mental model. Be sure to alert them when that assumption may be violated.

It's not stated outright, but that also sort of implies that you should generally prefer to make a non-O(1) operation a method, not a property. There are lots of borderline cases—`count` is O(n) for the general case of a Sequence or Collection, but it's O(1) for many of the most common types like Array, so it's made a property even though that might be confusing. Very few types would have O(1) `min/maxIndex`, so it doesn't seem appropriate to use methods.

Also, non-`Comparable` collections would need a form which takes a comparison function as a parameter. That means method.

Also, I’d favour “bounds”, “boundaries” or “limits” over minmax. There are plenty of English words which better and more precisely describe what it provides.

These all sound like words for the `start/endIndex`. That's a problem with this proposal more generally; I'm not really in favor.

(I wonder if instead, there should be an operation like reduce(_:combine:) but with a function parameter which returns a Bool, and which ends up returning the last element which the function returned true for.)

···

--
Brent Royal-Gordon
Architechies

Karl · 2016-04-20T00:12:58.000Z

I understand what you’re saying about API bloat, but I still think this is a fair proposal:

1. It’s not a very outlandish thing. We already have min/max. Adding a function for the mean would probably be too much. Collection is a bit of a special API; it should be reasonably comprehensive to allow developers to keep working at the most abstract level possible, but you’re right, of course, that there must be limits.

2. Many complex collections will probably decide to cache their min/max indexes and invalidate them on insertion/removal. With this API, we could grab those indexes from a stored property; without it, we’d have to get the min/max elements (which internally will probably just look up those cached indexes) and work backwards to find the indexes. I’d rather remove min() and max() and replace them with collection[collection.indexOfMaxElement].

As far as naming goes, you’re right. “minIndex" and “maxIndex" are far too similar to “startIndex" and “endIndex”.

Karl

···

on Sat Apr 16 2016, Nate Cook<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:
>
> 1 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
> }
Just with regard to naming, I don't think these work. I read “minIndex”
as “the minimum index,” and since we expect all indices to be
comparable, that clearly implies c.minIndex() == c.startIndex. I think
you'd need “c.indexOfMin()”

I am also really reluctant to add specialized algorithms for things
that can be trivially composed out of existing parts, e.g.

c.indices.min { c[$0]<c[$1] }

Once we start down this road, we very quickly end up with mapValues,
mapKeys, indexOfMinimumKey, etc.

--
Dave

anandabits · 2016-04-17T18:10:09.000Z

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

I thought the _ prefix meant “internal to stdlib”. Are the existing extension points intended to be exposed as part of the public interface? Or are they just intended to be implementation details of the library which are implemented by some of the stdlib types? If they are implementation details they are probably not a good model for public interfaces.

These extension points are effectively “optional protocol requirements”. There has been a lengthy thread about those, with much discussion around Cocoa protocols such as UITableView using lack of customization to take a fast path implementation. Your extension points essentially do the opposite - implementing them means there is a custom fast path that can be taken, rather than a complex custom layout that defeats the standard fast path.

Despite the differences the impact on the design of the protocol is quite similar. I think this is a good opportunity to agree on the most Swifty way to handle this kind of customization point (i.e. “optional” requirement with a default implementation). Some of the ideas discussed in the other thread would require language tweaks if we go with them.

I think the “optional requirement” issue should be sorted out first and this proposal updated accordingly before proceeding with a review.

···

On Apr 17, 2016, at 9:42 AM, Nate Cook via swift-evolution <swift-evolution@swift.org> wrote:
On Apr 17, 2016, at 8:46 AM, plx via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

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 <mailto: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 <Issues · apple/swift-issues · GitHub; and SR-890 <Issues · apple/swift-issues · GitHub;
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 <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

Patrick_Pijnappel · 2016-04-17T15:03:27.000Z

I like the idea. A few notes on naming:
– minIndex is somewhat confusing to me (it sounds like it's getting the
minimum index, i.e. indices.minElement()). How about indexOfMin() or
indexOfMinElement()?
– minmax() also doesn't read very well to me, plus it should technically be
minMax() which is kinda ugly. Perhaps limits() or extrema()? The latter
would be the most correct mathematically. For the index form that would
give e.g. indicesOfExtrema().

···

On Sun, Apr 17, 2016 at 4:42 PM, Nate Cook via swift-evolution < swift-evolution@swift.org> wrote:

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
<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 <Issues · apple/swift-issues · GitHub; and SR-890
<Issues · apple/swift-issues · GitHub;
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:

   1.

   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}

   2.

   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])")}

   3.

   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

dabrahams · 2016-04-19T22:51:52.000Z

Agree with notes about minIndex vs indexOfMin. Seems clear for me the
later should be chosen. We have .min() so it is naturally to have
.indexOfMin

But I disagree on specialized algorithms. Can't understand, how
custom-made function with block with comparision is better than
handful, clear and explicit method.

It's important, as a baseline, for the library to provide all the right
primitives that you can combine to easily get most jobs done. After
that, the bar for expanding the API surface area gets much higher,
because greater API surface area means more complexity for users to
confront. The usual criterion is, “is it hard to write (correctly and
performantly) yourself?” I think this one fails that test.

Btw, I feel your "composition" is not obvious on what is going on from
first look and if instance name is somethingDescriptive you'll have
very long expression instead of method with clear name and obvious
meaning.

What is wrong to have a set of useful and explicit methods for basic
operations on array, map, set etc?

Nothing at all, but there's a balance to be maintained between design
coherence, graspability of the whole API, convenience, and many other
factors.

···

on Tue Apr 19 2016, "Vladimir.S" <svabox-AT-gmail.com> wrote:

On 19.04.2016 21:12, Dave Abrahams via swift-evolution wrote:

Just with regard to naming, I don't think these work. I read “minIndex”
as “the minimum index,” and since we expect all indices to be
comparable, that clearly implies c.minIndex() == c.startIndex. I think
you'd need “c.indexOfMin()”

I am also really reluctant to add specialized algorithms for things
that can be trivially composed out of existing parts, e.g.

c.indices.min { c[$0] < c[$1] }

Once we start down this road, we very quickly end up with mapValues,
mapKeys, indexOfMinimumKey, etc.

--
Dave

dabrahams · 2016-04-20T01:07:54.000Z

I understand what you’re saying about API bloat, but I still think this is a fair proposal:

1. It’s not a very outlandish thing.

No, of course it isn't. That doesn't mean we should add it, either.

Note: I'm not predisposed against these particular algorithms; not at
all. At the same time, I want to be sure we understand why each
algorithm we add is being added, and where the limits are.

We already have min/max. Adding a function for the mean would probably
be too much. Collection is a bit of a special API; it should be
reasonably comprehensive to allow developers to keep working at the
most abstract level possible, but you’re right, of course, that there
must be limits.

2. Many complex collections will probably decide to cache their
min/max indexes and invalidate them on insertion/removal.

Many? I've never heard of a general purpose data structure that did
this, (other than sorted collections, which sort of need to do it by
definition, in order to produce startIndex and endIndex).

With this API, we could grab those indexes from a stored property;
without it, we’d have to get the min/max elements (which internally
will probably just look up those cached indexes) and work backwards to
find the indexes.

Only in generic code that doesn't know it's handling this particular
collection. The concrete collection is free to expose whatever it wants
to.

I’d rather remove min() and max() and replace them with
collection[collection.indexOfMaxElement].

That is certainly an interesting direction to consider. One might say
that no standard library algorithm should ever return an element of the
collection unless it is being removed; instead we should always and only
return an index to the element.

···

on Tue Apr 19 2016, Karl Wagner <swift-evolution@swift.org> wrote:

As far as naming goes, you’re right. “minIndex" and “maxIndex" are far
too similar to “startIndex" and “endIndex”.

Karl

on Sat Apr 16 2016, Nate Cook<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:
>
> 1 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
> }
Just with regard to naming, I don't think these work. I read “minIndex”
as “the minimum index,” and since we expect all indices to be
comparable, that clearly implies c.minIndex() == c.startIndex. I think
you'd need “c.indexOfMin()”

I am also really reluctant to add specialized algorithms for things
that can be trivially composed out of existing parts, e.g.

c.indices.min { c[$0]<c[$1] }

Once we start down this road, we very quickly end up with mapValues,
mapKeys, indexOfMinimumKey, etc.

--
Dave

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

--
Dave

plx · 2016-04-17T15:09:47.000Z

I *quite* like `extrema`/`indicesOfExtrema` over minmax.

···

On Apr 17, 2016, at 10:03 AM, Patrick Pijnappel <patrickpijnappel@gmail.com> wrote:

I like the idea. A few notes on naming:
– minIndex is somewhat confusing to me (it sounds like it's getting the minimum index, i.e. indices.minElement()). How about indexOfMin() or indexOfMinElement()?
– minmax() also doesn't read very well to me, plus it should technically be minMax() which is kinda ugly. Perhaps limits() or extrema()? The latter would be the most correct mathematically. For the index form that would give e.g. indicesOfExtrema().

gribozavr · 2016-04-18T16:08:36.000Z

I'm sorry, but they are not optional requirements. They are
workarounds for a language issue -- inability to make
conditionally-available methods customizable by a conforming type.

Dmitri

···

On Sun, Apr 17, 2016 at 11:10 AM, Matthew Johnson via swift-evolution <swift-evolution@swift.org> wrote:

These extension points are effectively “optional protocol requirements”.

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/

anandabits · 2016-04-18T19:29:34.000Z

These extension points are effectively “optional protocol requirements”.

I'm sorry, but they are not optional requirements. They are
workarounds for a language issue -- inability to make
conditionally-available methods customizable by a conforming type.

I understand that they are not optional requirements as they exist in the language today. What I meant is that the approach these extension points are taking is effectively the same as one of the approaches discussed in the "How to eliminate 'optional' protocol requirements” thread.

I am referring to the first option in Doug’s initial message: https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20160404/014471.html\. Doug considered this unworkable but Joe considers the reasons Doug called it unworkable to be missing language features that should exist anyway: https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20160411/014696.html\. There has not yet been a resolution on this issue.

The primary difference between that approach and your extension points is that you add and extra level of optionality to the value returned whereas the approach in that thread has an optional closure property. Both approaches use a default implementation of “return nil” to indicate that there is no customization requested by the implementer.

In your proposal the extension points look like this:

func _customMinComparableElement() -> Iterator.Element??

Translating to the option Doug presented they would look like this:

var _customMinComparableElement: (() -> Iterator.Element?)? { get }

In either case a default implementation that returns nil would be provided. Under Doug’s model where methods can be used to implement such requirements, implementers would provide a method like this:

func _customMinComparableElement() -> Iterator.Element?

I hope I have clarified how I believe these extension points are related to the thread about removing optional protocol requirements from the language. My opinion is that if we are going to remove them and import them from Objective-C in a more Swifty way by embedding the optionality in the type system that same mechanism should be used by any extension points which behave similarly.

Matthew

···

On Apr 18, 2016, at 11:08 AM, Dmitri Gribenko <gribozavr@gmail.com> wrote:
On Sun, Apr 17, 2016 at 11:10 AM, Matthew Johnson via swift-evolution > <swift-evolution@swift.org> wrote:

Dmitri

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/