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

[Karl Wagner]

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