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

[Dave Abrahams]

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

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

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

-- 
Dave