Я ищу запрос без монады, постоянный доступO (1) ассоциативный массив.

Рассмотрим гипотетический тип:

data HT k v = ???

Я хочу построить неизменную структуру один раз:

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

Я хочу впоследствии запросить его несколько раз с постоянным временем доступа ::

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

Похоже, есть две библиотеки-кандидаты, которые не отвечают требованиям:

unordered-containers

hashtables

unordered-containers содержит как строгие, так и ленивые варианты типаHashMap, И то и другоеHashMapсO (log n) запросы, как документированоlookup функция. Это время доступа к запросу, по-видимому, связано с созданиемHashMap типы, которые имеют внутреннюю структуру дерева, позволяющуюO (log n) insert функциональность. Понятный дизайн компромисс для многих вариантов использования, но так как мне не нужен изменяемыйHashMap этот компромисс мешает моему варианту использования.

hashtables содержитHashTable класс типов и три типа экземпляров с различными стратегиями построения таблиц. Тип-класс этой библиотеки определяет постоянное времяO (1) lookup определение функции, но оно вечно встроено вST монада. Нет возможности "заморозить" государствоHashTable реализации и имеютlookup функция, которая не встроена в монаду с состоянием. Интерфейс класса типов библиотеки хорошо спроектирован, когда все вычисления заключены в монаду состояний, но этот дизайн не подходит для моего варианта использования.

Существует ли какая-то другая библиотека, которая определяет типы и функции, которые могут создавать неизменяемый запрос постоянного доступаO (1) ассоциативный массив, который не встроен в монаду с состоянием?

Существует ли какой-либо способ обернуть или изменить эти существующие библиотеки на основе хеширования для создания неизменяемого запроса с постоянным доступомO (1) ассоциативный массив, который не встроен в монаду с состоянием?