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

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

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

Какие-нибудь идеи для того, чтобы сделать это чисто функциональным способом? (Хеш-таблицы или массивы не допускаются).

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

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

Ответы [ 4 ]

9 голосов
/ 13 ноября 2008

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

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

1 голос
/ 17 мая 2009

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

0 голосов
/ 22 февраля 2011

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

0 голосов
/ 27 июля 2010

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

...