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

[Nate Cook]

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


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

Impact on existing code
The current sorting algorithms would need to be modified to use the new partition(where:) method. 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160706/7773ccb7/attachment.html>