[Haskell-cafe] Pure hashtable library

Stephan Friedrichs deduktionstheorem at web.de
Wed Aug 27 05:52:23 EDT 2008

Bulat Ziganshin wrote:
> solving one more task that uses English dictionary, i've thought: why we
> don't yet have pure hashtable library? There is imperative hashtables,
> [...]
> how should it look:
> * hashtable is represented as an array of assoc lists: Array Int [(a,b)]

Don't immutable arrays get rather inefficient when modified?

> [...]

Just a tought: You might want to have a look at the bloom filter
implementation. On one hand, it is an alternative for your dictionary
and on the other and, its implementation uses hash functions and arrays
as well. IIRC it does that in a state monad that keeps the array mutable
and finally freezes it before usage, which might be a good idea for pure
hash table as well.



Früher hieß es ja: Ich denke, also bin ich.
Heute weiß man: Es geht auch so.

 - Dieter Nuhr

More information about the Haskell-Cafe mailing list