Brad Larsen wrote:
I have considered using Data.IntMap to implement a sort of faux hash table, e.g., introduce a Hashable class, and then use an IntMap to lists of Hashable. The result would be a pure, persistent ``hash table''. In such a case, however, lookup/insert/delete operations would have average complexity logarithmic in the number of buckets.
I'll throw in an idea that has been nagging me about hash tables. You could have a list of hash tables of increasing size. On an insert collision in a smaller table all the entries get put into the next one up. For a lookup you would have to check all the tables until you find the hash. e.g. With three hash table in the list of these example sizes. Table size 2^2 = 2 probable entries before collision. 2^4 = 4 2^6 = 8 h..h ...h.....h.h...h h......h.......h....h...........h......h.h..........h........... I expect if it's any good it has already been done. Richard.