[Draft] Fix the Collection Partition API


(Nate Cook) #1

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.


(Dave Abrahams) #2

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.

···

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

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