• bearophile (24/24) Sep 25 2011 In std.algorithm there is a section of set functions that work on ordere...

bearophile <bearophileHUGS lycos.com> writes:

In std.algorithm there is a section of set functions that work on ordered
iterables, like nWayUnion:
http://www.d-programming-language.org/phobos/std_algorithm.html#nWayUnion

This is an example of nWayUnion usage:


import std.algorithm;
void main() {
    auto data = [[1, 2, 3], [1, 3, 5]];
    auto expected = [1, 1, 2, 3, 3, 5];
    assert(equal(nWayUnion(data), expected));
}


But this is not a set operation, and the result is not a set. A set never
contains repeated items (a certain definition of "duplication" is possible only
if you define your own equality relation).

So in my opinion a nWayUnion function has to return:

auto data = [[1, 2, 3], [1, 3, 5]];
auto expected = [1, 2, 3, 5];
assert(equal(nWayUnion(data), expected));


While the current nWayUnion function has to be renamed "nWayMerge".

auto data = [[1, 2, 3], [1, 3, 5]];
auto expected = [1, 1, 2, 3, 3, 5];
assert(equal(nWayMerge(data), expected));

In my opinion both nWayUnion and nWayMerge are very useful operations useful in
various situations, but they are different things. In my opinion confusing the
two leads to bugs in programs that use arrays to represent sets (I have just
hit a but caused by this).


nWayUnion is probably uniq(nWayMerge). If Phobos devs don't want to add the
"nWayUnion" function, then I suggest to just rename "nWayUnion" => "nWayMerge"
(and put it outside the documentation section about set functions) to avoid
some mistakes. Names are very important, and classifications too.

The bug report/enhancement request:
http://d.puremagic.com/issues/show_bug.cgi?id=6718

Bye,
bearophile