Smalltalk › Squeak › Squeak - Dev

Support of algebraic operations on sets

_‹ Previous Topic Next Topic _›

Classic

List

Threaded

63 messages Options

1234

Igor Stasenko

Support of algebraic operations on sets

I would like to ask community, why there's no methods in Set class
which support macro operations with sets like
intersection/subtraction.
There's only a #union: method, in my 3.8 , and i wonder, why there's
no #intersect: and #subtract: ?
These are common algebraic operations on sets, and i really missing
them: i have to modify one set by comparing it with another and
add/remove elements based on this comparison. Currently i forced to
implement intersection/subtraction operations each time i need them,
but i would really like to see these operations in standard Set
protocol.

Or, if someone knows, please describe the reasons why these operations
was not included in standard Set protocol?

Bert Freudenberg

Re: Support of algebraic operations on sets

On Jun 15, 2007, at 13:24 , sig wrote:

> I would like to ask community, why there's no methods in Set class
> which support macro operations with sets like
> intersection/subtraction.
> There's only a #union: method, in my 3.8 , and i wonder, why there's
> no #intersect: and #subtract: ?
> These are common algebraic operations on sets, and i really missing
> them: i have to modify one set by comparing it with another and
> add/remove elements based on this comparison. Currently i forced to
> implement intersection/subtraction operations each time i need them,
> but i would really like to see these operations in standard Set
> protocol.
>
> Or, if someone knows, please describe the reasons why these operations
> was not included in standard Set protocol?

Because they are included in the standard Collection protocol, no
special need to implement them for Sets:

#(1 2 3) asSet union: #(3 4 5) asSet "a Set(1 2 3 4 5)"

#(1 2 3) asSet intersection: #(3 4 5) asSet "a Set(3)"

#(1 2 3) asSet difference: #(3 4 5) asSet "a Set(1 2)"

You should start using the protocol browser.

- Bert -

Gary Chambers-4

RE: Support of algebraic operations on sets

Note that #difference: is the relative complement of the two sets, rather
than the symmetric difference.
Perhaps we could have a method for that too!

-----Original Message-----
From: [hidden email]
[mailto:[hidden email]] On Behalf Of Bert
Freudenberg
Sent: 15 June 2007 12:32 pm
To: sig
Cc: The general-purpose Squeak developers list
Subject: Re: Support of algebraic operations on sets

On Jun 15, 2007, at 13:24 , sig wrote:

> I would like to ask community, why there's no methods in Set class
> which support macro operations with sets like
> intersection/subtraction. There's only a #union: method, in my 3.8 ,
> and i wonder, why there's no #intersect: and #subtract: ?
> These are common algebraic operations on sets, and i really missing
> them: i have to modify one set by comparing it with another and
> add/remove elements based on this comparison. Currently i forced to
> implement intersection/subtraction operations each time i need them,
> but i would really like to see these operations in standard Set
> protocol.
>
> Or, if someone knows, please describe the reasons why these operations
> was not included in standard Set protocol?

Bert Freudenberg

Re: Support of algebraic operations on sets

On Jun 15, 2007, at 13:52 , Gary Chambers wrote:

> Note that #difference: is the relative complement of the two sets,
> rather
> than the symmetric difference.
> Perhaps we could have a method for that too!

IMHO that's not nearly as universally useful as the other operations.
Has anybody ever missed it before? We're not talking about Set theory
but actual usefulness as a general Collection protocol.

- Bert -

Igor Stasenko

Re: Support of algebraic operations on sets

In reply to this post by Gary Chambers-4

On 15/06/07, Gary Chambers <[hidden email]> wrote:
> Note that #difference: is the relative complement of the two sets, rather
> than the symmetric difference.
> Perhaps we could have a method for that too!
>

no, its perfectly fits with algebraic form.
a symmetric difference can be implemented easily:

(a diff: b) union: (b diff:a)
or:
(a union: b) diff: ( a intersection: b )

Gary Chambers-4

RE: Support of algebraic operations on sets

In reply to this post by Bert Freudenberg

Yes, I've missed it! Think "things that are here now as opposed to then".

-----Original Message-----
From: [hidden email]
[mailto:[hidden email]] On Behalf Of Bert
Freudenberg
Sent: 15 June 2007 1:21 pm
To: The general-purpose Squeak developers list
Subject: Re: Support of algebraic operations on sets

On Jun 15, 2007, at 13:52 , Gary Chambers wrote:

> Note that #difference: is the relative complement of the two sets,
> rather
> than the symmetric difference.
> Perhaps we could have a method for that too!

IMHO that's not nearly as universally useful as the other operations.
Has anybody ever missed it before? We're not talking about Set theory
but actual usefulness as a general Collection protocol.

- Bert -

Gary Chambers-4

RE: Support of algebraic operations on sets

In reply to this post by Igor Stasenko

Indeed. Whay not have a method that does that in Collection then?
Write once, use many times!

-----Original Message-----
From: [hidden email]
[mailto:[hidden email]] On Behalf Of sig
Sent: 15 June 2007 1:40 pm
To: The general-purpose Squeak developers list
Subject: Re: Support of algebraic operations on sets

On 15/06/07, Gary Chambers <[hidden email]> wrote:
> Note that #difference: is the relative complement of the two sets,
> rather than the symmetric difference. Perhaps we could have a method
> for that too!
>

no, its perfectly fits with algebraic form.
a symmetric difference can be implemented easily:

(a diff: b) union: (b diff:a)
or:
(a union: b) diff: ( a intersection: b )

Igor Stasenko

Re: Support of algebraic operations on sets

In reply to this post by Bert Freudenberg

actually i missing these operations for dictionaries.
in current implementation if you diff/union on two dictionaries,
you'll find out that associations play role as set elements, not keys.

for dictionaries 'a difference: b' i get not exactly what i would expect.

On 15/06/07, Bert Freudenberg <[hidden email]> wrote:

> On Jun 15, 2007, at 13:52 , Gary Chambers wrote:
>
> > Note that #difference: is the relative complement of the two sets,
> > rather
> > than the symmetric difference.
> > Perhaps we could have a method for that too!
>
> IMHO that's not nearly as universally useful as the other operations.
> Has anybody ever missed it before? We're not talking about Set theory
> but actual usefulness as a general Collection protocol.
>
> - Bert -
>
>
>
>

Bert Freudenberg

Re: Support of algebraic operations on sets

In reply to this post by Gary Chambers-4

I don't get you example - isn't that a difference?

| then now new |
then := #(1 2 3).
now := #(1 2 3 4 5).
new := now difference: then.
new "#(4 5)"

- Bert -

On Jun 15, 2007, at 14:40 , Gary Chambers wrote:

> Yes, I've missed it! Think "things that are here now as opposed to
> then".
>
> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]] On Behalf Of
> Bert
> Freudenberg
> Sent: 15 June 2007 1:21 pm
> To: The general-purpose Squeak developers list
> Subject: Re: Support of algebraic operations on sets
>
>
> On Jun 15, 2007, at 13:52 , Gary Chambers wrote:
>
>> Note that #difference: is the relative complement of the two sets,
>> rather
>> than the symmetric difference.
>> Perhaps we could have a method for that too!
>
> IMHO that's not nearly as universally useful as the other operations.
> Has anybody ever missed it before? We're not talking about Set theory
> but actual usefulness as a general Collection protocol.
>
> - Bert -
>
>
>
>

Gary Chambers-4

RE: Support of algebraic operations on sets

How about...

| then now new |
then := #(1 2 3).
now := #(3 4 5).
new := now symetricDifference: then.
new "#(1 2 4 5)"

As in, "new" are the things that have changed.

-----Original Message-----
From: [hidden email]
[mailto:[hidden email]] On Behalf Of Bert
Freudenberg
Sent: 15 June 2007 2:38 pm
To: The general-purpose Squeak developers list
Subject: Re: Support of algebraic operations on sets

I don't get you example - isn't that a difference?

| then now new |
then := #(1 2 3).
now := #(1 2 3 4 5).
new := now difference: then.
new "#(4 5)"

- Bert -

On Jun 15, 2007, at 14:40 , Gary Chambers wrote:

Bert Freudenberg

Re: Support of algebraic operations on sets

In reply to this post by Igor Stasenko

On Jun 15, 2007, at 14:45 , sig wrote:

> actually i missing these operations for dictionaries.
> in current implementation if you diff/union on two dictionaries,
> you'll find out that associations play role as set elements, not keys.
>
> for dictionaries 'a difference: b' i get not exactly what i would
> expect.

Dictionaries are like other collections - a collection of
"elements" (the values). The keys are only interesting for accessing
- like indices on Arrays. #do: operates on the values. So does
#select:, and #difference:. You wouldn't expect #difference: on an
Array to work on its indices, would you?

- Bert -

Gary Chambers-4

RE: Support of algebraic operations on sets

I would expect difference, in this case, to have the common element taken
from "a" rather then "b", seeing as #difference: is non-commutative.

-----Original Message-----
From: [hidden email]
[mailto:[hidden email]] On Behalf Of Bert
Freudenberg
Sent: 15 June 2007 2:51 pm
To: The general-purpose Squeak developers list
Subject: Re: Support of algebraic operations on sets

On Jun 15, 2007, at 14:45 , sig wrote:

> actually i missing these operations for dictionaries.
> in current implementation if you diff/union on two dictionaries,
> you'll find out that associations play role as set elements, not keys.
>
> for dictionaries 'a difference: b' i get not exactly what i would
> expect.

Dictionaries are like other collections - a collection of
"elements" (the values). The keys are only interesting for accessing
- like indices on Arrays. #do: operates on the values. So does
#select:, and #difference:. You wouldn't expect #difference: on an
Array to work on its indices, would you?

- Bert -

Igor Stasenko

Re: Support of algebraic operations on sets

In reply to this post by Bert Freudenberg

On 15/06/07, Bert Freudenberg <[hidden email]> wrote:

>
> On Jun 15, 2007, at 14:45 , sig wrote:
>
> > actually i missing these operations for dictionaries.
> > in current implementation if you diff/union on two dictionaries,
> > you'll find out that associations play role as set elements, not keys.
> >
> > for dictionaries 'a difference: b' i get not exactly what i would
> > expect.
>
> Dictionaries are like other collections - a collection of
> "elements" (the values). The keys are only interesting for accessing
> - like indices on Arrays. #do: operates on the values. So does
> #select:, and #difference:. You wouldn't expect #difference: on an
> Array to work on its indices, would you?
>

Consider following example (union of two dictionaries):

| dict1 dict2 result1 result2 |
dict1 := Dictionary new.
dict2 := Dictionary new.
dict1 at: 1 put: 5.
dict2 at: 1 put: 6.

result1 := dict1 union: dict2.
result2 := dict2 union: dict1.

union defined as commutative operation fails in this example, because
result1<>result2.
it can be considered as commutative only in case if we taking
resulting keys into account, not values.
from this point same logics must be followed when doing
intersection/difference for dictionaries - take only keys into
account, not their associative values.

So, i'd expect 'dict1 difference: dict2' must return empty
dictionary, as well as
dict1 intersection: dict2 return non-empty dictionary.

Btw, all this is based on wrong semantics of Association '=' mehod,
which compares not only keys, but values also. This was discussed in
other topic before.

Gary Chambers-4

RE: Support of algebraic operations on sets

Indeed. Need to decide if keys are enough or association pairs are
necessary.
Personally, I'd take keys.

-----Original Message-----
From: [hidden email]
[mailto:[hidden email]] On Behalf Of sig
Sent: 15 June 2007 3:43 pm
To: The general-purpose Squeak developers list
Subject: Re: Support of algebraic operations on sets

On 15/06/07, Bert Freudenberg <[hidden email]> wrote:

>
> On Jun 15, 2007, at 14:45 , sig wrote:
>
> > actually i missing these operations for dictionaries.
> > in current implementation if you diff/union on two dictionaries,
> > you'll find out that associations play role as set elements, not
> > keys.
> >
> > for dictionaries 'a difference: b' i get not exactly what i would
> > expect.
>
> Dictionaries are like other collections - a collection of "elements"
> (the values). The keys are only interesting for accessing
> - like indices on Arrays. #do: operates on the values. So does
> #select:, and #difference:. You wouldn't expect #difference: on an
> Array to work on its indices, would you?
>

Consider following example (union of two dictionaries):

| dict1 dict2 result1 result2 |
dict1 := Dictionary new.
dict2 := Dictionary new.
dict1 at: 1 put: 5.
dict2 at: 1 put: 6.

result1 := dict1 union: dict2.
result2 := dict2 union: dict1.

union defined as commutative operation fails in this example, because
result1<>result2. it can be considered as commutative only in case if we
taking resulting keys into account, not values. from this point same logics
must be followed when doing intersection/difference for dictionaries - take
only keys into account, not their associative values.

So, i'd expect 'dict1 difference: dict2' must return empty dictionary, as
well as dict1 intersection: dict2 return non-empty dictionary.

Btw, all this is based on wrong semantics of Association '=' mehod, which
compares not only keys, but values also. This was discussed in other topic
before.

Gary Chambers-4

RE: Support of algebraic operations on sets

In reply to this post by Igor Stasenko

But the semantics of Association should probably be separate from the
semantics of Dictionary (no direct delegation).
Depends on your point of view.

-----Original Message-----
From: [hidden email]
[mailto:[hidden email]] On Behalf Of sig
Sent: 15 June 2007 3:43 pm
To: The general-purpose Squeak developers list
Subject: Re: Support of algebraic operations on sets

On 15/06/07, Bert Freudenberg <[hidden email]> wrote:

>
> On Jun 15, 2007, at 14:45 , sig wrote:
>
> > actually i missing these operations for dictionaries.
> > in current implementation if you diff/union on two dictionaries,
> > you'll find out that associations play role as set elements, not
> > keys.
> >
> > for dictionaries 'a difference: b' i get not exactly what i would
> > expect.
>
> Dictionaries are like other collections - a collection of "elements"
> (the values). The keys are only interesting for accessing
> - like indices on Arrays. #do: operates on the values. So does
> #select:, and #difference:. You wouldn't expect #difference: on an
> Array to work on its indices, would you?
>

Consider following example (union of two dictionaries):

| dict1 dict2 result1 result2 |
dict1 := Dictionary new.
dict2 := Dictionary new.
dict1 at: 1 put: 5.
dict2 at: 1 put: 6.

result1 := dict1 union: dict2.
result2 := dict2 union: dict1.

union defined as commutative operation fails in this example, because
result1<>result2. it can be considered as commutative only in case if we
taking resulting keys into account, not values. from this point same logics
must be followed when doing intersection/difference for dictionaries - take
only keys into account, not their associative values.

So, i'd expect 'dict1 difference: dict2' must return empty dictionary, as
well as dict1 intersection: dict2 return non-empty dictionary.

Btw, all this is based on wrong semantics of Association '=' mehod, which
compares not only keys, but values also. This was discussed in other topic
before.

Klaus D. Witzel

Re: Support of algebraic operations on sets

In reply to this post by Bert Freudenberg

On Fri, 15 Jun 2007 15:50:54 +0200, Bert Freudenberg wrote:

> On Jun 15, 2007, at 14:45 , sig wrote:
>
>> actually i missing these operations for dictionaries.
>> in current implementation if you diff/union on two dictionaries,
>> you'll find out that associations play role as set elements, not keys.
>>
>> for dictionaries 'a difference: b' i get not exactly what i would
>> expect.
>
> Dictionaries are like other collections - a collection of "elements"
> (the values). The keys are only interesting for accessing - like indices
> on Arrays. #do: operates on the values. So does #select:, and
> #difference:. You wouldn't expect #difference: on an Array to work on
> its indices, would you?

Good argument. And if some solves that by (aDict keys op: bDict keys) and
aDict's values are completely different from bDict values, no cDict can
hold the "correct" values unless cDict is empty under all circumstances ;-)

/Klaus

> - Bert -
>
>
>
>

Bert Freudenberg

Re: Support of algebraic operations on sets

In reply to this post by Gary Chambers-4

Actually, the only sensible thing would be to take the values IMHO.

- Bert -

On Jun 15, 2007, at 16:49 , Gary Chambers wrote:

> Indeed. Need to decide if keys are enough or association pairs are
> necessary.
> Personally, I'd take keys.
>
> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]] On Behalf Of
> sig
> Sent: 15 June 2007 3:43 pm
> To: The general-purpose Squeak developers list
> Subject: Re: Support of algebraic operations on sets
>
>
> On 15/06/07, Bert Freudenberg <[hidden email]> wrote:
>>
>> On Jun 15, 2007, at 14:45 , sig wrote:
>>
>>> actually i missing these operations for dictionaries.
>>> in current implementation if you diff/union on two dictionaries,
>>> you'll find out that associations play role as set elements, not
>>> keys.
>>>
>>> for dictionaries 'a difference: b' i get not exactly what i would
>>> expect.
>>
>> Dictionaries are like other collections - a collection of "elements"
>> (the values). The keys are only interesting for accessing
>> - like indices on Arrays. #do: operates on the values. So does
>> #select:, and #difference:. You wouldn't expect #difference: on an
>> Array to work on its indices, would you?
>>
> Consider following example (union of two dictionaries):
>
> | dict1 dict2 result1 result2 |
> dict1 := Dictionary new.
> dict2 := Dictionary new.
> dict1 at: 1 put: 5.
> dict2 at: 1 put: 6.
>
> result1 := dict1 union: dict2.
> result2 := dict2 union: dict1.
>
> union defined as commutative operation fails in this example, because
> result1<>result2. it can be considered as commutative only in case
> if we
> taking resulting keys into account, not values. from this point
> same logics
> must be followed when doing intersection/difference for
> dictionaries - take
> only keys into account, not their associative values.
>
> So, i'd expect 'dict1 difference: dict2' must return empty
> dictionary, as
> well as dict1 intersection: dict2 return non-empty dictionary.
>
> Btw, all this is based on wrong semantics of Association '=' mehod,
> which
> compares not only keys, but values also. This was discussed in
> other topic
> before.
>
>

Bert Freudenberg

Re: Support of algebraic operations on sets

In reply to this post by Igor Stasenko

On Jun 15, 2007, at 16:42 , sig wrote:

> On 15/06/07, Bert Freudenberg <[hidden email]> wrote:
>>
>> On Jun 15, 2007, at 14:45 , sig wrote:
>>
>> > actually i missing these operations for dictionaries.
>> > in current implementation if you diff/union on two dictionaries,
>> > you'll find out that associations play role as set elements, not
>> keys.
>> >
>> > for dictionaries 'a difference: b' i get not exactly what i would
>> > expect.
>>
>> Dictionaries are like other collections - a collection of
>> "elements" (the values). The keys are only interesting for accessing
>> - like indices on Arrays. #do: operates on the values. So does
>> #select:, and #difference:. You wouldn't expect #difference: on an
>> Array to work on its indices, would you?
>>
> Consider following example (union of two dictionaries):
>
> | dict1 dict2 result1 result2 |
> dict1 := Dictionary new.
> dict2 := Dictionary new.
> dict1 at: 1 put: 5.
> dict2 at: 1 put: 6.
>
> result1 := dict1 union: dict2.
> result2 := dict2 union: dict1.
>
> union defined as commutative operation fails in this example, because
> result1<>result2.
> it can be considered as commutative only in case if we taking
> resulting keys into account, not values.
> from this point same logics must be followed when doing
> intersection/difference for dictionaries - take only keys into
> account, not their associative values.
>
> So, i'd expect 'dict1 difference: dict2' must return empty
> dictionary, as well as
> dict1 intersection: dict2 return non-empty dictionary.
>
> Btw, all this is based on wrong semantics of Association '=' mehod,
> which compares not only keys, but values also. This was discussed in
> other topic before.

The actual problem here is that Dictionary is implemented as a
subclass of Set while it is no proper Set. If it wasn't, then the
#union: implementation in Collection would do The Right Thing. Of
course we'd need Dictionary>>asSet defined as "^self values asSet".

So IMHO what *should* happen is that #union: always answers a Set.

- Bert -

Ron Teitelbaum

RE: Support of algebraic operations on sets

In reply to this post by Bert Freudenberg

Hey where's symmetricDifference?

Ron Teitelbaum

> -----Original Message-----
> From: Bert Freudenberg
>
>
> Because they are included in the standard Collection protocol, no
> special need to implement them for Sets:
>
> #(1 2 3) asSet union: #(3 4 5) asSet "a Set(1 2 3 4 5)"
>
> #(1 2 3) asSet intersection: #(3 4 5) asSet "a Set(3)"
>
> #(1 2 3) asSet difference: #(3 4 5) asSet "a Set(1 2)"
>
> You should start using the protocol browser.
>
> - Bert -
>
>

Ron Teitelbaum

RE: Support of algebraic operations on sets

In reply to this post by Gary Chambers-4

I should have kept reading first! The reason I care about
symmetricDifference is that, way back when, I wrote a method to do this, and
spent more time trying to figure out what the name of the method should be
then it took to write the method! I knew it had a name but I had no idea
what it was.

Ron

> -----Original Message-----
> From: [hidden email] [mailto:squeak-dev-
> [hidden email]] On Behalf Of Gary Chambers
> Sent: Friday, June 15, 2007 9:49 AM
> To: 'The general-purpose Squeak developers list'
> Subject: RE: Support of algebraic operations on sets
>
> How about...
>
> | then now new |
> then := #(1 2 3).
> now := #(3 4 5).
> new := now symetricDifference: then.
> new "#(1 2 4 5)"
>
> As in, "new" are the things that have changed.
>
> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]] On Behalf Of Bert
> Freudenberg
> Sent: 15 June 2007 2:38 pm
> To: The general-purpose Squeak developers list
> Subject: Re: Support of algebraic operations on sets
>
>
> I don't get you example - isn't that a difference?
>
> | then now new |
> then := #(1 2 3).
> now := #(1 2 3 4 5).
> new := now difference: then.
> new "#(4 5)"
>
>
> - Bert -
>
> On Jun 15, 2007, at 14:40 , Gary Chambers wrote:
>
> > Yes, I've missed it! Think "things that are here now as opposed to
> > then".
> >
> > -----Original Message-----
> > From: [hidden email]
> > [mailto:[hidden email]] On Behalf Of
> > Bert
> > Freudenberg
> > Sent: 15 June 2007 1:21 pm
> > To: The general-purpose Squeak developers list
> > Subject: Re: Support of algebraic operations on sets
> >
> >
> > On Jun 15, 2007, at 13:52 , Gary Chambers wrote:
> >
> >> Note that #difference: is the relative complement of the two sets,
> >> rather
> >> than the symmetric difference.
> >> Perhaps we could have a method for that too!
> >
> > IMHO that's not nearly as universally useful as the other operations.
> > Has anybody ever missed it before? We're not talking about Set theory
> > but actual usefulness as a general Collection protocol.
> >
> > - Bert -
> >
> >
> >
> >
>
>
>

1234