Data.UnionFind

A persistent, but not so efficient union-find structure.

Documentation

newtype UnionFind a

Constructors

UnionFind

Fields

unUnionFind :: Map a a

Instances

Typeable1 UnionFind

Eq a => Eq (UnionFind a)

(Data a, Ord a) => Data (UnionFind a)

Ord a => Ord (UnionFind a)

Show a => Show (UnionFind a)

Ord a => Monoid (UnionFind a)

con_UnionFind :: Constr

ty_T :: DataType

unionFind :: Ord a => Map a a -> UnionFind a

Smart constructor from a Map to a union-find structure.

map :: (Ord a, Ord b) => (a -> b) -> UnionFind a -> UnionFind b

empty :: UnionFind a

empty is the syntactic identity equivalence relation.

size :: UnionFind a -> Int

size uf returns the number of stored equalities.

equate :: Ord a => a -> a -> UnionFind a -> UnionFind a

equate x y uf inserts the equality x = y into uf.

fromList :: Ord a => [(a, a)] -> UnionFind a

equateList :: Ord a => UnionFind a -> [(a, a)] -> UnionFind a

toList :: UnionFind a -> [(a, a)]

union :: Ord a => UnionFind a -> UnionFind a -> UnionFind a

find :: Ord a => a -> UnionFind a -> Maybe a

find x uf returns the representative of the equivalence class that x belongs to in uf, if there is any.

findWithDefault :: Ord a => a -> a -> UnionFind a -> a

findWithDefault def x uf returns the representative of the equivalence class that x belongs to in uf or def, if there is no representative.

equiv :: Ord a => (a, a) -> UnionFind a -> Bool

(x,y) equiv uf iff x and y are in the same equivalence class with respect to uf.