[swift-evolution] [Draft] Expanded min/max algorithms

[Dave Abrahams]

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