3 ms·

Thanks for answering. You're right, but in my case, I was adapting http://norvig.com/spell-correct.html http://norvig.com/spell-correct.html, and the set operat

by swah 14y ago

Thanks for answering. You're right, but in my case, I was adapting http://norvig.com/spell-correct.html http://norvig.com/spell-correct.html, and the set operation (constructor, actually) was exactly what I needed. Of course, it was simple to write a removeDuplicates fn that inserted elements from the array to a map, and back to an array. But that is the point of my parent comment... :) Once, while writing something in Java, I found out that I needed a Multiset (didn't knew the term) and that Java had a implementation. As strange as it sounds, that made me very productive and confident my code was working... (Of course, soon you're writing getters and setters and hating Java again..)

burntsushi 14y ago
Ah, I see. What if you represented a multiset as a map just like in my parent comment, but with integers instead of booleans? type Set map[string]int // Add to set set["element"]++ // Remove from set s[el] = max(0, s[el]-1) // Membership s[el] > 0 Here's a working example: http://play.golang.org/p/zMvVF1yERc http://play.golang.org/p/zMvVF1yERc N.B. This is a fiendish way of making good use of "zero" values in Go.
- swah 14y ago
  It seems you're just counting ocurrences? The Multiset actually stores them IIRC. So to me it seems the Set type should be map[string][]type_of_elem, if that is possible. [edit] I'm confusing Multiset with Multimap... sorry. [note] Actually Multimap/Mutliset is not shipped with Java, but from Google... So it's not that "included".
  - burntsushi 14y ago
    > It seems you're just counting ocurrences? Yeah. Remember, a multi-set is just a bag. If the bag is `{a, b, a, a, b}`, then it can also be represented as a simple frequency vector: `{a: 3, b: 2}`. There's no need to actually store duplicate values. > So to me it seems the Set type should be map[string][]type_of_elem, if that is possible. OK, now I see. It depends on what your definition of equality is. If the entire value represents identity, then my solution works. But if only part of your value (say, some but not all fields in a struct) represents identity, then my approach won't work at all. My approach relies on Go's built in definition of equality, which isn't flexible and cannot be changed. For instance, if you're storing values with this type in your set: type MyValue struct { Id int Tag string } And these two values are equivalent: MyValue{5, "abc"} MyValue{5, "xyz"} Then you'd have to roll your own implementation. (Since in the eyes of Go, these two values are not equal. And that cannot be changed.) There are elegant ways around this, but it is certainly more clumsy in Go than it would be in a language with some sort of ad hoc polymorphism (like overloading in Java or type classes in Haskell). I think your idea is pretty close: type MultiSet map[MyValueIdentity][]MyValue type MyValueIdentity int Anyway, best of luck to you. Don't be afraid to drop by the #go-nuts channel on IRC. We're a friendly bunch :-)

by swah 14y ago

burntsushi 14y ago

Ah, I see. What if you represented a multiset as a map just like in my parent comment, but with integers instead of booleans? type Set map[string]int // Add to set set["element"]++ // Remove from set s[el] = max(0, s[el]-1) // Membership s[el] > 0 Here's a working example: http://play.golang.org/p/zMvVF1yERc http://play.golang.org/p/zMvVF1yERc N.B. This is a fiendish way of making good use of "zero" values in Go.

swah 14y ago
It seems you're just counting ocurrences? The Multiset actually stores them IIRC. So to me it seems the Set type should be map[string][]type_of_elem, if that is possible. [edit] I'm confusing Multiset with Multimap... sorry. [note] Actually Multimap/Mutliset is not shipped with Java, but from Google... So it's not that "included".
- burntsushi 14y ago
  > It seems you're just counting ocurrences? Yeah. Remember, a multi-set is just a bag. If the bag is `{a, b, a, a, b}`, then it can also be represented as a simple frequency vector: `{a: 3, b: 2}`. There's no need to actually store duplicate values. > So to me it seems the Set type should be map[string][]type_of_elem, if that is possible. OK, now I see. It depends on what your definition of equality is. If the entire value represents identity, then my solution works. But if only part of your value (say, some but not all fields in a struct) represents identity, then my approach won't work at all. My approach relies on Go's built in definition of equality, which isn't flexible and cannot be changed. For instance, if you're storing values with this type in your set: type MyValue struct { Id int Tag string } And these two values are equivalent: MyValue{5, "abc"} MyValue{5, "xyz"} Then you'd have to roll your own implementation. (Since in the eyes of Go, these two values are not equal. And that cannot be changed.) There are elegant ways around this, but it is certainly more clumsy in Go than it would be in a language with some sort of ad hoc polymorphism (like overloading in Java or type classes in Haskell). I think your idea is pretty close: type MultiSet map[MyValueIdentity][]MyValue type MyValueIdentity int Anyway, best of luck to you. Don't be afraid to drop by the #go-nuts channel on IRC. We're a friendly bunch :-)