Hacker News Reader

Comment by omaranto | Hacker News Reader

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).

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.

View on HN

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.

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.

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.

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.

http://play.golang.org/p/tLhF-JIRVv forget using strings like Perl, Awk, and Lua.

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?

Yes you are right, using a struct for a key does not directly solve the variable length key problem. Until I read the article I didn't know you could use structs for keys, that's all, but thanks for expecting deeper thoughts.

Because of golang I'm starting to wonder just how many keys a person might want, and that's a different way of thinking for someone used to python or clojure.

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.)

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.

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.

Reply on news.ycombinator.com