Быстрый поиск элементов для функционального языка (Haskell)

Скажем, мы просматриваем график и хотим быстро определить, был ли вид node раньше или нет. У нас есть несколько предусловий.

Узлы отмечены целыми значениями 1..N
График реализуется с узлами, имеющими список смежности
Каждое целочисленное значение из 1..N встречается в графе, который имеет размер N

Любые идеи для этого в чисто функциональном ключе (без таблиц Hash или массивов).

Мне нужна структура данных с двумя работающими над ней функциями; add (добавляет встреченное целое число) и lookup (проверяет, добавлено ли целое число). Оба должны предпочтительно брать O (n) время, амортизированное для N повторений.

Возможно ли это?

Ответ 1

Вы можете использовать Data.Set. Вы добавляете элемент, создавая новый набор из старого с insert и передавая новый набор. Вы просматриваете, является ли элемент членом набора с помощью member. Обе операции: O (log n).

Возможно, вы могли бы рассмотреть возможность использования государственной монады для потоковой передачи набора.

Ответ 2

Эффективный поиск элементов на функциональных языках довольно сложно. Data.Set (как показано выше) реализуется с использованием двоичного дерева, которое может быть создано чисто функциональным способом, обеспечивающим операции поиска в O (log n). Хэш-таблицы (которые не являются чисто функциональными) имели бы O (1).

Ответ 3

Я считаю, что Data.BitSet может быть O (n).

Ответ 4

Взгляните на judy hashtables, если вы не против упаковки вашего кода в монаде IO.