[Issue 9842] std.algorithm.hashGroup

via Digitalmars-d-bugs digitalmars-d-bugs at puremagic.com
Tue Jan 6 08:13:14 PST 2015


https://issues.dlang.org/show_bug.cgi?id=9842

bearophile_hugs at eml.cc changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|std.algorithm.hashGroup /   |std.algorithm.hashGroup
                   |hashGroupBy                 |

--- Comment #4 from bearophile_hugs at eml.cc ---
Now I think a "hashGroup" suffices (hashGroup can also be used without template
argument, it uses an x=>x identity function on default).

In Phobos we have std.array.assocArray that allows to build a built-in
associative array from a range of key-value Phobos Tuples (it will become
mostly legacy when we will have a good associative array in Phobos and built-in
tuples in D, that is the opposite of the data structures we have today).

But there is another very common pattern of creation of associative arrays,
where you want to "accumulate" inside the values.

The basic form of accumulation is counting:

//A
const a = [1, 2, 1, 3, 5, 1, 2];
uint[int] aa1;
foreach (x; a)
    aa1[x]++;
aa1.writeln; // [1:3, 5:1, 2:2, 3:1]

Another example is just emumeration in an array:

//B
const b = [-1, 2, 1, 3, 5, -1, -2];
int[][int] aa2;
foreach (x; b)
    aa2[x.abs] ~= x;
aa2.writeln; // [1:[-1, 1, -1], 5:[5], 2:[2, -2], 3:[3]]

Or even in a set (here implemented with another associative array of
int-bools):

//C
bool[int][int] aa3;
foreach (x; b)
    aa3[x.abs][x] = true;
aa3.writeln; // [1:[1:true, -1:true], 5:[5:true], 2:[2:true, -2:true],
3:[3:true]]


There are ways to perform those operations with Phobos today, but the code is
so bad looking that it's better to skip this.


So I suggest to add a std.array.hashGroup function to Phobos that as argument
takes a range, and as template argument takes one or two functions.

The first function is a mapping key unary function.

The second function is optional and takes as argument the sub-range of grouped
values.

The patterns above become:

//A
a.hashGroup!(id, count).writeln;

//B
a.hashGroup!abs.writeln;

//C
a.hashGroup!(abs, items => items.zip(true.repeat).assocArray)).writeln;


Where "id" is the identity function (not present in Phobos):

//A
a.hashGroup!(x => x, count).writeln;

Once Phobos has a Set data structure with a constructor helper function that
accepts a range as argument you can also write just:

//C
a.hashGroup!(abs, set).writeln;

--


More information about the Digitalmars-d-bugs mailing list