# Is it OK that SameQ considers expressions identical, although they have different structure?

\$Version
(* 10.2.0 for Microsoft Windows (64-bit) (July 7, 2015) *)

Information[SameQ]
(* lhs===rhs yields True if the expression
lhs is identical to rhs, and yields False otherwise.  >> *)

a = SparseArray[Automatic, {1}, 0, {1, {{0, 0}, {}}, {}}] &;

b = With[{s = SparseArray[Automatic, {1}, 0, {1, {{0, 0}, {}}, {}}]}, s &];

SameQ[a, b]
(* True *)

Depth /@ {a, b}
(* {6, 3} *)

LeafCount /@ {a, b}
(* {14, 2} *)

Position[a, _]
(* {{0}, {1, 0}, {1, 1}, {1, 2, 0}, {1, 2, 1}, {1, 2}, {1, 3},
{1, 4, 0}, {1, 4, 1}, {1, 4, 2, 0}, {1, 4, 2, 1, 0}, {1, 4, 2, 1, 1},
{1, 4, 2, 1, 2}, {1, 4, 2, 1}, {1, 4, 2, 2, 0}, {1, 4, 2, 2},
{1, 4, 2}, {1, 4, 3, 0}, {1, 4, 3}, {1, 4}, {1}, {}} *)

Position[b, _]
(* {{0}, {1}, {}} *)


Is it expected behavior? Are the expressions stored in variables a and b identical?

Update: I found function SystemPrivateVerbatimSameQ that appears to check if two expressions are really completely identical.

• Have you looked at FullForm /@ {a, b}? In case a, SparseArray has not evaluated, but in case b, it has and become atomic, which affects Depth and LeafCount, but not the FullForm (nor, therefore, SameQ). – Michael E2 Mar 3 '16 at 4:50
• FullForms look character-wise identical, StandardForms look different. TreeForms are also slightly different. – Vladimir Reshetnikov Mar 3 '16 at 4:53
• Hashes are the same. – Vladimir Reshetnikov Mar 3 '16 at 5:02
• I noticed before that SameQ will give true for two arrays that differ in whether they are packed or not, Needs["Developer"]; ara = RandomReal[1, {5, 5}]; ara2 = FromPackedArray[ara]; {PackedArrayQ /@ {ara, ara2}, SameQ[ara, ara2]}. They do end up having the same FullForm and Hash, but they aren't perfectly the same under the hood. – Jason B. Mar 3 '16 at 8:33
• I also noticed that Uncompress[Compress[b]] does not round-trip b exactly, but rather converts it to the same form as a. – Vladimir Reshetnikov Mar 3 '16 at 18:18

We need not turn to anything as complicated as SparseArray to see the same behavior.

a = Rational[1, 2] &
b = With[{s = Rational[1, 2]}, s &]

(*  Rational[1, 2] &  *)

(*  1/2 &             *)

a === b

(*  True              *)


Structurally these are equivalent, but in one case the structure is unevaluated and in the other it is the external representation of an atomic internal format.

I learned to doubt "sameness" from the answers to my Stack Overflow question:

As WReach wrote: SameQ Is Not An Equivalence Relation

A more trustworthy comparator is Order.

Order[a, b]

(*  -1              *)


The function SystemPrivateVerbatimSameQ that you discovered is not a solution, at least in version 10.1.0. Instead it appears to just be SameQ with a HoldAllComplete attribute. Evaluating a and b gives the same "True" result as SameQ:

SystemPrivateVerbatimSameQ @@ {a, b}

SystemPrivateVerbatimSameQ[##] &[a, b]

(*  True              *)

(*  True              *)

• Interestingly, applying FullForm[] on both a and b shows them to be both Function[Rational[1, 2]], so I wonder if the display is a different issue altogether. – J. M. is in limbo Jan 24 '17 at 11:50
• @J.M. I fear I don't understand the point you are making. As I said they are structurally identical. One is atomic however and the other is not. AtomQ[Rational[1, 2]] vs AtomQ[Unevaluated@Rational[1, 2]]. – Mr.Wizard Jan 24 '17 at 12:06
• It was less a point and more a question of sorts; now that you mention that AtomQ[Unevaluated @ Rational[1, 2]] is False, I'm now actually confused as to why the Unevaluated[] makes a difference, even after using Trace[] to see how things work. (This also happens with Complex[], apparently.) – J. M. is in limbo Jan 24 '17 at 12:13
• @J.M. I terribly fear I am "teaching grandmother to suck eggs" but: it is impossible to enter atomic expressions directly in plain code: Rational[1, 2] must evaluate before it becomes atomic; until then it is just an arbitrary head with two leaves. (I know AtomQ[Unevaluated[1]] is an exception to that statement but I think numeric entry forms are a special case, cf HoldComplete[1*^6].) – Mr.Wizard Jan 24 '17 at 12:16
• I see; so my gedanken Mathematica was faulty in that respect. Thanks, and I had better update! :D – J. M. is in limbo Jan 24 '17 at 12:19

The problem is that SparseArrays are "atomic". Mathematica is getting more and more atomic expressions with each version. There are good reasons for this (mostly performance), but it can also get problematic because there are many operations which need to be defined (i.e. what makes sense) and implemented separately for each kind of atomic expression. Sometimes this implementation is done in a not fully consistent way. The discrepancy between SameQ and Depth is one example.

I think that finding the best way to handle each atomic expression is not at all an easy task. SparseArray has certain behaviours only because it represents an array, for which operations like e.g Length make sense. Thus enacting general rules, like "every atomic expression has Length 0" would be counterproductive. Some inconsistency is probably unavoidable.

What complicates matters more is that many complex atomic objects do have a compound expression representation, which will usually immediately eveluate to the atomic version. These representations are typically used for serialization—writing to text files (Save), sending through MathLink, Compressing, etc. See this post on how to get this representation reliably. How visible these representations are during normal use varies. Some will show up with a simple InputForm.

In principle, there can be a disconnect between what an expression represents conceptually, what its compound form looks like, and what its true internal representation is. In practice, there probably is a disconnect between them. For example, think about Graphs. It isn't even obvious when two graphs are conceptually the same. Should that mean isomorphism? Should it mean that they are identical as labelled graphs? Should it mean that they are represented with identical data structures? It is not very well known that Graph` can have multiple different internal representations (sparse array, edge list, ect.), which are completely transparent to users. There also seems to be some internal caching going on with certain graph computations (e.g. possibly with layouts), which again isn't exposed at all to the user.

This is not an answer, just a long comment. I made this comment because some might read your question as a complaint—"something obviously isn't right". But I just don't see how it could be made to work in a way that everyone would agree is correct.

• "something obviously isn't right" because this is a growing part of the system and documentation does not explain it. The tutorial/ExpressionsOverview says nothing, isn't it ridiculous? – Kuba Jan 24 '17 at 12:15