Для алгоритма автоматов мне нужна быстрая структура данных Union-Find на функциональном языке. Поскольку мне нужно официально доказать правильность структуры данных, я бы предпочел бы простую структуру.
Я пытаюсь вычислить классы эквивалентности элементов в наборе S w.r.t. отношение R ⊆ S × S. В конце я хочу получить некоторую функцию f: S → S, которая отображает любой элемент S в (канонический) представитель своего класса R -эквивалентности. Под "каноническим" я подразумеваю, что мне все равно, какой представитель он до тех пор, пока он одинаковый для всех элементов одного класса эквивалентности, т.е. Я хочу f x = f y ⟺ (x,y) ∈ R удерживать.
Какова была бы лучшая структура данных и алгоритм для этого в функциональном языке? Я должен добавить, что мне действительно нужен "нормальный" функциональный код, т.е. Не монады трансформации/состояния трансформатора.
EDIT: В то же время я придумал этот алгоритм:
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} - это дешевая операция над этой структурой.)
