Скажем, мы просматриваем график и хотим быстро определить, был ли вид node раньше или нет. У нас есть несколько предусловий.
Любые идеи для этого в чисто функциональном ключе (без таблиц Hash или массивов).
Мне нужна структура данных с двумя работающими над ней функциями; add (добавляет встреченное целое число) и lookup (проверяет, добавлено ли целое число). Оба должны предпочтительно брать O (n) время, амортизированное для N повторений.
Возможно ли это?
Вы можете использовать Data.Set. Вы добавляете элемент, создавая новый набор из старого с insert и передавая новый набор. Вы просматриваете, является ли элемент членом набора с помощью member. Обе операции: O (log n).
Возможно, вы могли бы рассмотреть возможность использования государственной монады для потоковой передачи набора.
Эффективный поиск элементов на функциональных языках довольно сложно. Data.Set (как показано выше) реализуется с использованием двоичного дерева, которое может быть создано чисто функциональным способом, обеспечивающим операции поиска в O (log n). Хэш-таблицы (которые не являются чисто функциональными) имели бы O (1).
Я считаю, что Data.BitSet может быть O (n).
Взгляните на judy hashtables, если вы не против упаковки вашего кода в монаде IO.