オートマトン アルゴリズムの場合、関数型言語による高速の Union-Find データ構造が必要です。データ構造の正しさを正式に証明する必要があるため、単純な構造を好みます。
私がやろうとしているのはS、関係に関するセット内の要素の等価クラスを計算することR ⊆ S × Sです。最後に知りたいのは、 の任意の要素をその等価クラスの (正規の) 代表にf: S → Sマップする関数です。「標準的」とは、1 つの等価クラスのすべての要素で同じである限り、つまり保持したい限り、どの代表であってもかまわないことを意味します。SRf 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} に対する反復 - これはその構造に対する安価な操作です。)