[SR-888] Sequence.minElement() and maxElement() should be protocol requirements (customization points)

[gribozavr]

Previous ID	SR-888
Radar	rdar://problem/24999603
Original Reporter	@gribozavr
Type	Bug
Status	In Progress
Resolution

Additional Detail from JIRA

Votes	0
Component/s	Standard Library
Labels	Bug, AffectsABI, StarterBug, StarterProposal, swift-evolution-proposal-needed
Assignee	akhilmantha (JIRA)
Priority	Medium

md5: 38f233c0b4c0d1508b74875d0c159d05

Issue Description:

Some collections naturally maintain sorted order and can implement `minElement()` and `maxElement()` in O(1). Thus, these algorithms should be protocol requirements to allow collection-specific customizations.

Note that `minElement()` and `maxElement()` that take predicates should continue to be pure extensions.

[natecook1000]

How does a collection satisfy a minElement() requirement in the general case? Making the predicate version required would let the no-argument version be provided as an extension for comparable elements that simply calls the required method with <.

[gribozavr]

> How does a collection satisfy a minElement() requirement in the general case?

With a default implementation that compares elements one by one.

> Making the predicate version required

That version would be a pure extension, and wouldn't allow customization, since no customization can be faster than the default.

[natecook1000]

I guess I'm asking what an Array<UIImage> would return for this? Would it simply be undefined for sequences of elements that aren't Comparable, like `first` for unordered collections?

[gribozavr]

Right, the no-arg method will only be defined for collections of comparable elements.

[belkadan]

I'm not super happy with us continuing to add customization points willy-nilly. These have a definite code size cost, and we should start taking that into account or come up with an alternate implementation.