Does a useful Haskell HashMap/HashTable/Dictionary library exist?
<p>I'm looking for a monad-free, constant access query <em>O(1)</em> associative array.</p>

<p>Consider the hypothetical type:</p>

<pre><code>data HT k v = ???
</code></pre>

<p>I want to construct an immutable structure once:</p>

<pre><code>fromList :: Foldable t, Hashable k =&gt; t (k,v) -&gt; HT k v
</code></pre>

<p>I want to subsequently query it repeatedly with constant time access::</p>

<pre><code>lookup :: Hashable k =&gt; HT k v -&gt; k -&gt; Maybe v
</code></pre>

<p>There appears to be two candidate libraries which fall short:</p>

<ul>
<li><p><a href="https://hackage.haskell.org/package/unordered-containers" rel="noreferrer"><code>unordered-containers</code></a></p></li>
<li><p><a href="https://hackage.haskell.org/package/hashtables" rel="noreferrer"><code>hashtables</code></a></p></li>
</ul>

<h3><code>unordered-containers</code></h3>

<p><code>unordered-containers</code> contains both strict and lazy variants of the type <code>HashMap</code>. Both <code>HashMap</code>s have <em>O(log n)</em> queries as documented by the <a href="https://hackage.haskell.org/package/unordered-containers-0.2.7.1/docs/Data-HashMap-Lazy.html#v:lookup" rel="noreferrer"><code>lookup</code></a> function. This query access time appears to be due to the construction of the <code>HashMap</code> types, which have an internal tree structure allowing for <em>O(log n)</em> <a href="https://hackage.haskell.org/package/unordered-containers-0.2.7.1/docs/Data-HashMap-Lazy.html#v:insert" rel="noreferrer"><code>insert</code></a> functionality. An understandable design trade off for many use-cases, but since I don't need a mutable <code>HashMap</code> this tradeoff hampers my use-case.</p>

<h3><code>hashtables</code></h3>

<p><code>hashtables</code> contains a <code>HashTable</code> type-class and three instance types with varying table constructions strategies. This library's type-class defines a constant time <em>O(1)</em> <a href="https://hackage.haskell.org/package/hashtables-1.2.1.0/docs/Data-HashTable-Class.html#v:lookup" rel="noreferrer"><code>lookup</code></a> function definition, but it is eternally embedded in the <code>ST</code> monad. There is no way to "freeze" the stateful <code>HashTable</code> implementations and have a <code>lookup</code> function that is not embedded of a stateful monad. The library's type-class interface is well designed when the entire computation is wrapped in a state monad, but this design is unsuitable for my use-case.</p>

<hr>

<p>Does there exist some other library which defines types and functions which can construct an immutable constant access query <em>O(1)</em> associative array that is not embedded in a stateful monad?</p>

<p>Does there exist some way to wrap or modify these existing hashing-based libraries to produce an immutable constant access query <em>O(1)</em> associative array that is not embedded in a stateful monad?</p>