GroupBy sometimes deletes values

Question

Bug persisting through 13.1.0

---

GroupBy[{1, 1, 1, 1, 1, 1}, # > RandomReal[{0, 2}] &]

sometimes returns something like

<|False -> {1, 1, 1, 1}, True -> {1, 1}|>

but then again it might just return

<|True -> {1, 1, 1, 1}|>

Very strange. Apparently this issue can arise without duplicates though. The following two always have the same results.

a = 0.7;
GroupBy[{1, 1, 1, 1, 1, 1}, # > (a += 0.1) &]
(* <|False -> {1, 1, 1, 1}|> *)

a = 0.7;
GroupBy[{1.01, 1.02, 1.03, 1.04, 1.05, 1.06}, # > (a += 0.1) &]
(* <|False -> {1.04, 1.05, 1.06}|> *)

Is there a good reason for this? Seems like a bug.

Answer 1

The problem is that GroupBy uses the key function once to map over all of the elements, and then it uses it again for each distinct key. As an example, consider:

SeedRandom[3];

f[x_] := x > RandomReal[2]

TraceScan[
    Identity,
    GroupBy[{1, 1, 1, 1, 1, 1}, f],
    _Map,
    Print @* Rule,
    TraceInternal -> True
];

f/@{1,1,1,1,1,1}->{True,True,True,True,True,False}

Note that there are 5 trues and 1 false when mapping. From this information, GroupBy constructs the following association:

<|f[1] -> {1, 1, 1, 1, 1}, f[1] -> {1}|>

This is where the last two function calls of f occurs.

SeedRandom[3]

TraceScan[
    Identity,
    GroupBy[{1, 1, 1, 1, 1, 1}, f],
    _f,
    Print @* Rule,
    TraceOff -> Map,
    TraceInternal->True
];

f[1]->False

f[1]->False

Note that both function calls return False, so the final association is:

<|False -> {1, 1, 1, 1, 1}, False -> {1}|>

<|False -> {1}|>

When an association has duplicate keys, only the last duplicate is retained. This explains the behavior you see.

An alternative to using GroupBy is to use the ResourceFunction "GroupByList":

SeedRandom[3]

ResourceFunction["GroupByList"][{1, 1, 1, 1, 1, 1}, f /@ {1, 1, 1, 1, 1, 1}]

<|True -> {1, 1, 1, 1, 1}, False -> {1}|>

Answer 2

Per my comment, observe:

myGB[lst_, tst_] := With[{gb = GatherBy[lst, tst]},
   If[Length@gb == 1, AssociationThread[{tst@gb[[1, 1]]} -> gb],
    AssociationThread[{tst@gb[[1, 1]], tst@gb[[2, 1]]} -> gb]]];

Then test with the following. The results will be the same.

xxx = {1, 1, 1, 1, 1, 1};
seed = RandomInteger[500];

SeedRandom[seed];
GroupBy[xxx, # > RandomReal[{0, 2}] &]

SeedRandom[seed];
myGB[xxx, (# > RandomReal[{0, 2}] &)]

Answer 3

I would not consider this a bug. Here's why.

The second argument that you passed to GroupBy was not a function in the mathematical sense, or even in the functional programming sense. It does not return the same output for the same input.

Then the question is: Do we consider GroupBy as an algorithm? Are we in the procedural programming mindset? If so, then the specific steps of algorithm should be documented, but they are not ... It's much clearer to start with a mathematical mindset, which in this case is the same as the functional programming one, and consider GroupBy to compute equivalence classes based on a function. If so, then this is a GIGO situation: the input to GatherBy was nonsense (i.e. not a function), so no wonder the output is nonsense too.

There are many other functions which can be broken in a similar way. Consider not GatherBy, but simply Gather. The second argument should not only be a function, but also an equivalence relation, i.e. symmetric, transitive, and reflexive. Or in Sort, the second argument should be a total order. If these conditions are not satisfied, then Gather or Sort clearly cannot work correctly.

Mathematica has no formal way to encode that a function has such properties, so it becomes the users' responsibility to pass in valid input.