on Tue Jul 05 2016, Nate Cook <[email protected]> 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 _______________________________________________ swift-evolution mailing list [email protected] https://lists.swift.org/mailman/listinfo/swift-evolution
