5
$\begingroup$

In 2008 I wrote a group theory package. I've recently started using it again, and I found that one (at least) of my functions is broken in Mathematica 10. The problem is complicated to describe, but the essence of it occurs in this line:

l = Split[l, Union[#1] == Union[#2] &]

Here l is a list of sets. The intent of the line is to split l into sublists of identical sets. Each set is represented as a list of group elements. I say "sets" rather than "lists" because two sets are to be considered identical if they contain the same members in any order. This is the reason for comparing Unions of the sets.

This used to work, but now it doesn't. The problem is that sets that, as far as I can tell, are equal, do not compare equal by this test. fact, the comparison e1 == e2 for indistinguishable group elements e1 and e2 also sometimes fails to yield True. (It remains unevaluated; e1 === e2 evaluates to False.) The elements can be fairly complicated objects. For instance, in one case where I'm having this problem, ByteCount[e1] is 2448. But e1 and e2 are indistinguishable. For instance, ToString[FullForm[e1]] === ToString[FullForm[e2]] yields True.

I've shown one line where this failure to compare equal causes a problem. In this one case I could probably work around the problem by defining UpValues for e1 == e2 or e1 === e2. But, unfortunately, the problem raises its head in other contexts as well. For instance, I am trying to use GraphPlot to show a cycle graph of the elements. GraphPlot takes a list of edges of the form ei->ej. In order to recognize that edges ei->ej and ei->ek are both connected to ei, GraphPlot needs to know that the ei appearing in the first edge is the same as ei in the second. It doesn't, so I get a disconnected graph. Unlike Split, GraphPlot doesn't provide a hook to enable me to tell it how to test vertexes for equality, and it apparently doesn't use Equal or SameQ, either, as UpValues I define for those are not used.

(Sorry about the generic tag -- I couldn't find anything more specific. Suggestions welcome.)

EDIT: In response to Szabolcs request, here is the FullForm of such an object:

a = sdp[znz[1, 3], 
 aut[List[Rule[znz[1, 3], znz[1, 3]]], 
  List[Rule[znz[0, 3], znz[0, 3]], Rule[znz[1, 3], znz[1, 3]], 
   Rule[znz[2, 3], znz[2, 3]]], 
  Dispatch[List[Rule[znz[0, 3], znz[0, 3]], 
    Rule[znz[1, 3], znz[1, 3]], Rule[znz[2, 3], znz[2, 3]]]]], 
 Function[NonCommutativeMultiply[Slot[2], Slot[1]]]]

b = sdp[znz[1, 3], 
 aut[List[Rule[znz[1, 3], znz[1, 3]]], 
  List[Rule[znz[0, 3], znz[0, 3]], Rule[znz[1, 3], znz[1, 3]], 
   Rule[znz[2, 3], znz[2, 3]]], 
  Dispatch[List[Rule[znz[0, 3], znz[0, 3]], 
    Rule[znz[1, 3], znz[1, 3]], Rule[znz[2, 3], znz[2, 3]]]]], 
 Function[NonCommutativeMultiply[Slot[2], Slot[1]]]]

a === b

(* ==> False *)

Note that a and b are identical and ToString[a] === ToString[b] gives True.

$\endgroup$
  • $\begingroup$ What version did you write it in? $\endgroup$ – dr.blochwave Nov 18 '14 at 17:08
  • $\begingroup$ Not sure--whatever was current in 2008. 6, maybe. $\endgroup$ – Leon Avery Nov 18 '14 at 17:17
  • 2
    $\begingroup$ == is not really an appropriate way of testing whether expressions are the same. It's meant to be used to represent mathematical equality between algebraic expressions. This is why a==b won't evaluate to True or False. According to Mathematica, a and b stand for (complex) numbers here and whether they're equal depends on what is a and b. I think in your case === is the way to go. $\endgroup$ – Szabolcs Nov 18 '14 at 17:21
  • 1
    $\begingroup$ A pastebin is a website for temporarily sharing text (code, datafiles, etc.). Like this one. I suggested it because I thought that your expression would be huge and wouldn't fit in a post here. But it's quite small actually, so there's no need for the pastebin. I'll take a look at this when I have time. First idea: I know that Dispatch has been changed in Mathematica 10, so it's the first suspect. $\endgroup$ – Szabolcs Nov 18 '14 at 17:58
  • 1
    $\begingroup$ This was filed as a bug report. $\endgroup$ – Daniel Lichtblau Nov 18 '14 at 22:21
7
$\begingroup$

This is not a full answer, just a start towards a solution.

The culprit is Dispatch, which became atomic in version 10, and comparison wasn't implemented for it.

Here's a small test in version 9:

In[1]:= a = 
  Dispatch[{"a" -> 1, "b" -> 2, "c" -> 3, "d" -> 4, "e" -> 5, 
    "f" -> 6, "g" -> 7, "h" -> 8, "i" -> 9, "j" -> 10, "k" -> 11, 
    "l" -> 12, "m" -> 13}];

In[2]:= b = 
  Dispatch[{"a" -> 1, "b" -> 2, "c" -> 3, "d" -> 4, "e" -> 5, 
    "f" -> 6, "g" -> 7, "h" -> 8, "i" -> 9, "j" -> 10, "k" -> 11, 
    "l" -> 12, "m" -> 13}];

In[3]:= AtomQ[a]
Out[3]= False

In[4]:= a === b
Out[4]= True

(Note that there need to be a certain number of elements in the dispatch table before it actually builds a hash table from it. It won't happen when using only a few rules.)

In version 10 we get

In[3]:= AtomQ[a]
Out[3]= True

In[4]:= a === b
Out[4]= False

Unfortunately I do not see an easy solution around this as the Dispatch objects are only small parts of the expressions you are comparing. A "proper" solution would be a significant reworking of the package, but who has time for that ... ?

Another question is: is this a bug? I suspect that many programmers (which most of us aren't) wouldn't consider it a bug. There was good reason to make Dispatch atomic, for good performance, and seamlessly integrating atomic objects into Mathematica is hard. Lots of operations need special implementation for a seamless integration: pattern matching, comparison, translation to/from some sort of FullForm, etc. Also, the type of comparison you are doing between these expressions could be considered a hack or a quick-and-dirty solution.

On the other hand: Mathematica has always had the implicit promise that we can rely on everything being an expression and one of its big strengths is that it's really easy to hack together useful and working solutions. They are often not proper solutions, but most people who use Mathematica (researchers) don't develop software, as programmers do. We just create quick and dirty solutions for our own immediate use, targeted at the problem at hand. And Mathematica really shines at this.

You should definitely contact WRI about this and let them know about your use case.


Possible workaround

Here's a possible workaround: instead of Dispatch, use Association (new in 10). In a quick test, Association seems to give similar performance benefits to Dispatch. But unlike Dispatch, associations can be compared using ===. Just be sure to KeySort the association before including it in the expression: <| a -> 1, b -> 2 |> is different from <| b -> 2, a -> 1 |>.

$\endgroup$
  • 2
    $\begingroup$ +1, didn't know comparison was order sensitive $\endgroup$ – alancalvitti Nov 18 '14 at 21:47
5
$\begingroup$

As @Szabolcs points out Dispatch does not interact well with SameQ, etc in Mathematica 10.

Dispatch[1 -> 2] === Dispatch[1 -> 2]

False

Dispatch[1 -> 2] == Dispatch[1 -> 2]

False

Use Normal to "expand" the dispatch objects and then the comparison should work.

Normal[Dispatch[1 -> 2]] == Normal[Dispatch[1 -> 2]]

True

Normal works on your complete example expression:

Normal[sdp[znz[1, 3], 
  aut[List[Rule[znz[1, 3], znz[1, 3]]], 
   List[Rule[znz[0, 3], znz[0, 3]], Rule[znz[1, 3], znz[1, 3]], 
    Rule[znz[2, 3], znz[2, 3]]], 
   Dispatch[
    List[Rule[znz[0, 3], znz[0, 3]], Rule[znz[1, 3], znz[1, 3]], 
     Rule[znz[2, 3], znz[2, 3]]]]], 
  Function[NonCommutativeMultiply[Slot[2], Slot[1]]]]]

sdp[znz[1, 3], aut[{znz[1, 3] -> znz[1, 3]}, {znz[0, 3] -> znz[0, 3], znz[1, 3] -> znz[1, 3], znz[2, 3] -> znz[2, 3]}, {znz[0, 3] -> znz[0, 3], znz[1, 3] -> znz[1, 3], znz[2, 3] -> znz[2, 3]}], #2 ** #1 &]

PS As the documentation for Dispatch states "The use of Dispatch will never affect results that are obtained", this should probably be classified as a bug.

$\endgroup$
  • $\begingroup$ Thanks. That at least identifies the problem. The solution is still elusive, since there is no hook (in GraphPlot, for instance) that would enable me to change the way objects are tested for identity. $\endgroup$ – Leon Avery Nov 18 '14 at 18:15
  • $\begingroup$ Can you not simply apply Normal to your objects before using them in GraphPlot - see my edit? If your lists of rules are short, as in your example, there is little advantage in having them in Dispatched form in any case. $\endgroup$ – MikeLimaOscar Nov 18 '14 at 18:27
  • $\begingroup$ If it were only GraphPlot, maybe. But it's not that simple. The replacement lists can be much longer. (I wouldn't be using Dispatch in the first place if they were always order 3.) And operations on Normalized elements may produce elements with Dispatch lists. Looks like I have a major rewrite ahead. Perhaps replace Dispatch with Association... It's advertised as efficient, and seems to have sane comparison behavior. $\endgroup$ – Leon Avery Nov 18 '14 at 18:42
  • $\begingroup$ Oh well, you'll just have to decide which workaround is easiest for you to implement (or if you want to wait for a fix from Wolfram :-) Good luck! $\endgroup$ – MikeLimaOscar Nov 18 '14 at 19:10
3
$\begingroup$

Another possible workaround is to wrap Dispatch with a memoized function, so that both expressions a and b contain references to the same internal dispatch table.

i.e. define

mem : disp[x_] := mem = Dispatch[x]

then use disp in place of Dispatch in your code.

$\endgroup$
  • $\begingroup$ Suggestion: it might also be worth taking care of different rule orderings. $\endgroup$ – Szabolcs Nov 18 '14 at 18:45
  • $\begingroup$ @Szabolcs, in general rule order does matter though. Or is it different for Dispatch? $\endgroup$ – Simon Woods Nov 18 '14 at 18:59
  • $\begingroup$ You're right, it does matter. $\endgroup$ – Szabolcs Nov 18 '14 at 19:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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