[swift-evolution] [Draft] Fix the Collection Partition API

[Dave Abrahams]

on Tue Jul 05 2016, Nate Cook <swift-evolution at swift.org> wrote:

> Hi all,
>
> This is a crack at a proposal to revise the API of the collection
> partition method, called out as an open issue in the standard
> library. What's below is a much shorter revision of a prior proposal,
> focused only on the partition method. I welcome any feedback you might
> have!
>
> Thanks,
> Nate

Overall, a big +1.  Please submit a PR for the proposal to the evolution
repo!

Notes below.

> ––––
> This proposal revises the signature for the collection partition
> algorithm. Partitioning is a foundational API for sorting and for
> searching through sorted collections.
>
> Swift-evolution thread: Feedback from standard library team
> <https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20160502/016729.html>
> Swift Bug: SR-1965 <https://bugs.swift.org/browse/SR-1965>
> Motivation
> Based on feedback during the review of proposal SE-0074,
> Implementation of Binary Search Functions
> <https://github.com/apple/swift-evolution/blob/master/proposals/0074-binary-search.md>
> and the list of open issues affecting standard library API stability
> <https://gist.github.com/gribozavr/37e811f12b27c6365fc88e6f9645634d>,
> this is a revised proposal focused only on the existing collection
> partition method.
>
> The standard library's current partition methods, which partition a
> mutable collection using a binary predicate based on the value of the
> first element of a collection, are used by the standard library's
> sorting algorithm but don't offer more general partitioning
> functionality. A more general partition algorithm using a unary
> (single-argument) predicate would be more flexible and generally
> useful.
>
> Proposed solution
> The standard library should replace the existing partition methods
> with a single method taking a unary predicate. This new method,
> partition(where:), is a mutating method that accepts a unary
> predicate. The elements of the collection are rearranged according to
> the predicate, so that there is a pivot index p where no element
> before p satisfies the predicate and every element at and after p does
> satisfy the predicate.
>
> var n = [30, 40, 20, 30, 30, 60, 10]
> let p = n.partition(where: { $0 > 30 })
> // n == [30, 10, 20, 30, 30, 60, 40]
> // p == 5
> After partitioning, the predicate returns false for every element in
> n.prefix(upTo: p)and true for every element in n.suffix(from: p).
>
> Detailed design
> partition(where:) should be added as a MutableCollection requirement
> with default implementations for mutable and bidirectional mutable
> collections. Any mutable collection can be partitioned, but the
> bidirectional algorithm generally performs far fewer copies. The other
> two methods can be provided in an extension of the Collection
> protocol.
>
> The proposed APIs are collected here:
>
> protocol MutableCollection {
>     // existing requirements
>
>     /// Reorders the elements of the collection such that all the
>     /// elements that match the predicate are ordered after all the
>     /// elements that do not match the predicate.
>     ///
>     /// - Returns: The index of the first element in the reordered
>     ///   collection that matches the predicate.
>     /// - Complexity: O(n)
>     @discardableResult
>     mutating func partition(
>         where predicate: @noescape (Iterator.Element) throws-> Bool
>     ) rethrows -> Index
> }
>
> extension MutableCollection {
>     @discardableResult
>     mutating func partition(
>         where predicate: @noescape (Iterator.Element) throws-> Bool
>     ) rethrows -> Index
> }
>
> extension MutableCollection where Self: BidirectionalCollection {
>     @discardableResult
>     mutating func partition(
>         where predicate: @noescape (Iterator.Element) throws-> Bool
>     ) rethrows -> Index
> }
> A full implementation of the two default implementations can be found
> in this gist
> <https://gist.github.com/natecook1000/70f36608ecd6236552ce0e9f79b98cff>.

IMO we should choose a better parameter name for predicate, such as
`belongsInSecondPartition` or `moveToUpperPartition`.  That will help
guide people to correct usage.

> Impact on existing code
> The current sorting algorithms would need to be modified to use the
> new partition(where:) method. 

Not really; that's an implementation detail.  A super cheap fix would
just underscore the existing APIs.  The “Impact on existing code”
section is really about the impact on clients of the standard library,
not its internals.

> Other uses of the existing partition methods could be flagged or in
> theory could be replaced programmatically. The replacement code, on a
> mutable collection c:
>
> // old
> c.partition()
>
> // new
> if let first = c.first {
>     c.partition(where: { $0 >= first })
> }
> A thorough, though not exhaustive, search of GitHub for the existing
> partition method found no real evidence of its use. The evident uses
> of a partition method were mainly either tests from the Swift project
> or third-party implementations similar to the one proposed.
>
> Alternatives considered
> To more closely match the existing API, the partition(where:) method
> could be added only as a default implementation for mutable
> bidirectional collections. This would unnecessarily limit access to
> the algorithm for mutable forward collections.

-- 
Dave