Comparison of Dispatch objects ureliable in Mathematica 10

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.