Support of algebraic operations on sets

sig siguctua at
Sun Jun 17 19:56:42 UTC 2007

> Ok I see and this is where Bert's point about #do: comes in.  Since #do:
> iterates over values and not keys your suggested include doesn't work.  Your
> suggestion is that #do iterate over associations is so that #= can compare
> keys and forget about values.
> The #= message on dictionary is not a major concern for me.  Although
> Dictionary new at: #a put #b; yourself = Dictionary new at: #a put: #c;
> yourself   seems odd to me, even if I do see the use in set operations.  The
> set operational consistency also does not seem very useful either.
> Certainly no more useful then the current implementation of #= on
> Dictionary.  I would suggest that we do not change #= for the sake of set
> operational consistency and would agree with Bert that Dictionaries are not
> sets.

Well, maybe its because i currently solving a problems where a set
operations on dictionaries is much more useful to me, so i tend to
state that they having much higher value than simple #= :)
Btw, using set operations we can simply implement equality for sets
(and dictionaries) as following:
Set>>= anObject
"two sets considered equal if their symmetric difference is an empty set"
^ (self difference: anObject) isEmpty and: [ (anObject difference:
self) isEmpty ]

Which is strictly based on mathematic laws and having zero chances to
be changed for the rest of the days. You might say its not optimal for
speed, but this is another story.

> Changing #do: is a major concern for me.  There is a huge amount of value to
> iteration over values and therefore we can predict a lot of people have used
> it in their code.  This form of iteration makes Dictionary consistent with
> Collection.  Again it is not consistent with Set operations but I don't see
> the value of set operations on dictionaries since only the keys are sets.  I
> don't see these relationships of keys to sets translating into dictionaries
> are sets.  We expect to find only one entry per index on a dictionary, but
> this is true of collections too.

1st: a current #do: is _NOT_ consistent with Collection, as i showed
before, following code will fail with dictionary:

elem := a -> b.
dict add: elem.
assert: [ dict includes: elem].

2nd: as Bert notes, Collections don't introduce index at all. There's
no #at: , #at:put: in Collection. Collections introducing basic
methods (like #do:) which used for iterating through all of its items,
which actually states that any collection must know how iterate
through own items, but there's nothing about how these items are
stored/accessed or how they are indexed.
And then, based on this method, we having a number of methods which
use this property of collection, like #includes: e.t.c.

> Changing Dictionary must be done extremely carefully, I would vote against
> changing it to support set operations.
> (I still like my suggestion of collection of values resulting from set
> operations but that's me).
> I don't see that this precludes you from doing what you need to do.  If we
> change the superclass of Dictionary to be Collection or HashedCollection as
> was suggested then you could then add your set methods implemented the way
> you want them.  Maybe something like #asSetSymetricDifference: or
> #asSetIncludes:  With a nice comment that says something like "The
> comparisons for equality in set operations only consider keys so that the
> resulting set matches algebraic rules.  For example #asSetUnion: results are
> commutative using #asSetEquals.  Set operations can result in unexpected
> differences in the values of your resulting dictionary since only keys are
> used for set operations.  Set operations may throw out your values.  For
> example ..."

If you can see, the changes need to make for Dictionary to make it
conform with what i proposing is much less to what you proposing. But
yes , the amount of code which uses old semantics is paramount.
So, its better to create a new class then, because adding new methods
in Dictionary does not solves problems, but just makes Dictionary
having even less consistent and dirty protocol(s).

> Come to think of it we could just implement the set operations as
> #shouldNotImplement and we can replace that functionality with the methods
> above.
> Dictionaries are widely used in Smalltalk, too much so in my opinion (I'm as
> guilty as anyone).  In many cases modeling your dictionary into proper
> objects eliminates a shortcut but provides greater clarity to your model.

> Happy coding!

More information about the Squeak-dev mailing list