[Haskell-cafe] Re: symbol type?

[Yitzchak Gale]

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