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

[d-bugmail at puremagic.com]

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



--- Comment #2 from bearophile_hugs at 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: -------