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._______________________________________________
swift-evolution mailing list
[email protected]
https://lists.swift.org/mailman/listinfo/swift-evolution
