I'm trying to solve "The go programming lanaguage" exercise #1.4 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 ?
-
58hmmm. wondering why the negative votes ? I'm coming from the java world where we had a set almost right from the beginning, even without generics. So, I find this behavior a lil bizarre– anjanbDec 2, 2015 at 5:02
-
1Use this one: github.com/deckarep/golang-set– EricJan 26 at 4:20
4 Answers
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.
-
17Check for existence is simply indexing the map. Since if it's not in it, the zero value (which is
false
) will properly tell that. No need the comma-ok idiom for testing.– iczaDec 1, 2015 at 12:44 -
82It is more optimal to use
map[int]struct{}
instead ofbool
, because an empty struct occupies 0 bytes in the memory. I've recently written a gist for this gist.github.com/bgadrian/cb8b9344d9c66571ef331a14eb7a2e80 Jul 16, 2018 at 20:20 -
84That's not quite so easy. Just having to write that code everywhere you need to use a Set seems ridiculous to me these days. Collections support should be provided by any language. Think a better answer is that Go is not yet as mature. I'm sure there will be libraries to cover that soon enough.– StefMar 13, 2019 at 6:22
-
35Not easy nor intuitive. This is not a set, it is just a code pattern that behaves like a set. It is not a set since it doesn't store the data not provides operations as a set does. The correct answer is that GO doesn't have this functionality. Having a way to do something doesn't mean it is a reason not to have it. Dec 1, 2020 at 17:30
-
11
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.
-
75So if it doesn't have generics, how is the 'generic' map implemented at all? May 26, 2016 at 16:25
-
3@FerminSilva It's done by the compiler, using methods not directly accessible to developers.– VatineJun 6, 2016 at 16:43
-
45Note that if you want to save bytes, you can use
map[T]struct{}
instead ofmap[T]bool
.– emersionMay 24, 2017 at 9:00 -
8
-
29The usual answer for golang question: "Why provide a feature when you can rewrite it in just a few lines?". This is why something that can be done in 3 explicit lines in python (or many other languages) takes 50+ obscure lines in go. This is one of the reasons (along with single letter variables) why I hate reading go code. It's uselessly long, just doing with for loops what should be done by a clear, efficient and well tested properly named function. Go "spirit" is just throwing away 50 years of good software engineering practice with dubious justifications. Jul 8, 2021 at 11:34
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.
- Or you do a has-like approach like Dali showed.
A map does not have that problem, since you store something associated with the value.
-
2To handle buit-in sets, Pascal overloads a bunch of binary (two-argmnent) operators:
+
for union,-
for difference,*
for intersection,<=
for subset,>=
for superset,=
for equality,<>
for inequality andin
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.– kostixDec 1, 2015 at 16:03 -
39The fact that there are multiple ways to implement a set hasn't stopped many other languages from providing them.– augurarDec 2, 2015 at 7:29
-
1@kostix: Go could even use the syntax
s[key]
(as ifs
were amap[T]bool
) instead ofkey in s
.– musiphilAug 22, 2016 at 17:12 -
2
-
4I know this is 5 years old, but
pollute the language with keywords set, union, intersection, difference, subset
, really? Besideset
the rest are operations on sets, so they are functions.– foobarnaNov 3, 2020 at 11:50
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.
-
1I should note that I wrote the original version of the bitset package referenced above. Dec 1, 2015 at 20:46