Support of algebraic operations on dictionaries (was: ... sets)

Bert Freudenberg bert at freudenbergs.de
Sat Jun 16 10:52:53 UTC 2007


On Jun 16, 2007, at 11:25 , sig wrote:

> On 16/06/07, Bert Freudenberg <bert at freudenbergs.de> wrote:
>>
>> On Jun 16, 2007, at 9:10 , nicolas cellier wrote:
>> > So creating a HashedCollection above both Set and Dictionary would
>> > be an
>> > interesting alternative.
>>
>> Possibly, yes. The main reason for Dictionary to inherit from Set is
>> to reuse the hashing.
>>
>> The current inconsistencies come from Dictionary being a subclass of
>> Set, but not behaving as a proper Set. One manifestation of that is
>> #union: which relies on #asSet actually answering a collection with
>> Set semantics.
>
> A Set overrides a #union:, which is not using #asSet for this
> operation anymore.

I'm sorry, but apparently you don't get it. Compare #union: in  
Collection and Set. Set *has* to override this because Collection  
uses #asSet which is a no-op in Set. So instead of #asSet it uses  
#copy. The intent of #asSet in #union: is to get a variable-sized  
Collection with unique elements. Dictionary's behavior in response to  
#asSet violates that assumption.

>> Not having Dictionary be a Set subclass seems a lot cleaner to me
>> than trying to patch it up with more overrides.
>>
> Honestly i can't see what must be overriden in Dictionary to make it
> consistent with Set.
> It's all about Association, which makes Dictionary to not comform with
> sets semantics.

No, it's because Dictionary is a Collection. Indices or keys in a  
Collection are secondary. Look at the protocols in Collection - it  
does neither define nor use #at:.

> Maybe it's because i considering a Dictionary as set of keys with
> associated values instead of collection of arbitrary elements, where
> each one of them having unique key.

This is not unreasonable, but it is *not* what Dictionaries in  
Smalltalk are. You want, in your own words, a "set of keys with  
associated values". So use it instead of a Dictionary! Have a Set of  
LookupKeys then. Or even better, rather than in these oversimplified  
examples, reify your concept - for language translation have a  
TranslationEntry class that implements #= and #hash based on the  
original word and use a Set to store them.

Let me put it this way: The main property of Sets is that its  
elements are unique. The invariant would be

	aSet allSatisfy: [:element | (aSet occurrencesOf: element) = 1]

This indeed holds for each Set, but not for Dictionaries - you can  
have the same value multiple times.

So please, to get this discussion to a fruitful end, let's fix  
Dictionaries, but not redefine their semantics to suit your specific  
needs. Maybe using Nicholas' suggestion (which I find cleaner but has  
potentially more severe consequences) or by patching up Dictionary,  
in this case by overriding #asSet.

- Bert -





More information about the Squeak-dev mailing list