Folks are focusing on Swift 3 and non-critical additive things aren't going to get attention. It is best to avoid discussion of non-critical additive proposals until the focus returns to future looking (e.g post Swift 3). On Thu, Jul 7, 2016 at 1:48 PM Daryle Walker via swift-evolution < [email protected]> wrote:
> I doesn’t seem that anyone noticed the previous post. Here’s an inline > copy: > > Implement a mismatch algorithm, equivalent to std::mismatch() in C++ > > - Proposal: SE-NNNN > <https://gist.github.com/CTMacUser/NNNN-filename.md> > - Author: Daryle Walker <https://github.com/CTMacUser> > - Status: Awaiting review > - Review manager: TBD > > > <https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc#introduction> > Introduction > > This proposal is to add difference detection to Swift's standard library > collections. > > Swift-evolution thread: Discussion thread topic for that proposal > <http://news.gmane.org/gmane.comp.lang.swift.evolution> > > <https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc#motivation> > Motivation > > Finding where two similar collections differ is needed in algorithms that > have different policies on handling the common part versus the uncommon > parts. Similar tests already exist in the standard library: the > elementsEqual methods in Sequence for instance; the methods can indicate > two sequences are different but not where they diverged. Flipping it > around, it means that sequence equivalence, and several other sequence > methods, can be expressed in terms of mismatch-finding. However, returning > the divergence point means returning references to the diverging elements, > which means an index, which means that collections are required instead of > plain sequences. > > <https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc#proposed-solution>Proposed > solution > > The Swift standard library should provide generic implementations of the > "mismatch" algorithm for forward searches on prefixes and backward searches > on suffixes. The forward/prefix form is called diverges(from: > isEquivalent:). The backward/suffix form is called converges(with: > isEquivalent:), and is present only when the collection type supports > bidirectional indexing. If the collection's element type conforms to > Equatable, there variants of the method(s) that drop the second argument > and instead use == for the equivalency test. > > <https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc#detailed-design>Detailed > design > <https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc#divergesfromisequivalent-and-divergesfrom> > diverges(from:isEquivalent:) and diverges(from:) > > Forward mismatching on prefixes will be added to the Collection protocol > requirements with a default implementation. Its variant will extend > Collection with a default implementation. These methods will have the > following declarations: > > protocol Collection { > // existing declarations > > /** Compares the collection against a given collection > element-wise until either corresponding elements are no longer equivalent, > using the given predicate as the equivalence test, or at least one collection > reaches its end index. The predicate must be an equivalence relation > over the elements. - parameter from: A collection to compare to this > one. - parameter isEquivalent: A predicate the returns `true` if and > only if its two arguments are equivalent. - returns: A pair of > indices, indicating where the two collections mismatched. The first member > is the index of the element that mismatched in this collection, the second is > the index of the element that mismatched in the given collection. If the > testing stopped because the collections were of different lengths, but were > equivalent until that point, then exactly one member of the tuple will be at > its collection's end index. If both tuple members are at their respective > collection's end index, then the collections were equivalent. - > complexity: `min(count, from.count)` comparisons. - throws: Whatever > `isEquivalent` may throw. */ > func diverges<PossiblePrefix: Collection where > PossiblePrefix.Iterator.Element == Iterator.Element>(from possiblePrefix: > PossiblePrefix, isEquivalent: (Iterator.Element, Iterator.Element) throws -> > Bool) rethrows -> (Index, PossiblePrefix.Index) > } > extension Collection { > /** Compares the collection against a given collection > element-wise until either corresponding elements are no longer equivalent, > using the given predicate as the equivalence test, or at least one collection > reaches its end index. The predicate must be an equivalence relation > over the elements. - parameter from: A collection to compare to this > one. - parameter isEquivalent: A predicate the returns `true` if and > only if its two arguments are equivalent. - returns: A pair of > indices, indicating where the two collections mismatched. The first member > is the index of the element that mismatched in this collection, the second is > the index of the element that mismatched in the given collection. If the > testing stopped because the collections were of different lengths, but were > equivalent until that point, then exactly one member of the tuple will be at > its collection's end index. If both tuple members are at their respective > collection's end index, then the collections were equivalent. - > complexity: `min(count, from.count)` comparisons. - throws: Whatever > `isEquivalent` may throw. */ > func diverges<PossiblePrefix: Collection where > PossiblePrefix.Iterator.Element == Iterator.Element>(from possiblePrefix: > PossiblePrefix, isEquivalent: (Iterator.Element, Iterator.Element) throws -> > Bool) rethrows -> (Index, PossiblePrefix.Index) > } > extension Collection where Iterator.Element: Equatable { > /** Compares the collection against a given collection > element-wise until either corresponding elements are no longer equal, or at > least one collection reaches its end index. - parameter from: A > collection to compare to this one. - returns: A pair of indices, > indicating where the two collections mismatched. The first member is the > index of the element that mismatched in this collection, the second is the > index of the element that mismatched in the given collection. If the testing > stopped because the collections were of different lengths, but were equal > until that point, then exactly one member of the tuple will be at its > collection's end index. If both tuple members are at their respective > collection's end index, then the collections were equal. - complexity: > `min(count, from.count)` comparisons. */ > func diverges<PossiblePrefix: Collection where > PossiblePrefix.Iterator.Element == Iterator.Element>(from possiblePrefix: > PossiblePrefix) -> (Index, PossiblePrefix.Index) > } > > I don't know if we should insist that at least one (or both) of the > collections tested should be finite. I don't know if the results should be > discardable. > > <https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc#convergeswithisequivalent-and-convergeswith> > converges(with:isEquivalent:) and converges(with:) > > Backward mismatching on suffixes will be added to the > BidirectionalCollection protocol requirements with a default > implementation. Its variant will extend BidirectionalCollection with a > default implementation. These methods will have the following declarations: > > protocol BidirectionalCollection { > // existing declarations > > /** Compares the collection against a given collection > element-wise and backwards until either corresponding elements are no longer > equivalent, using the given predicate as the equivalence test, or at least > one collection reaches its start index. Both collections must be > finite. The predicate must be an equivalence relation over the > elements. - parameter with: A collection to compare to this one. > - parameter isEquivalent: A predicate the returns `true` if and only if its > two arguments are equivalent. - returns: A pair of indices, indicating > where the two collections started to match. The first member is the index of > the element that suffix-matched in this collection, the second is the index > of the element that suffix-matched in the given collection. If the testing > stopped because the collections were of different lengths, but were > equivalent until that point, then exactly one member of the tuple will be at > its collection's start index. If both tuple members are at their respective > collection's start index, then the collections were equivalent. If both > tuple members are at their respective collection's end index, then either the > collections' last elements differ or at least one collection was empty. > - complexity: `min(count, from.count)` comparisons. - throws: > Whatever `isEquivalent` may throw. */ > func converges<PossibleSuffix: BidirectionalCollection where > PossibleSuffix.Iterator.Element == Iterator.Element>(with possibleSuffix: > PossibleSuffix, isEquivalent: (Iterator.Element, Iterator.Element) throws -> > Bool) rethrows -> (Index, PossibleSuffix.Index) > } > extension BidirectionalCollection { > /** Compares the collection against a given collection > element-wise and backwards until either corresponding elements are no longer > equivalent, using the given predicate as the equivalence test, or at least > one collection reaches its start index. Both collections must be > finite. The predicate must be an equivalence relation over the > elements. - parameter with: A collection to compare to this one. > - parameter isEquivalent: A predicate the returns `true` if and only if its > two arguments are equivalent. - returns: A pair of indices, indicating > where the two collections started to match. The first member is the index of > the element that suffix-matched in this collection, the second is the index > of the element that suffix-matched in the given collection. If the testing > stopped because the collections were of different lengths, but were > equivalent until that point, then exactly one member of the tuple will be at > its collection's start index. If both tuple members are at their respective > collection's start index, then the collections were equivalent. If both > tuple members are at their respective collection's end index, then either the > collections' last elements differ or at least one collection was empty. > - complexity: `min(count, from.count)` comparisons. - throws: > Whatever `isEquivalent` may throw. */ > func converges<PossibleSuffix: BidirectionalCollection where > PossibleSuffix.Iterator.Element == Iterator.Element>(with possibleSuffix: > PossibleSuffix, isEquivalent: (Iterator.Element, Iterator.Element) throws -> > Bool) rethrows -> (Index, PossibleSuffix.Index) > } > extension BidirectionalCollection where Iterator.Element: Equatable { > /** Compares the collection against a given collection > element-wise and backwards until either corresponding elements are no longer > equal, or at least one collection reaches its start index. Both > collections must be finite. - parameter with: A collection to compare > to this one. - returns: A pair of indices, indicating where the two > collections started to match. The first member is the index of the element > that suffix-matched in this collection, the second is the index of the > element that suffix-matched in the given collection. If the testing stopped > because the collections were of different lengths, but were equivalent until > that point, then exactly one member of the tuple will be at its collection's > start index. If both tuple members are at their respective collection's > start index, then the collections were equivalent. If both tuple members are > at their respective collection's end index, then either the collections' last > elements differ or at least one collection was empty. - complexity: > `min(count, from.count)` comparisons. */ > func converges<PossibleSuffix: BidirectionalCollection where > PossibleSuffix.Iterator.Element == Iterator.Element>(with possibleSuffix: > PossibleSuffix) -> (Index, PossibleSuffix.Index) > } > > I don't know if the results should be discardable. > > <https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc#impact-on-existing-code>Impact > on existing code > > The comparison methods are an additive feature that doesn’t impact > existing code. > > <https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc#alternatives-considered>Alternatives > considered > The alternative is to not include these methods in the standard library, > but the user will need to develop their custom implementation of the > mismatch algorithms tailored for their needs. > > > — > Daryle Walker > Mac, Internet, and Video Game Junkie > darylew AT mac DOT com > > On Jul 6, 2016, at 5:01 AM, Daryle Walker <[email protected]> wrote: > > I mentioned in other messages about adding permutations and combinations > (probably as generators/iterators) to the standard library. I tried making > sample implementations and a proposal, but it transitioned to adapting > C++’s “is_permutation,” “next_permutation,” and “prev_permutation” > instead. The sample implementation of “is_permutation” I saw at < > http://en.cppreference.com/w/cpp/algorithm/is_permutation> involves the > “mismatch” function, which we also don’t seem to have. Since that function > seems like a small enough bite the chew, I finally made a proposal at < > https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc>. > (The Gist is currently flagged as secret.) > > Oh, it seems that everyone here has moved on to Swift 3, and so has my > third-party documentation program. Unfortunately, I still on non-beta > code, which means Swift 2.2. So I took some time having to translate > concepts between the versions, including new names. > > The name “mismatch” didn’t seem Swift-y enough since it doesn’t describe > what’s happening from a Swift programming perspective. I tried: > > * commonPrefixUntil / commonSuffixUntil > * elementsEqualUntil / elementsEqualSince > * elementsShared(until:) / elementsShared(since:) > * elementsDiverge / elementsConverge > > No, those parameters on the third one don’t make sense. The last one > inspired me to trim the fat and just use “diverge(from:)”. Since we use > indexes here like C++’s iterators, that was the best choice for a return > type that allows the users to take the results in an inspecting manner or > mutating manner. But Swift’s model doesn’t handle reversed collections > like C++ does, so I need a separate routine for mismatching with reverse > iterators, i.e. searching backwards with indexes. Since I used the > “diverge” name for the forward search, I flipped it to “converge(with:)” > for the reverse/suffix search. The returns aren’t used in quite the same > manner since I have to avoid needing a before-the-start index. > > A lot of the format was badly copied from the rotate/reverse proposal (< > https://github.com/apple/swift-evolution/blob/master/proposals/0078-rotate-algorithm.md>). > Looking for opinions, mistakes/clean-up, anything major missing?... > > — > Daryle Walker > Mac, Internet, and Video Game Junkie > darylew AT mac DOT com > > > _______________________________________________ > swift-evolution mailing list > [email protected] > https://lists.swift.org/mailman/listinfo/swift-evolution >
_______________________________________________ swift-evolution mailing list [email protected] https://lists.swift.org/mailman/listinfo/swift-evolution
