[Issue 6718] "nWayUnion" => "nWayMerge", plus true nWayUnion
http://d.puremagic.com/issues/show_bug.cgi?id=6718 Andrei Alexandrescu changed: What|Removed |Added CC||and...@erdani.com --- Comment #1 from Andrei Alexandrescu 2013-02-27 05:32:27 PST --- Here "union" has the meaning in relational algebra, not in set theory. I'll keep this opened until I add a mention to the documentation. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 6718] "nWayUnion" => "nWayMerge", plus true nWayUnion
http://d.puremagic.com/issues/show_bug.cgi?id=6718 --- Comment #2 from bearophile_h...@eml.cc 2013-02-27 09:54:36 PST --- (In reply to comment #1) > Here "union" has the meaning in relational algebra, not in set theory. I'll > keep this opened until I add a mention to the documentation. Thank you for the answer. So all those set functions turn out not being about _sets_. Adding a mention in the documentation is not enough. So: 1) I suggest to rename "nWayUnion" as "nWayMerge", to avoid any confusion in D programmers like me. In the Merge Sort that algorithm is named "Merge", so calling it "merge" has a very long tradition in computer science (http://en.wikipedia.org/wiki/Merge_algorithm ). 2) In this page: http://dlang.org/phobos/std_algorithm.html The "Set operations" column is misnamed because those are NOT sets. In Computer Science and in Mathematics those are named bags or multisets (http://en.wikipedia.org/wiki/Multiset ). But those functions work with a comparison operator and work on ordered sequences, so I suggest to call that column "Multiset operations" or "Ordered bags operations". 3) setIntersection is equally badly named. And it should be renamed "bagsIntersection", or something similar. Also the examples given in the site for setIntersection show only true sets, so this contribute to the confusion, it's even more easy to miss that it is actually a bags intersection: int[] a = [ 1, 2, 4, 5, 7, 9 ]; int[] b = [ 0, 1, 2, 4, 7, 8 ]; int[] c = [ 0, 1, 4, 5, 7, 8 ]; assert(equal(setIntersection(a, a), a)); assert(equal(setIntersection(a, b), [1, 2, 4, 7][])); assert(equal(setIntersection(a, b, c), [1, 4, 7][])); Those examples need to show clearly some repetitions, like this: int[] a = [1, 1, 2, 4, 5, 5, 5, 5, 7, 9]; int[] b = [0, 1, 2, 4, 7, 7, 8]; int[] c = [0, 1, 1, 1, 1, 4, 4, 5, 7, 8]; Extra) Is it worth to add a true nWayUnion (in set theory sense) to std.algorithm? It's a useful operation. A nWayUnion is possibly computed as: seqs.nWayMerge.uniq.array So maybe it's not worth it, I don't know. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 6718] "nWayUnion" => "nWayMerge", plus true nWayUnion
http://d.puremagic.com/issues/show_bug.cgi?id=6718 bearophile_h...@eml.cc changed: What|Removed |Added Severity|normal |major --- Comment #3 from bearophile_h...@eml.cc 2013-02-27 09:55:47 PST --- Raised importance to Major, because this naming cancer in std.algorithm is worse than I expected in 2011. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 6718] "nWayUnion" => "nWayMerge", plus true nWayUnion
http://d.puremagic.com/issues/show_bug.cgi?id=6718 Andrei Alexandrescu changed: What|Removed |Added Severity|major |minor --- Comment #4 from Andrei Alexandrescu 2013-02-27 10:02:00 PST --- No need to raise importance out of proportion. Thanks. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 6718] "nWayUnion" => "nWayMerge", plus true nWayUnion
http://d.puremagic.com/issues/show_bug.cgi?id=6718 --- Comment #5 from bearophile_h...@eml.cc 2013-02-27 10:06:41 PST --- (In reply to comment #4) > No need to raise importance out of proportion. Thanks. OK, sorry. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 6718] "nWayUnion" => "nWayMerge", plus true nWayUnion
https://issues.dlang.org/show_bug.cgi?id=6718 Andrei Alexandrescu changed: What|Removed |Added Keywords||bootcamp --- Comment #7 from Andrei Alexandrescu --- nWayUnion shall stay, but we can add new and better names and alias nWayUnion to one of them. --
[Issue 6718] "nWayUnion" => "nWayMerge", plus true nWayUnion
https://issues.dlang.org/show_bug.cgi?id=6718 RazvanN changed: What|Removed |Added CC||razvan.nitu1...@gmail.com --- Comment #8 from RazvanN --- So, how should we proceed here? Rename nWayUnion to nWayMerge and alias nWayUnion to it? If we do that we should probably deprecate nWayUnion. --
[Issue 6718] "nWayUnion" => "nWayMerge", plus true nWayUnion
https://issues.dlang.org/show_bug.cgi?id=6718 --- Comment #9 from Andrei Alexandrescu --- (In reply to RazvanN from comment #8) > So, how should we proceed here? Rename nWayUnion to nWayMerge and alias > nWayUnion to it? If we do that we should probably deprecate nWayUnion. @RazvanN, let's do this: * rename nWayUnion to multiwayMerge * rename struct NWayUnion to MultiwayMerge * leave nWayUnion as an undocumented alias of multiwayMerge. Mention in the documentation that "...for backward compatibility, `multiwayMerge` is also available under the name `nWayUnion`, which will be deprecated. New code should use `multiwayMerge`." Coordinate with Sebastian and Vladimir about the exact text and layout. That would be one PR. The second PR: * add function multiwayUnion that actually performs the union (no repeats). A simple implementation is to pipe the result of multiwayMerge through uniq. * add function multiwayIntersection that performs the intersection of multiple sets. These pull requests would close this issue. --
[Issue 6718] "nWayUnion" => "nWayMerge", plus true nWayUnion
https://issues.dlang.org/show_bug.cgi?id=6718 --- Comment #10 from RazvanN --- (In reply to Andrei Alexandrescu from comment #9) > (In reply to RazvanN from comment #8) > > So, how should we proceed here? Rename nWayUnion to nWayMerge and alias > > nWayUnion to it? If we do that we should probably deprecate nWayUnion. > > @RazvanN, let's do this: > > * rename nWayUnion to multiwayMerge > > * rename struct NWayUnion to MultiwayMerge > > * leave nWayUnion as an undocumented alias of multiwayMerge. Mention in the > documentation that "...for backward compatibility, `multiwayMerge` is also > available under the name `nWayUnion`, which will be deprecated. New code > should use `multiwayMerge`." Coordinate with Sebastian and Vladimir about > the exact text and layout. > > That would be one PR. The second PR: > > * add function multiwayUnion that actually performs the union (no repeats). > A simple implementation is to pipe the result of multiwayMerge through uniq. > > * add function multiwayIntersection that performs the intersection of > multiple sets. > > These pull requests would close this issue. We already have setIntersection which, as bearophile pointed out, computes the bags intersection. Maybe we should also rename setIntersection to multiwayIntersection and use setIntersection for the newly added function. I know that this may break code but setIntersection is very misleading --
[Issue 6718] "nWayUnion" => "nWayMerge", plus true nWayUnion
https://issues.dlang.org/show_bug.cgi?id=6718 --- Comment #11 from Andrei Alexandrescu --- >Maybe we should also rename setIntersection to multiwayIntersection setIntersection has two inputs. "multiwayIntersection" would have multiple inputs (a range of ranges) and would be a distinct function with important uses and its own theory and practice (http://www.cs.toronto.edu/~tl/papers/wea06.pdf is a good overview). --
[Issue 6718] "nWayUnion" => "nWayMerge", plus true nWayUnion
https://issues.dlang.org/show_bug.cgi?id=6718 --- Comment #12 from RazvanN --- (In reply to Andrei Alexandrescu from comment #11) > >Maybe we should also rename setIntersection to multiwayIntersection > > setIntersection has two inputs. "multiwayIntersection" would have multiple > inputs (a range of ranges) and would be a distinct function with important > uses and its own theory and practice > (http://www.cs.toronto.edu/~tl/papers/wea06.pdf is a good overview). If I understand correctly, setIntersection is going to do a bags intersection for just 2 ranges, while multiwayIntersection is going to be a generalization of set intersection (i.e. it will still do bags intersection) --
[Issue 6718] "nWayUnion" => "nWayMerge", plus true nWayUnion
https://issues.dlang.org/show_bug.cgi?id=6718 --- Comment #13 from RazvanN --- (In reply to Andrei Alexandrescu from comment #11) > >Maybe we should also rename setIntersection to multiwayIntersection > > setIntersection has two inputs. "multiwayIntersection" would have multiple > inputs (a range of ranges) and would be a distinct function with important > uses and its own theory and practice > (http://www.cs.toronto.edu/~tl/papers/wea06.pdf is a good overview). Actually, looking at the implementation, it seems that setIntersection also has a variable number of inputs : https://dlang.org/phobos/std_algorithm_setops.html#setIntersection --
[Issue 6718] "nWayUnion" => "nWayMerge", plus true nWayUnion
https://issues.dlang.org/show_bug.cgi?id=6718 --- Comment #14 from Andrei Alexandrescu --- (In reply to RazvanN from comment #13) > (In reply to Andrei Alexandrescu from comment #11) > > >Maybe we should also rename setIntersection to multiwayIntersection > > > > setIntersection has two inputs. "multiwayIntersection" would have multiple > > inputs (a range of ranges) and would be a distinct function with important > > uses and its own theory and practice > > (http://www.cs.toronto.edu/~tl/papers/wea06.pdf is a good overview). > > Actually, looking at the implementation, it seems that setIntersection also > has a variable number of inputs : > https://dlang.org/phobos/std_algorithm_setops.html#setIntersection It has a number of inputs known during compilation. True "multi" set intersection takes a range of ranges, i.e. an arbitrary number of sets. --
[Issue 6718] "nWayUnion" => "nWayMerge", plus true nWayUnion
https://issues.dlang.org/show_bug.cgi?id=6718 --- Comment #15 from github-bugzi...@puremagic.com --- Commits pushed to master at https://github.com/dlang/phobos https://github.com/dlang/phobos/commit/9efa504bdca2b2644375e86d3b1527170512b726 Fix Issue 6718 - nWayUnion => nWayMerge, plus true nWayUnion https://github.com/dlang/phobos/commit/bdae5f08f3cf4ed153063ad1d9a07fbb5aa12668 Merge pull request #5620 from RazvanN7/Issue_6718 [WIP] Fix Issue 6718 - nWayUnion => nWayMerge, plus true nWayUnion merged-on-behalf-of: Andrei Alexandrescu --
[Issue 6718] "nWayUnion" => "nWayMerge", plus true nWayUnion
https://issues.dlang.org/show_bug.cgi?id=6718 --- Comment #16 from github-bugzi...@puremagic.com --- Commits pushed to stable at https://github.com/dlang/phobos https://github.com/dlang/phobos/commit/9efa504bdca2b2644375e86d3b1527170512b726 Fix Issue 6718 - nWayUnion => nWayMerge, plus true nWayUnion https://github.com/dlang/phobos/commit/bdae5f08f3cf4ed153063ad1d9a07fbb5aa12668 Merge pull request #5620 from RazvanN7/Issue_6718 --
[Issue 6718] "nWayUnion" => "nWayMerge", plus true nWayUnion
https://issues.dlang.org/show_bug.cgi?id=6718 --- Comment #17 from github-bugzi...@puremagic.com --- Commits pushed to dmd-cxx at https://github.com/dlang/phobos https://github.com/dlang/phobos/commit/9efa504bdca2b2644375e86d3b1527170512b726 Fix Issue 6718 - nWayUnion => nWayMerge, plus true nWayUnion https://github.com/dlang/phobos/commit/bdae5f08f3cf4ed153063ad1d9a07fbb5aa12668 Merge pull request #5620 from RazvanN7/Issue_6718 --
[Issue 6718] "nWayUnion" => "nWayMerge", plus true nWayUnion
http://d.puremagic.com/issues/show_bug.cgi?id=6718 Denis Shelomovskij changed: What|Removed |Added CC||verylonglogin@gmail.com Severity|minor |normal --- Comment #6 from Denis Shelomovskij 2013-09-30 18:00:41 MSD --- Bearophile, what about to start NG thread about it? Bad names are always causes of user code bugs so this issue should be thoroughly considered. Also restored "normal" importance as terminology isn't a minor issue. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---