15 ms·

The fact that slices cannot be used as keys in maps was, for me, a fairly big turn off.

jerf 14y ago
Using a slice as a key doesn't make much sense; a slice is a fundamentally-mutable view onto an underlying array, which itself may be mutable. Quick testing shows that you can use arrays: func main() { a := [4]int{1,2,3,4} m := make(map[[4]int]string) m[a] = "Hello" fmt.Println(m[[4]int{1,2,3,4}]) } Although that will be klunky, since the size of the array is in the type of the array. And still mutable. Mutating keys is bad. In all my years of using maps, I can't think of when I wanted to index by something that was truly an arbitrary-length array of things. If you want to index by something like a tuple of things, declare a datatype for that purpose. What exactly are you trying to do by using a slice as a key?
- omaranto 14y ago
  I was lazy when I complained about not be able to use slices as keys, I guess I really meant to complain that there is no arbitrary-length immutable sequence type that I can use as keys to a map (other than strings, which are sequences of characters and are allowed as keys to a map). For an example where you might want to do this consider storing a count of the frequency with which different words follow a given n-gram (sequence of n words) in some corpus, the sort of thing you'd need to make a Markov chain nonsense text generator (like the example programs in chapter 3 of The Practice of Programming: http://cm.bell-labs.com/cm/cs/tpop/code.html http://cm.bell-labs.com/cm/cs/tpop/code.html). Of course, you can always take your immutable sequences and represent them as strings, as other languages such as Perl, Awk and Lua force you to do. But I really like that I'm not forced to use such kludges in, say, Python or Haskell.
  - car54whereareu 14y ago
    http://play.golang.org/p/tLhF-JIRVv http://play.golang.org/p/tLhF-JIRVv forget using strings like Perl, Awk, and Lua.
    - omaranto 14y ago
      Sorry if I'm being stupid, but how does this solve the problem of using arbitrary/variable length sequences of, say, numbers as map keys?
      - cmccabe 14y ago
        Doing m[f(a)] = b is not that much less convenient than m[a] = b. You can wrap it in a function if it seems easier. If f() seems expensive, then you should reconsider whether you should be using a (hash) map at all (or use a struct and cache the key value in there.)
        omaranto 14y ago
        Just to be clear: you are not explaining how car54whereareu's code solves the problem of using arbitrary length sequences as keys, but rather explaining a different solution, right? car54whereareu's code, which uses structs as keys doesn't seem to me as if it would work for variable length sequences given Go's types. Your solution is what I had in mind when I said above you can concert your keys to strings. The way I see it there are two cases for m[f(a)]: 1. f is injective: this pretty much forces f to return a string, since it must return a data type that is allowed as a key and that can represent arbitrary length sequences without loss of information. 2. f is not injective: then we're using f as a hash function and we need to store the full key inside the value (i.e., m[f(a)]=pair(a,b)) so look ups can make equality checks for the key. You also need to handle f-collisions somehow (I just described disallowing keys with the same f, but that may not work for certain applications). You are basically writing your own hash table at this point.
        cmccabe 14y ago
        Based on my understanding, you're right-- you'd have to use a string to get a truly arbitrary length key. However, you can use interface types as I've commented above, which gives you some flexibility, but not truly arbitrary flexibility. If you want to tune for performance, you can always replace the convert-to-string code with something custom later. I've seen a few HashTable implementations in Go floating around on the internet.
  - jerf 14y ago
    This is a problem in a number of languages, in various guises. Generally you'll want the solution as outlined car54whereareu, but I don't deny that Go makes it harder to vary the type parameter than I'd like (it's easy to make a map with a 3-tuple key, easy to make a map with a 4-tuple key, not easy to pick between them without sacrificing type safety somewhere). It works almost exactly like Haskell, if you couldn't just say "a" for the key type of a map. And if you have no good way to label keys as immutable.
    - cmccabe 14y ago
      You can use interfaces types as the keys to a map. So you could easily have a map with both 3-tuples and 4-tuples as keys, just by having one struct with 3 elements and one with 4 implement the same interface and using that as the key. Of course, if you want a truly arbitrary length key, you'll probably have to use the convert-to-string trick.
  - juiceandjuice 14y ago
    A map is a hash table. I'm confused as to why you don't use either a custom hashing function or your own custom datatype that organizes your data according to the sequence order of your key. While a generic hashing function that can operate on any type of data could be implemented in the language, I believe the flexibility of defining the hashing function yourself is perfectly acceptable considering the performance implications of having a universal hash function. The reason why is this: The table lookup should fundamentally be roughly an O(1) operation after hashing your key value. A universal hashing function that operates on arbitrary-length immutable sequences would likely be an additional O(n) (where n is the length of the sequence) complexity built into the map structure. I don't believe that's acceptable from a language standpoint.
    - dsymonds 14y ago
      There's nothing stopping you writing your own hash map that can be configured with a custom hash function. The builtin map is limited to types for which the language defines ==. It's a simplifying trade-off; I don't think "acceptable" versus "unacceptable" enters into it. One could imagine expanding the builtin map type to support a hash function, and that was something that was considered early on, but it added complexity that just wasn't needed most of the time.
- deleted 14y ago
  [deleted]
- omaranto 14y ago
  Another application of arbitrary-length sequences is storing sparse multivariable polynomials as maps from monomials to coefficients.

jerf 14y ago

Using a slice as a key doesn't make much sense; a slice is a fundamentally-mutable view onto an underlying array, which itself may be mutable. Quick testing shows that you can use arrays: func main() { a := [4]int{1,2,3,4} m := make(map[[4]int]string) m[a] = "Hello" fmt.Println(m[[4]int{1,2,3,4}]) } Although that will be klunky, since the size of the array is in the type of the array. And still mutable. Mutating keys is bad. In all my years of using maps, I can't think of when I wanted to index by something that was truly an arbitrary-length array of things. If you want to index by something like a tuple of things, declare a datatype for that purpose. What exactly are you trying to do by using a slice as a key?

omaranto 14y ago
I was lazy when I complained about not be able to use slices as keys, I guess I really meant to complain that there is no arbitrary-length immutable sequence type that I can use as keys to a map (other than strings, which are sequences of characters and are allowed as keys to a map). For an example where you might want to do this consider storing a count of the frequency with which different words follow a given n-gram (sequence of n words) in some corpus, the sort of thing you'd need to make a Markov chain nonsense text generator (like the example programs in chapter 3 of The Practice of Programming: http://cm.bell-labs.com/cm/cs/tpop/code.html http://cm.bell-labs.com/cm/cs/tpop/code.html). Of course, you can always take your immutable sequences and represent them as strings, as other languages such as Perl, Awk and Lua force you to do. But I really like that I'm not forced to use such kludges in, say, Python or Haskell.
- car54whereareu 14y ago
  http://play.golang.org/p/tLhF-JIRVv http://play.golang.org/p/tLhF-JIRVv forget using strings like Perl, Awk, and Lua.
  - omaranto 14y ago
    Sorry if I'm being stupid, but how does this solve the problem of using arbitrary/variable length sequences of, say, numbers as map keys?
    - cmccabe 14y ago
      Doing m[f(a)] = b is not that much less convenient than m[a] = b. You can wrap it in a function if it seems easier. If f() seems expensive, then you should reconsider whether you should be using a (hash) map at all (or use a struct and cache the key value in there.)
      - omaranto 14y ago
        Just to be clear: you are not explaining how car54whereareu's code solves the problem of using arbitrary length sequences as keys, but rather explaining a different solution, right? car54whereareu's code, which uses structs as keys doesn't seem to me as if it would work for variable length sequences given Go's types. Your solution is what I had in mind when I said above you can concert your keys to strings. The way I see it there are two cases for m[f(a)]: 1. f is injective: this pretty much forces f to return a string, since it must return a data type that is allowed as a key and that can represent arbitrary length sequences without loss of information. 2. f is not injective: then we're using f as a hash function and we need to store the full key inside the value (i.e., m[f(a)]=pair(a,b)) so look ups can make equality checks for the key. You also need to handle f-collisions somehow (I just described disallowing keys with the same f, but that may not work for certain applications). You are basically writing your own hash table at this point.
        cmccabe 14y ago
        Based on my understanding, you're right-- you'd have to use a string to get a truly arbitrary length key. However, you can use interface types as I've commented above, which gives you some flexibility, but not truly arbitrary flexibility. If you want to tune for performance, you can always replace the convert-to-string code with something custom later. I've seen a few HashTable implementations in Go floating around on the internet.
- jerf 14y ago
  This is a problem in a number of languages, in various guises. Generally you'll want the solution as outlined car54whereareu, but I don't deny that Go makes it harder to vary the type parameter than I'd like (it's easy to make a map with a 3-tuple key, easy to make a map with a 4-tuple key, not easy to pick between them without sacrificing type safety somewhere). It works almost exactly like Haskell, if you couldn't just say "a" for the key type of a map. And if you have no good way to label keys as immutable.
  - cmccabe 14y ago
    You can use interfaces types as the keys to a map. So you could easily have a map with both 3-tuples and 4-tuples as keys, just by having one struct with 3 elements and one with 4 implement the same interface and using that as the key. Of course, if you want a truly arbitrary length key, you'll probably have to use the convert-to-string trick.
- juiceandjuice 14y ago
  A map is a hash table. I'm confused as to why you don't use either a custom hashing function or your own custom datatype that organizes your data according to the sequence order of your key. While a generic hashing function that can operate on any type of data could be implemented in the language, I believe the flexibility of defining the hashing function yourself is perfectly acceptable considering the performance implications of having a universal hash function. The reason why is this: The table lookup should fundamentally be roughly an O(1) operation after hashing your key value. A universal hashing function that operates on arbitrary-length immutable sequences would likely be an additional O(n) (where n is the length of the sequence) complexity built into the map structure. I don't believe that's acceptable from a language standpoint.
  - dsymonds 14y ago
    There's nothing stopping you writing your own hash map that can be configured with a custom hash function. The builtin map is limited to types for which the language defines ==. It's a simplifying trade-off; I don't think "acceptable" versus "unacceptable" enters into it. One could imagine expanding the builtin map type to support a hash function, and that was something that was considered early on, but it added complexity that just wasn't needed most of the time.
deleted 14y ago
[deleted]
omaranto 14y ago
Another application of arbitrary-length sequences is storing sparse multivariable polynomials as maps from monomials to coefficients.