[Issue 6718] "nWayUnion" => "nWayMerge", plus true nWayUnion

[d-bugmail--- via Digitalmars-d-bugs]

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

[via Digitalmars-d-bugs]

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

[via Digitalmars-d-bugs]

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 <andra...@users.noreply.github.com>

--

[Issue 6718] "nWayUnion" => "nWayMerge", plus true nWayUnion

[via Digitalmars-d-bugs]

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

[via Digitalmars-d-bugs]

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

[via Digitalmars-d-bugs]

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

[via Digitalmars-d-bugs]

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

[via Digitalmars-d-bugs]

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

[via Digitalmars-d-bugs]

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

[via Digitalmars-d-bugs]

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

[via Digitalmars-d-bugs]

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

[d-bugmail]

http://d.puremagic.com/issues/show_bug.cgi?id=6718


Denis Shelomovskij verylonglogin@gmail.com changed:

   What|Removed |Added

 CC||verylonglogin@gmail.com
   Severity|minor   |normal


--- Comment #6 from Denis Shelomovskij verylonglogin@gmail.com 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: ---

[Issue 6718] nWayUnion = nWayMerge, plus true nWayUnion

[d-bugmail]

http://d.puremagic.com/issues/show_bug.cgi?id=6718


Andrei Alexandrescu and...@erdani.com changed:

   What|Removed |Added

 CC||and...@erdani.com


--- Comment #1 from Andrei Alexandrescu and...@erdani.com 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

[d-bugmail]

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

[d-bugmail]

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

[d-bugmail]

http://d.puremagic.com/issues/show_bug.cgi?id=6718


Andrei Alexandrescu and...@erdani.com changed:

   What|Removed |Added

   Severity|major   |minor


--- Comment #4 from Andrei Alexandrescu and...@erdani.com 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

[d-bugmail]

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: ---