4 ms·
I always have trouble explaining this limitation of Go maps. First, a string can point to an unlimited amount of data (i.e., it can be of arbitrary length) and
by omaranto 7y ago
I always have trouble explaining this limitation of Go maps.
First, a string can point to an unlimited amount of data (i.e., it can be of arbitrary length) and all of its characters are taken into account when deciding string equality.
Now, an array type in Go is not like that: the length of the array is part of the type. There is (or at least there wasn't when I last checked) no type of all arrays of ints, say, but there is a type of array of 5 ints, a type of arrays of 8 ints, etc. Each of those is of limited size.
A slice is like a string, it can point to an arbitrary amoun of data, but slices are not allowed as map keys.
A struct has a fixed number of members and is only allowed as a map key if all of its members are of types allowed as maps keys.
So a struct type that is allowed as a map key type can only point to unlimited data all used for equality if it contains directly or indirectly a string somewhere. Among types allowed as keys, the only source or arbitrary-sizedness are strings.
For example, if you want to represent multivariate polynomials sparsely as a map from exponent vector to coefficients (i.e., the polynomial 3x^2y^3-7xy^4 corresponds to the map {(2,3)=>3, (1,4)=>-7}) you can only do it in Go with the built-in maps awkwardly. You could pick a maximum number of variables and use arrays of exponents as keys. You can leave the number of variables arbitrary and convert exponent vectors to strings (i.e., use {"2,3"=>3, "1,4"=>-7}). I find it frustrating that those are my options.
- ainar-g 7y agoI see now, thanks. Existing maps will probably remain that way forever, but the new Generics Draft Design[1], if implemented, should allow people to easily write a wrapper that will work on anything. [1]: https://go.googlesource.com/proposal/+/58566e5309365c84587aedc5816344daad48ec27/design/go2draft-contracts.md https://go.googlesource.com/proposal/+/58566e5309365c84587ae...
- omaranto 7y agoFixing the existing maps sounds a lot easier than adding generics. All that would be required is to allow slices as keys. If there is a concern about immutability you could just say mutating a slice used as a key leads to undefined behavior.
- ainar-g 7y agoAFAIK, “undefined behaviour” is not a thing in Go The Language (there is some undefined behaviour in the Go The StdLib). The Go Specification[1] doesn't even contain the word “undefined”, and only has two instances of “unspecified”. I guess that if immutable slices became a thing, one would probably be able to use them as map keys. But so far the Go Team is very reluctant about adding immutability to the language. [1]: https://golang.org/ref/spec https://golang.org/ref/spec
- omaranto 7y agoLots of currently allowed map keys can be mutated such as structs or arrays. Let whatever happens when you mutate them (what does happen?) happen also for slices.
- ainar-g 7y agoUhm, no, they cannot be mutated. If you use a structure with two integers as a key and then change one of these integers, then you have a new value, and a new key, just like with integers.
- omaranto 7y agoThat didn't quite clear up for me what happens when you mutate keys, so I ran a quick experiment. It seems like maybe the map stores a copy of the key, as the map doesn't "see the mutation". package main import "fmt" func main() { x := [2]int{1, 2} m := make(map[[2]int]int) m[x] = 5 fmt.Println(m[x]) x[1] = 3 fmt.Println(m[x], m[[2]int{1, 2}], m[[2]int{1, 3}]) for k, v := range m { fmt.Println(k, v) } } This prints: 5 0 5 0 [1 2] 5 I'd be perfectly happy if slices were allowed as keys with the same semantics as arrays...