on Thu Jul 07 2016, Daryle Walker <[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++ I definitely want this algorithm in the standard library, someday soon. It's out of scope for Swift 3, though. > 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 >> <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 >> <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 >> <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 > -- Dave _______________________________________________ swift-evolution mailing list [email protected] https://lists.swift.org/mailman/listinfo/swift-evolution
