Быстрый поиск элементов для функционального языка (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). HashTables (которые не являются чисто функциональными) будут иметь O (1).

Answer 3

Посмотрите на хеш-таблицы Джуди , если вы не против поместить код в монаду ввода-вывода.

Answer 4

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