From: Hans Aberg
On 28 Jan 2010, at 20:07, Steve Schafer wrote:
The data are currently in a large lookup table. To save space, I'd like to convert that into a sort of hash function:
hash :: key -> value
My question is this: Is there any kind of generic approach that can make use of the knowledge about the internal redundancy of the keys to come up with an efficient function?
There are minimal perfect hash functions; there are some libraries mentioned here, though they are not in Haskell code: http://en.wikipedia.org/wiki/Perfect_hash_function
This is suitable when you do a lot of lookups with few key updates. An alternative might be Data.Map, where lookups have time complexity O(log n), n = size of map.
The minimal perfect hash function looks like the real algorithmic solution, but I would just use Data.IntMap for this. Cheers, John