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

[Brent Royal-Gordon via swift-evolution]

> 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

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

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

[Dave Abrahams via swift-evolution]

on Tue Apr 19 2016, Karl Wagner  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 Cookwrote:
>> 
>> > 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]> 

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

[Karl Wagner via swift-evolution]

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 Cookwrote:
> 
> > 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] 
> 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

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

[Dave Abrahams via swift-evolution]

on Tue Apr 19 2016, "Vladimir.S"  wrote:

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

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

[Vladimir.S via swift-evolution]

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.

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

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

[Dave Abrahams via swift-evolution]

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

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

[Matthew Johnson via swift-evolution]

> On Apr 18, 2016, at 11:08 AM, Dmitri Gribenko  wrote:
> 
> On Sun, Apr 17, 2016 at 11:10 AM, Matthew Johnson via swift-evolution
>  wrote:
>> 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

> 
> Dmitri
> 
> -- 
> main(i,j){for(i=2;;i++){for(j=2;j (j){printf("%d\n",i);}}} /*Dmitri Gribenko */

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

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

[Dmitri Gribenko via swift-evolution]

On Sun, Apr 17, 2016 at 11:10 AM, Matthew Johnson via swift-evolution
 wrote:
> 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.

Dmitri

-- 
main(i,j){for(i=2;;i++){for(j=2;j*/
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

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

[Matthew Johnson via swift-evolution]

> On Apr 17, 2016, at 9:42 AM, Nate Cook via swift-evolution 
>  wrote:
> 
> 
> On Apr 17, 2016, at 8:46 AM, plx via swift-evolution 
> mailto: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
>  
> 
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.  


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

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

[plx via swift-evolution]

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

> On Apr 17, 2016, at 10:03 AM, Patrick Pijnappel  
> 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().

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

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

[Patrick Pijnappel via swift-evolution]

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

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

[Nate Cook via swift-evolution]

> On Apr 17, 2016, at 8:46 AM, plx via swift-evolution 
>  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 {
> 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 
>>  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 s

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

[plx via swift-evolution]

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

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

[Dmitri Gribenko via swift-evolution]

On Sat, Apr 16, 2016 at 11:50 PM, Taras Zakharko via swift-evolution
 wrote:
> Hi Nate,
>
>  I think this is a very useful addition! I also had a related proposal few
> days ago:
> https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20160411/014665.html
>
>  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?

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

Dmitri

-- 
main(i,j){for(i=2;;i++){for(j=2;j*/
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

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

[Taras Zakharko via swift-evolution]

Hi Nate, 

 I think this is a very useful addition! I also had a related proposal few days 
ago: 
https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20160411/014665.html
 

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