Estou procurando uma consulta de acesso constante e sem mônadaO (1) matriz associativa.

Considere o tipo hipotético:

data HT k v = ???

Eu quero construir uma estrutura imutável uma vez:

fromList :: Foldable t, Hashable k => t (k,v) -> HT k v

Desejo consultá-lo posteriormente repetidamente com acesso em tempo constante:

lookup :: Hashable k => HT k v -> k -> Maybe v

Parece haver duas bibliotecas candidatas que ficam aquém:

unordered-containers

hashtables

unordered-containers contém variantes estritas e preguiçosas do tipoHashMap. AmbosHashMapbarbearO (log n) consultas conforme documentado pelolookup função. Esse tempo de acesso à consulta parece dever-se à construção doHashMap tipos, que possuem uma estrutura em árvore interna que permiteO (log n) insert funcionalidade. Um design compreensível para muitos casos de uso, mas como não preciso de um mutávelHashMap essa troca dificulta meu caso de uso.

hashtables contém umHashTable classe de tipo e três tipos de instância com estratégias variadas de construção de tabela. A classe de tipo desta biblioteca define um tempo constanteO (1) lookup definição de função, mas está eternamente embutida noST mônada. Não há como "congelar" o estadoHashTable implementações e ter umlookup função que não é incorporada de uma mônada com estado. A interface de classe de tipo da biblioteca é bem projetada quando toda a computação é agrupada em uma mônada de estado, mas esse design é inadequado para o meu caso de uso.

Existe alguma outra biblioteca que define tipos e funções que podem construir uma consulta de acesso constante imutávelO (1) matriz associativa que não está incorporada em uma mônada com estado?

Existe alguma maneira de agrupar ou modificar essas bibliotecas existentes baseadas em hash para produzir uma consulta de acesso constante imutávelO (1) matriz associativa que não está incorporada em uma mônada com estado?