I wrote:
Perhaps Data.HashTable is what you are looking for then?
Jerzy Karczmarczuk wrote:
extract from Data.Hash what you need... why not try tries?
apfelmus wrote:
There's always Data.Map
Those are log n. I would personally use those for almost every application, but Mike says he wants constant time, for a compiler. Apparantly he wants to do some really serious optimization. HashTable is highly optimized. Of course, any memory access is really no better than log n, but HashTable uses the built-in parallelization available on most hardware that makes it look like constant time up to the size of system memory. (Otherwise known as accessing memory locations by address.) So yes, using this hardware has side effects and needs to be in IO. You could do it in the ST monad instead of the IO monad if you want, if that is any consolation. -Yitzchak -Yitz