14
$\begingroup$

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.

$\endgroup$
11
  • 1
    $\begingroup$ Very interesting. Look also at a = 0.7; GroupBy[{1.01, 1.02, 1.03, 1.04, 1.05, 1.06}, Echo[#, "Check"] > (Echo[a += 0.1, "a ="]) &]. It doesn't seem to check elements sequentially. $\endgroup$
    – thorimur
    Commented May 3, 2021 at 22:23
  • 1
    $\begingroup$ Also, apparently GroupBy[Table[i, {i,6}], Echo[#] > Echo[RandomReal[{0, 2}], "random"] &] sometimes checks some list elements multiple times? weird... $\endgroup$
    – thorimur
    Commented May 3, 2021 at 22:26
  • 1
    $\begingroup$ oh! it re-checks the first element that gives each key, i think. so, it'll always re-check the first element of the list, and then the first element that produced whatever the next key is, etc.. one can check this with other functions, e.g. GroupBy[Table[i, {i, 8}], Floor[Echo[#]/3] &]. $\endgroup$
    – thorimur
    Commented May 3, 2021 at 22:36
  • 1
    $\begingroup$ This has nothing to do with duplicates, nor is it a bug IMO. It is doing what it should. It effectively does a GatherBy using the criteria, then checks the same against the first member(s) of the result to build the association. When the latter test(s) are the same, only the latter is retained, as in AssociationThread... $\endgroup$
    – ciao
    Commented May 3, 2021 at 22:36
  • 2
    $\begingroup$ that's a bug in my view. it's not using the correct key-value pair $\endgroup$
    – thorimur
    Commented May 3, 2021 at 22:37

3 Answers 3

14
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ nice use of TraceScan! would you consider it a bug? although this explains the result, shouldn't GroupBy keep around the keys it finds "along the way" to build the resulting association, instead of producing them again (given cases like this)? $\endgroup$
    – thorimur
    Commented May 3, 2021 at 22:46
  • $\begingroup$ (I suppose one could hack it to do so by using a memoizing f manually, but still...) $\endgroup$
    – thorimur
    Commented May 3, 2021 at 22:48
  • 2
    $\begingroup$ @thorimur I think it should be reported at least as an unexpected behavior. $\endgroup$ Commented May 4, 2021 at 9:38
  • 4
    $\begingroup$ @AlexeyPopkov FYI and others, this has been discussed internally back in 2018, and the bug has been reported. It wasn't deemed the top priority one however. Perhaps it is time to remind ourselves about it. $\endgroup$ Commented May 4, 2021 at 12:58
  • 3
    $\begingroup$ IMO this is at best a documentation bug if it is not mentioned. $\endgroup$
    – Carsten S
    Commented May 4, 2021 at 15:51
4
$\begingroup$

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}] &)]
$\endgroup$
1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ As Leonid pointed out in the comment, this issue was already discussed internally and reported as a bug. And I personally would consider such functions as Gather etc. from the algorithmic point of view, because they are obviously intended not just for mathematical, but in the first place for programming purposes. $\endgroup$ Commented Jul 3, 2022 at 10:08
  • $\begingroup$ As to the fact that the algorithm isn't documented, it is a common problem in Mathematica, and the developers are obviously trying to implement algorithms which behave in an expected way. Double evaluation of f is unexpected and also makes the algorithm lesser efficient. It should be avoided in the first place. $\endgroup$ Commented Jul 3, 2022 at 10:12
  • $\begingroup$ I agree with @Szabolcs that this is GIGO. Perhaps the documentation could include a well-crafted sentence as to what nature f should have. It is patently obvious, but then at least one would have a place to point people to. Or include an example in the "Possible Issues" section. This is not a bug in a conventional sense. $\endgroup$
    – user293787
    Commented Jul 3, 2022 at 10:15
  • $\begingroup$ I've seen the comment, but the fact that "it was discussed" is not really related to the point I was trying to make. A for considering it as an algorithm: I disagree that this is productive. You can define the result of an operation, or you can define the algorithmic steps it performs. The latter is inflexible, hard to reason about, and leaves no room for future optimization. If this were up to me, I would definitely define GroupBy through its result, not through an algorithm. Yes, it is necessary for this to impose restrictions on the input, and I would document those for clarity. $\endgroup$
    – Szabolcs
    Commented Jul 3, 2022 at 10:16
  • $\begingroup$ The point about "result vs steps to achieve result" does not always apply, of course. I am talking specifically about GroupBy here. I have pointed out many, many times that the network community detection functions in Mathematica are almost completely useless because community detection is not a mathematically well-defined concept. The result can't be separated from the steps to get the result. There's (almost) no way to evaluate the result in isolation, and there is no criterion by which to decide if it's correct. $\endgroup$
    – Szabolcs
    Commented Jul 3, 2022 at 10:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.