Haskell hash implementation that does not live in the IO monad

Question

I am looking for a data structure that is a bit like Data.HashTable , but it is not burdened with the IO monad. At the moment I am using [(key, val)]. I would like the structure to be O (log n), where n is the number of key value pairs.

A structure is created infrequently compared to how often it needs to be read, and when it is built, I have all the key pairs available at the same time. String keys, if that matters.

It would be nice to know how much to abandon [(key, val)].

Answer 1

You might think:

• Data.Map

or alternatively

• Data.HashMap

The first is a standard container for storing and searching for items with keys in Haskell. The latter is a new library specifically optimized for key hashing.

A recent talk by Johan Tibell, Faster persistent data structures through hashing provides an overview, and Milan Straka's recent publication Haskell Symposium specifically describes the Data.Map structure and the hashmap package.

Answer 2

If you have all the key value pairs, you can consider the perfect hash function .

Benchmarking will tell you when to switch from a simple list.