Реализация хеш-кода в Haskell, который не живет в монаде IO

Question

Я ищу структуру данных, которая немного похожа на Data.HashTable, но не обременена монадой ввода-вывода. На данный момент я использую [(key, val)]. Я хотел бы, чтобы структура O (log n), где n - количество пар ключ-значение.

Структура создается нечасто по сравнению с тем, как часто она должна читаться, и когда она создается, у меня есть все пары ключ-значение, доступные одновременно. Клавиши String s, если это имеет значение.

Было бы также неплохо узнать, на какой размер стоит отойти от [(key, val)].

Answer 1

Вы можете рассмотреть:

• Data.Map

или, альтернативно,

• Data.HashMap

Первый - это стандартный контейнер для хранения и поиска элементов по ключам в Haskell. Последняя представляет собой новую библиотеку, специально оптимизированную для хеширования ключей.

Недавний доклад Йохана Тибелла Ускорение устойчивых структур данных за счет хеширования дает обзор, в то время как в недавней статье Милана Страки *1024* конкретно описывается структура Data.Map и пакет hashmap.

Answer 2

Если у вас есть все пары ключ-значение, вам может потребоваться идеальная хеш-функция .

Бенчмаркинг подскажет вам, когда переключаться из простого списка.