Classes d'équivalence et union / find dans un langage fonctionnel

pour un algorithme automata, j'ai besoin d'une structure de données Union-Find rapide dans un langage fonctionnel. Comme je dois prouver formellement l'exactitude de la structure des données, je préférerais une structure simple.

ce que j'essaie de faire, c'est de calculer les classes d'équivalence des éléments dans un ensemble S W. R. T. une relation R ⊆ S × S. Ce que je veux obtenir à la fin est une fonction f: S → S qui correspond à n'importe quel élément de S à un représentant (canonique) de son R-classe d'équivalence. Par "canonique", je veux dire que je me fous de quel représentant il s'agit tant qu'il est le même pour tous les éléments d'une classe d'équivalence, i.e. je veux f x = f y ⟺ (x,y) ∈ R à tenir.

quelle serait la meilleure structure de données et le meilleur algorithme pour cela dans un langage fonctionnel? Je dois ajouter que j'ai vraiment besoin de code fonctionnel "normal", c'est-à-dire pas de monades de transformateur de mutabilité/état.

EDIT: Dans le temps de le dire, je suis venu avec cette algorithme:

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]

Cela crée une carte qui associe à tout élément de S pour le représentant de sa classe d'équivalence, où le représentant est le premier élément qui est atteint par l'itération sur S. Je pense que cela a en fait le temps linéaire (si les opérations de carte sont constantes). Cependant, je m'intéresse toujours à d'autres solutions, car je ne sais pas si c'est efficace dans la pratique.

(ma relation est représenté en interne comme un "S → (S Set) option", d'où l'itération au - dessus de {t | (s,T) le pion r} - c'est une opération bon marché sur cette structure.)