# Support of algebraic operations on sets

63 messages
1234
Open this post in threaded view
|

## 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?
Open this post in threaded view
|

## 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 -
Open this post in threaded view
|

## 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? 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 -
Open this post in threaded view
|

## 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 -
Open this post in threaded view
|

## 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 )
Open this post in threaded view
|

## 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 -
Open this post in threaded view
|

## 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 )
Open this post in threaded view
|

## 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 - > > > >
Open this post in threaded view
|

## 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 - > > > >
Open this post in threaded view
|

## 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 - > > > >
Open this post in threaded view
|

## 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 -
Open this post in threaded view
|

## 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 -
Open this post in threaded view
|

## 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.
Open this post in threaded view
|

## 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.
Open this post in threaded view
|

## 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.
Open this post in threaded view
|

## 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 - > > > >
Open this post in threaded view
|

## 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. > >
Open this post in threaded view
|

## 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 -
Open this post in threaded view
|

## 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 - > >