5 ms·

I haven't been keeping up with Go. Is it still the case that the only datatype than can be used as keys to a map and is not of a fixed size is string?

ainar-g 7y ago
I'm not sure what you're talking about. Map keys in Go can be strings, numbers, pointers, some structs, etc. And that was the case since at least Go 1.0.
- 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 ago
    I 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 ago
      Fixing 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 ago
        AFAIK, “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 ago
        Lots 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 ago
        Uhm, 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.
nemo1618 7y ago
Strings are fixed-size, though. A string is a pointer and a length. It's true that you can't use a slice as a map key, though, even though slices are also fixed-size (pointer, length, and capacity). As I recall, the argument is that the equality rules for slices are unclear. (maps and funcs can't be used as keys either, for the same reason: they're not comparable.) Is a 0-length slice equal to a nil slice? Is a slice with len 3, cap 3 equal to a slice with len 3, cap 4? In practice, this is rarely a problem. It most commonly comes up when you want to use []byte as a key, in which case you can convert the []byte to a string. This overhead of this conversion (specifically when it occurs in the context of a map key) has been optimized away for a few versions now.
- omaranto 7y ago
  Maybe "fixed size" was the wrong way to phrase it. What I meant is that a string points to an unlimited amount of data and all of that unlimited amount of data is taken into account when deciding equality of strings. And my question should have been, is string the only datatype with that feature? If it is, it means Go is like Lua, where if you want to use any compound data structure as a key in a map, you either marshall it to a string or you implement your own hashtable. In Python you are allowed to use tuples of immutable objects as keys, for example. Much nicer than serializing everything to strings. As for "in practice this is rarely a problem", I agree, but prefer languages where the standard library doesn't have these arbitrary limitations. For example I might want to implement multivariate sparse polynomials as maps from exponent tuples to coefficients (the polynomial 3 x^2 y^3 z + 7 x y z^4 corresponds to the map {(2,3,1): 3, (1,1,4): 7}). That's straightforward in Python but awkward in Go (in Go I might be tempted to just set a maximum number of variables and use arrays or exponents as keys).
  - tapirl 7y ago
    > In Python you are allowed to use tuples of immutable objects as keys You can do this in Go too with structs.
    - bakery2k 7y ago

ainar-g 7y ago

I'm not sure what you're talking about. Map keys in Go can be strings, numbers, pointers, some structs, etc. And that was the case since at least Go 1.0.

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 ago
  I 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 ago
    Fixing 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 ago
      AFAIK, “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 ago
        Lots 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 ago
        Uhm, 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.

nemo1618 7y ago

Strings are fixed-size, though. A string is a pointer and a length. It's true that you can't use a slice as a map key, though, even though slices are also fixed-size (pointer, length, and capacity). As I recall, the argument is that the equality rules for slices are unclear. (maps and funcs can't be used as keys either, for the same reason: they're not comparable.) Is a 0-length slice equal to a nil slice? Is a slice with len 3, cap 3 equal to a slice with len 3, cap 4? In practice, this is rarely a problem. It most commonly comes up when you want to use []byte as a key, in which case you can convert the []byte to a string. This overhead of this conversion (specifically when it occurs in the context of a map key) has been optimized away for a few versions now.

omaranto 7y ago
Maybe "fixed size" was the wrong way to phrase it. What I meant is that a string points to an unlimited amount of data and all of that unlimited amount of data is taken into account when deciding equality of strings. And my question should have been, is string the only datatype with that feature? If it is, it means Go is like Lua, where if you want to use any compound data structure as a key in a map, you either marshall it to a string or you implement your own hashtable. In Python you are allowed to use tuples of immutable objects as keys, for example. Much nicer than serializing everything to strings. As for "in practice this is rarely a problem", I agree, but prefer languages where the standard library doesn't have these arbitrary limitations. For example I might want to implement multivariate sparse polynomials as maps from exponent tuples to coefficients (the polynomial 3 x^2 y^3 z + 7 x y z^4 corresponds to the map {(2,3,1): 3, (1,1,4): 7}). That's straightforward in Python but awkward in Go (in Go I might be tempted to just set a maximum number of variables and use arrays or exponents as keys).
- tapirl 7y ago
  > In Python you are allowed to use tuples of immutable objects as keys You can do this in Go too with structs.
  - bakery2k 7y ago