I'm trying to solve a Go language exercise which requires me to have a set. I can create a set type but why doesn't the language come with one?
Go, having come from Google, where Guava also originated, why didn't the language designers opt for adding support for fundamental data structures? Why force your users to create their own implementations for something so basic as a set?
One reason is that it is easy to create a set from map:
s := map[int]bool{5: true, 2: true}
_, ok := s[6] // check for existence
s[8] = true // add element
delete(s, 2) // remove element
Union
s_union := map[int]bool{}
for k, _ := range s1{
s_union[k] = true
}
for k, _ := range s2{
s_union[k] = true
}
Intersection
s_intersection := map[int]bool{}
if len(s1) > len(s2) {
s1, s2 = s2, s1 // better to iterate over a shorter set
}
for k,_ := range s1 {
if s2[k] {
s_intersection[k] = true
}
}
It is not really that hard to implement all other set operations.
false) will properly tell that. No need the comma-ok idiom for testing.
map[int]struct{} instead of bool, because an empty struct occupies 0 bytes in the memory. I've recently written a gist for this gist.github.com/bgadrian/cb8b9344d9c66571ef331a14eb7a2e80
Partly, because Go doesn't have generics (so you would need one set-type for every type, or fall back on reflection, which is rather inefficient).
Partly, because if all you need is "add/remove individual elements to a set" and "relatively space-efficient", you can get a fair bit of that simply by using a map[yourtype]bool (and set the value to true for any element in the set) or, for more space efficiency, you can use an empty struct as the value and use _, present = the_setoid[key] to check for presence.
map[T]struct{} instead of map[T]bool.
Another possibility is to use bit sets, for which there is at least one package or you can use the built-in big package. In this case, basically you need to define a way to convert your object to an index.
Like Vatine wrote: Since go lacks generics it would have to be part of the language and not the standard library. For that you would then have to pollute the language with keywords set, union, intersection, difference, subset...
The other reason is, that it's not clear at all what the "right" implementation of a set is:
There is a functional approach:
func IsInEvenNumbers(n int) bool {
if n % 2 == 0 {
return true
}
return false
}
This is a set of all even ints. It has a very efficient lookup and union, intersect, difference and subset can easily be done by functional composition.
A map does not have that problem, since you store something associated with the value.
+ for union, - for difference, * for intersection, <= for subset, >= for superset, = for equality, <> for inequality and in for membership. So in Go, it would be only a single new keyword -- in. On the other hand, Pascal's built-in sets only work on "ordinals"--that is, any type which has an underlying representation of an integer value of some size.
s[key] (as if s were a map[T]bool) instead of key in s.
n % 2 == 0?
pollute the language with keywords set, union, intersection, difference, subset, really? Beside set the rest are operations on sets, so they are functions.
container/list) are half-baked.