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

Question

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

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

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

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

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

Answer 1

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

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

Answer 2

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

Answer 3

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

Answer 4

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