Классы эквивалентности и объединения / поиска на функциональном языке

Question

Для алгоритма автоматов мне нужна быстрая структура данных Union-Find на функциональном языке. Поскольку мне нужно формально доказать правильность структуры данных, я бы предпочел простую структуру.

Я пытаюсь вычислить классы эквивалентности элементов в наборе. S по отношению R ⊆ S × S, Что я хочу получить в конце концов, это какая-то функция f: S → S который отображает любой элемент S (каноническому) представителю его Rкласс эквивалентности. Под "каноническим" я подразумеваю, что мне все равно, какой это представитель, если он одинаков для всех элементов одного класса эквивалентности, т.е. f x = f y ⟺ (x,y) ∈ R держать.

Какова будет лучшая структура данных и алгоритм для этого на функциональном языке? Я должен добавить, что мне действительно нужен "нормальный" функциональный код, то есть не монады изменяемости / преобразования состояния.

РЕДАКТИРОВАТЬ: В то же время я придумал этот алгоритм:

m := empty map
for each s ∈ S do
  if m s = None then
    for each t in {t | (s,t) ∈ R}
      m := m[t ↦ s]

Это создает карту, которая отображает любой элемент S представителю его класса эквивалентности, где представителем является первый элемент, который достигается итерацией по S, Я думаю, что это на самом деле имеет линейное время (если операции карты постоянны). Однако меня все еще интересуют другие решения, поскольку я не знаю, насколько это эффективно на практике.

(мое отношение внутренне представляется как "опция S → (S Set)", поэтому итерация по {t | (s,t) ∈ R} - это дешевая операция на этой структуре.)

Answer 1

AFAIK (и быстрый поиск не разочаровал меня), нет никакого известного чисто функционального эквивалента обычной структуры данных с несвязным множеством, которая имеет сопоставимые асимптотические характеристики (амортизированная обратная функция Аккермана). (обычная структура данных не является чисто функциональной, поскольку для ее сжатия требуется деструктивное обновление)

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

Если вас не интересует сопоставление асимптотической производительности, вы можете заменить массив произвольного доступа обычной структуры данных на постоянную ассоциативную карту за счет дополнительного коэффициента производительности O(log N) и необходимости проверки его правильности.

Если вам нужна максимальная простота в целях проверки, и вы не уста- новлены ни в одном из перечисленных выше случаев, вы можете использовать обновляемый массив и отказаться от оптимизации по рангу. IIRC это дает O(log N) амортизированную производительность в худшем случае, но может фактически повысить практическую скорость выполнения (поскольку ранг больше не нужно хранить или управлять).