ポエトリークラブ

素集合（union-find構造）は、値の集まりを重なりのないグループに分割した状態で保持し、ある1つの問いにすばやく答えます。その問いとは、この2つの値は同じグループにあるかどうかです。これはdisjoint-setsボキャブラリーにあります。

素集合を組み立てる

<disjoint-set>は空の構造を組み立てます。値（アトム）は、add-atomで1つずつ追加するか、add-atomsでシーケンスからまとめて追加します。それぞれのアトムは最初、自分だけのグループに入っています。

<disjoint-set> ( -- disjoint-set )
add-atom       ( atom disjoint-set -- )
add-atoms      ( seq disjoint-set -- )

USING: disjoint-sets ;

<disjoint-set>
{ 1 2 3 } over add-atoms   ! 1, 2 and 3 each in their own group

素集合はミュータブルです。add-atom、add-atoms、equateは、新しいものを返すのではなく、その場で書き換えます。これらのワードが素集合を消費したあとに、その素集合を再びスタックに戻したいときはkeepが便利です。

グループを統合する

equateは、そのアトムが属する2つのグループを統合します。統合は推移的です。2つのアトムを統合し、次にそのどちらかを3つ目のアトムと統合すると、3つとも同じグループになります。

equate ( atom1 atom2 disjoint-set -- )

代表元

それぞれのグループには、標準となるメンバーが1つあり、それを代表元と呼びます。representativeはそれを返します。2つのアトムが同じグループに属するのは、それらの代表元が等しいときに限られます。

representative ( atom disjoint-set -- representative )

USING: disjoint-sets ;

<disjoint-set>
{ 1 2 3 } over add-atoms
1 2 pick equate
1 over representative .   ! => 1
2 over representative .   ! => 1   (same representative as 1)
3 over representative .   ! => 3   (still on its own)

グループがどのアトムを代表元に選ぶかは内部の詳細です。特定のアトムが選ばれることを当てにしてはいけません。当てにしてよいのは、同じグループの2つのアトムの代表元が一致していることだけです。