[BUG] Dictionary equality test

Richard A. O'Keefe ok at cs.otago.ac.nz
Mon Jun 10 02:56:13 UTC 2002


Andres Valloud <sqrmax at prodigy.net>
has replied to my note about Dictionary>> = 
	> Dictionary>>
	> = aDictionary
	>     (aDictionary isKindOf: Dictionary) ifFalse: [^false].
	>     self size = aDictionary size ifFalse: [^false].
	>     self associationsDo: [:assoc|
	>         (aDictionary at: assoc key ifAbsent: [^false]) =
	>		assoc value ifFalse: [^false]].
	>     ^true
	
Note that this code makes NO assumption about how Associations are
compared.  It is entirely equivalent in effect to

    Dictionary>>
    = aDictionary
        (aDictionary isKindOf: Dictionary) ifFalse: [^false].
	self size = aDictionary size ifFalse: [^false].
	self keysAndValuesDo: [:key :value |
	    (aDictionary at: key ifAbsent: [^false]) = value
	        ifFalse: [^false]]
	^true

except that it is slightly more efficient.

	I think Dictionaries are just collections whose contents are accessed
	through arbitrary names --- as opposed to e.g. Arrays, whose contents
	are accessed through positive integer names.
	
Yes, exactly.
That's PRECISELY what that method checks when given another dictionary.

	IMHO, given that associations are equal iif their keys are equal, a
	dictionary is *not* a set of associations.
	
The fact that Squeak compares Associations weirdly is irrelevant,
because the code above DOES NOT COMPARE THE ASSOCIATIONS.

	Therefore, I think Dictionary>>= should read:
	
	= aDictionary
	
		self species = aDictionary species ifFalse: [^false].
		^self asBag = aDictionary asBag
	
This is quite wrong.  This would make
    (Dictionary new at: #x put: 1; at: #y put: 2; yourself)
  = (Dictionary new at: #x put: 2; at: #y put: 1; yourself)
true, when it obviously should be false.

Or rather, it WOULD return true if only Bag comparison worked.
Example:
    b1 := Bag new add: 1; add: 2; yourself.
    b2 := Bag new add: 2; add: 1; yourself.
    {b1. b2. b1 = b2}
prints
    #(a Bag(1 2) a Bag(1 2) false}

	Note that this definition of Dictionary>>= will discriminate between
	dictionaries that have the same values with different amount of
	occurrences (ie, it is stronger than self asSet = aDictionary asSet).
	
Yes, but it doesn't actually WORK.  If I wanted to compare dictionaries
as bags, I'd write the calls to asBag myself.

Here's my definition:

    Two indexed collections are equal if and only if
	(a) they are the same "kind"
        (b) they have the same set of keys
	(c) for each key, corresponding elements are the same.

We do NOT say that two arrays are equal if one is a permutation of
the other.  Try it!
    #(1 2) = #(2 1)
 => false

Why should we adopt a different criterion of dictionaries, when the
one I spelled out above gives the right answer for sequenceable collections
and an intuitively sensible answer for dictionaries?

As for why
    #(1 2) asBag = #(2 1) asBag
fails, that's because it inherits a definition of = from Object,
and that definition doesn't work for Bags.

Here's my proposal for Bag>> =

    Bag>>
    = aBag
        self class = aBag class ifFalse: [^false].
        self size = aBag size ifFalse: [^false].
	contents associationsDo: [:each |
	    (aBag occurrencesOf: each key) = each value
	        ifFalse: [^false]].
	^true

Ironically, what we really want to do here is just
	self class = aBag class and: [contents = aBag asDictionary]
with my definition of = for dictionaries.   Evidence, if more evidence
were needed, that a definition of = for dictionaries should look at the
keys.



More information about the Squeak-dev mailing list