[Haskell-cafe] hash tables

[Frank Staals]

David Turner <dct25-561bs at mythic-beasts.com> writes:

> Hi Dennis,
>
> Data.HashMap [1] is my preferred way to do this, which avoids any mucking
> around in IO at all.
>
> If that doesn't work for you, funnily enough the function you're looking
> for may well be called `freeze` [2]
>
> [1]
> https://hackage.haskell.org/package/unordered-containers-0.2.7.2/docs/Data-HashMap-Strict.html
>
> [2]
> https://hackage.haskell.org/package/vector-0.12.0.0/docs/Data-Vector.html#v:freeze
>
> On 27 Jan 2017 05:18, "Dennis Raddle" <dennis.raddle at gmail.com> wrote:
>
> I want to build a hash table and then freeze it and use it for fast lookup
> later. Is there a way to build it in IO or ST but freeze it and use it in
> transparent code later?
> D

I've actually wanted this type of operations a few times as well, but
never really found a solution so far. The problem with just using
Data.HashMap is that it does not guarantee the desired query times
(although I'm guessing it would "work well in practice").

It would be awesome if there was some sort of cuckoo-hashing
implementation that you could build in ST (in expected O(n) time or so),
and then freeze as to get O(1) worst case (guaranteed) lookups in pure
code.

--

- Frank