Does a useful Haskell HashMap/HashTable/Dictionary library exist?

The library you want is… unordered-containers. Or just plain old Data.Map from containers, if you’d prefer.

The note in the unordered-containers documentation explains why you shouldn’t worry about the O(log n) time complexity for lookups:

Many operations have a average-case complexity of O(log n). The implementation uses a large base (i.e. 16) so in practice these operations are constant time.

This is a common practice with certain kinds of functional data structures because it allows good sharing properties while also having good time complexities. log₁₆ still produces very small numbers even for very large n, so you can almost always treat those complexities as “effectively constant time”.

If this is ever a bottleneck for your application, sure, go with something else, but I find that highly unlikely. After all, log₁₆(1,000,000) is a little under 5, so your lookup time is not going to grow very quickly. Processing all that data is going to take up much more time than the overhead of the lookup.

As always: profile first. If you somehow have a problem that absolutely needs the fastest possible hash map in the world, you might need an imperative hash map, but for every case I’ve ever had, the functional ones work just fine.

You should follow Alexis' suggestion and use unordered-containers. If you really want something that is guaranteed to have Θ(1) lookups, you can define your own frozen version of any of the hash table types from hashtables using unsafePerformIO, but this is not very elegant. For example:

module HT
    ( HT
    , fromList
    , lookup
    ) where

import qualified Data.HashTable.IO as H
import Data.Hashable (Hashable)
import Data.Foldable (toList)
import System.IO.Unsafe (unsafePerformIO)
import Prelude hiding (lookup)

newtype HT k v = HT (H.BasicHashTable k v)

fromList :: (Foldable t, Eq k, Hashable k) => t (k, v) -> HT k v
fromList = HT . unsafePerformIO . H.fromList . toList

lookup :: (Eq k, Hashable k) => HT k v -> k -> Maybe v
lookup (HT h) k = unsafePerformIO $ H.lookup h k

Both uses of unsafePerformIO above should be safe. For that is crucial that the HT is exported as an abstract type.

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

At this point in time, the answer is still no.

As of late-2019 there is an efficient IO-based hashtable package with decent benchmarks.

What you describe seems doable in the same way that pure, immutable Data.Array construction is possible. See Data.Array.Base for how this is achieved via unsafe* operators. A Data.Array is defined with a bound, and my initial thought is that a pure, immutable hashtable will potentially have GC problems if it's allowed to grow without bounds.