Klasy równoważności i połączenie/znajdowanie w języku funkcjonalnym

Question

Do algorytmu automatów potrzebuję szybkiej struktury danych Union-Find w języku funkcjonalnym. Ponieważ muszę formalnie udowodnić poprawność struktury danych, wolałbym prostą strukturę.

Co próbuję zrobić, to obliczyć klasy równoważności elementów w zbiorze S w.r.t. relacja R ⊆ S × S. To, co chcę wydostać na końcu, to jakaś funkcja f: S → S, która odwzorowuje dowolny element z S na (kanoniczną) reprezentację jego klasy dekompresji R. Przez "kanoniczny", mam na myśli to, że nie obchodzi mnie, który przedstawiciel jest tak długi, jak długo jest taki sam dla wszystkich elementów jednej klasy równoważności, tj. Chcę, aby f x = f y ⟺ (x,y) ∈ R trzymał.

Jaka byłaby najlepsza struktura danych i algorytm w języku funkcjonalnym? Powinienem dodać, że naprawdę potrzebuję "normalnego" kodu funkcjonalnego, tzn. Bez monad transformacyjnych/transformatorów stanu.

EDIT: W tym czasie, mam wymyślić tego algorytmu:

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] 

Stwarza to mapa, która mapuje dowolny element S do przedstawiciela tej klasy równoważności, gdzie przedstawiciel jest pierwszym element osiągnięty przez iterację ponad S. Myślę, że ma to liniowy czas (jeśli operacje na mapie są stałe). Jednak nadal jestem zainteresowany innymi rozwiązaniami, ponieważ nie wiem, jak efektywne jest to w praktyce.

(my związek jest wewnętrznie reprezentowane jako "wariant S → (S Set)", stąd iteracji się. {T | (s, t) ∈ R} - jest tani wykonywania tej konstrukcji)

Answer 1

AFAIK (i szybkie wyszukiwanie mnie nie zniechęciło), nie ma znanego czysto funkcjonalnego odpowiednika standardowego disjoint-set datastructure, który ma porównywalne osiągi asymptotyczne (amortyzowana funkcja odwrotna-Ackermanna). (konwencjonalna struktura danych nie jest czysto funkcjonalna, ponieważ wymaga przeprowadzenia destrukcyjnej aktualizacji w celu kompresji ścieżki).

Jeśli nie ustawiłeś na czysto funkcjonalną, możesz po prostu użyć destrukcyjnej aktualizacji i wdrożyć konwencjonalną bazę danych.

Jeśli nie zależy Ci na dopasowaniu asymptotycznej wydajności, możesz zastąpić tablicę dostępu swobodnego konwencjonalnej struktury danych wartością persistent associative map, kosztem dodatkowego współczynnika wydajności O (log N) i konieczności zweryfikowania jej poprawność.

Jeśli chcesz uzyskać maksymalną prostotę w celu weryfikacji i nie ustawiłeś w trybie dead-set na żadnym z powyższych, możesz użyć aktualizacji tablicy i upuścić optymalizację związaną z pozycją. IIRC daje to O (log N) amortyzację najgorszego przypadku, ale może faktycznie poprawić praktyczną szybkość wykonania (ponieważ ranga nie musi być dłużej przechowywana lub zarządzana).